R – Why does this Haskell code work successfully with infinite lists

foldfunctional programminghaskellinfinite

I have some Haskell code that does work correctly on an infinite list, but I do not understand why it can do so successfully. (I modified my original code — that did not handle infinite lists — to incorporate something from some other code online, and suddenly I see that it works but don't know why).

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
   where
      step item acc = p item || acc

My understanding of foldr is that it will loop through every item in the list (and perhaps that understanding is incomplete). If so, it should not matter how the "step" function is phrased … the code should be unable to handle infinite loops.

However, the following works:

*Main Data.List> myAny even [1..]
True

Please help me understand: why??

Best Answer

Let's do a little trace in our heads of how Haskell will evaluate your expression. Substituting equals for equals on each line, the expression pretty quickly evaluates to True:

myAny even [1..]
foldr step False [1..]
step 1 (foldr step False [2..])
even 1 || (foldr step False [2..])
False  || (foldr step False [2..])
foldr step False [2..]
step 2 (foldr step False [3..])
even 2 || (foldr step False [3..])
True   || (foldr step false [3..])
True

This works because acc is passed as an unevaluated thunk (lazy evaluation), but also because the || function is strict in its first argument.

So this terminates:

True || and (repeat True)

But this does not:

and (repeat True) || True

Look at the definition of || to see why this is the case:

True  || _ =  True
False || x =  x

Related Solutions

Haskell – Why does this Haskell code produce the “infinite type” error

The problem is in the last clause, where you treat x and y as elements, while they are lists. This will work:

intersperse _ [] = []
intersperse _ [x] = x 
intersperse s (x:y:xs) = x ++ [s] ++ y ++ intersperse s xs

The infinite type error occurs because the : operator has type a -> [a] -> [a], while you treat it as [a] -> a -> [a], which means that [a] must be identified with a, which would mean that a is an infinitely nested list. That is not allowed (and not what you mean, anyway).

Edit: there is also another bug in the above code. It should be:

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) = x ++ [s] ++ intersperse s xs

R – Why does this first Haskell function FAIL to handle infinite lists, while this second snippet SUCCEEDS with infinite lists

Others have pointed out the problem, which is that step always evaluates its second argument before producing any output at all, yet its second argument will ultimately depend on the result of another invocation of step when the foldr is applied to an infinite list.

It doesn't have to be written this way, but your second version is kind of ugly because it relies on the initial argument to step having a particular format and it's quite hard to see that the head/tail will never go wrong. (I'm not even 100% certain that they won't!)

What you should do is restructure the first version so it produces output without depending on the input list in at least some situations. In particular we can see that when the character is not a space, there's always at least one element in the output list. So delay the pattern-matching on the second argument until after producing that first element. The case where the character is a space will still be dependent on the list, but that's fine because the only way that case can infinitely recurse is if you pass in an infinite list of spaces, in which case not producing any output and going into a loop is the expected behaviour for words (what else could it do?)

Best Answer

Related Solutions

Haskell – Why does this Haskell code produce the “infinite type” error

R – Why does this first Haskell function FAIL to handle infinite lists, while this second snippet SUCCEEDS with infinite lists

Related Topic