Why are these functions differently evaluated

Question

I was experimenting with haskell, and while trying to improve the readability of my code I suddenly changed the behaviour of it. I would have thought these two variants would be equivalent.

Original:

f :: Eq c => c -> c -> [[c]] -> [[c]]
f d c acc  
  | c == d    = [] : acc
  | otherwise = ([c] ++ (head acc)) : tail acc

split :: Eq a => a -> [a] -> [[a]]
split delim = foldr (f delim) [[]]

Here is the second one:

f' :: Eq c => c -> c -> [[c]] -> [[c]]
f' d c (currentWord:wordsSoFar)  
  | c == d    = [] : currentWord : wordsSoFar
  | otherwise = (c : currentWord) : wordsSoFar

split' :: Eq a => a -> [a] -> [[a]]
split' delim = foldr (f' delim) [[]]

Here are the results of running the two:

*Main> take 1 (split 5 [1..])
[[1,2,3,4]]
*Main> take 1 (split' 5 [1..])
*** Exception: stack overflow

Answer 1

Your first version only needs to evaluate acc when you call head and tail on it, so no evaluation takes place when c == d.

The second version needs to know whether acc is empty or not before it does anything else as none of the other code must execute if the pattern does not match. This means that acc has to be evaluated even if c == d. This leads to an infinite loop.

You can make the second version work by using an irrefutable pattern like this:

f' d c ~(currentWord:wordsSoFar) =

By making the pattern irrefutable, you're saying that you know that the pattern will match, so no check is necessary. If acc were empty, this would cause an error to happen when (and if) you used currentWord and wordsSoFar instead of a non-exhaustive pattern error happening right away (and regardless of whether currentWord and wordsSoFar are actually used).