CODEWITHSUNDEEP
haskelllazy-evaluation
morten
morten

Reputation: 401

Why are these functions differently evaluated

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

Upvotes: 10

Views: 212

Answers (2)

sepp2k
sepp2k

Reputation: 370425

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).

Upvotes: 8

MathematicalOrchid
MathematicalOrchid

Reputation: 62848

I think this should be equivalent:

f d c acc | c == d = [] : acc
f d c (currentWord:wordsSoFar) = (c : currentWord) : wordsSoFar

Notice that if c == d then we don't attempt to determine whether acc is empty or not. (All versions of your code will actually fail if c == d and acc == []; I presume this never happens.)

Upvotes: 2

Related Questions