[Haskell-cafe] One-Off detection. Question about Space/Time complexity

Richard A. O'Keefe ok at cs.otago.ac.nz
Thu Mar 23 23:21:59 UTC 2017

> On 23/03/2017, at 9:52 PM, Andrew Butterfield <Andrew.Butterfield at scss.tcd.ie> wrote:
> It can be done in one sweep down both strings together - look for the first difference,
> and then test hypotheses regarding the 5 possible edits
> oneOff :: String -> String -> Bool
> oneOff [] [] = False
> oneOff [] (_:rest) = null rest
> oneOff (_:rest) [] = null rest
> oneOff s1@(c1:s1') s2@(c2:s2')
>  | c1 == c2  =  oneOff s1' s2'  -- keep looking
>  | otherwise  
>      =    s1' == s2   -- s2 is s1 with c1 deleted or s1 is s2 with c1 inserted 
>        || s2' == s1   -- s1 is s2 with c2 deleted or s2 is s1 with c2 inserted
>        || s1' == s2'  -- c1 is s1 was replaced by c2 in s2, or v.v.
> I guess the above should be O(1) in space

The question is what "O(1) in space" means here.

If you discount the storage required for the strings, fine.
If however you think in terms of lazy lists of characters,
the fact that this code will look at the tails of the lists
up to 3 times means that those tails will be stored, so we
are talking about O(n) space.

I believe it is possible to walk down s1 s1' s2 s2' in a
single pass, maintaining "streaming".

Whether it is _worth_ doing that is another matter.

More information about the Haskell-Cafe mailing list