[Haskell-cafe] Stack overflow

[Albert Y. C. Lai]

Grzegorz wrote:
> hammingDistance [] _ = 0
> hammingDistance _ [] = 0
> hammingDistance (x:xs) (y:ys) | x==y      = hammingDistance xs ys
>                               | otherwise = 1 + hammingDistance xs ys

hammingDistance xs ys = h xs ys 0
     where
       h [] _ n = n
       h _ [] n = n
       h (x:xs) (y:ys) n | x==y      = h xs ys n
                         | otherwise = h xs ys $! (n+1)

It is also possible to use a bang pattern on the parameter n. I'm too 
lazy to look up how to do it.

But that is not the end of the problem.

>             modify (\ (sum,count) -> ((,) $! hammingDistance xs ys + sum) $!
> count + 1)

modify still delays state update, i.e., its code says

     s <- get
     put (f s)

therefore s nor f s is evaluated now. Loop over it, and you will 
accumulate a thunk equivalent to

     f (f (f (f (... (f s)...

and that costs stack.

Try your own version of modify, e.g.,

     modifies f =
         do s <- get
            put $! f s

and that does it.