Tutorial :Why does this Haskell code work successfully with infinite lists?



Question:

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??


Solution:1

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  


Solution:2

My understanding of foldr is that it will loop through every item in the list (and perhaps that understanding is incomplete).

foldr (unlike foldl) does not have to loop through every item of the list. It is instructive to look at how foldr is defined.

foldr f z []     = z  foldr f z (x:xs) = f x (foldr f z xs)  

When a call to foldr is evaluated, it forces the evaluation of a call to the function f. But note how the recursive call to foldr is embedded into an argument to the function f. That recursive call is not evaluated if f does not evaluate its second argument.


Solution:3

The key point here is that Haskell is a non-strict language. "Non-strict" means that it allows non-strict functions, which in turn means that function parameters may not be fully evaluated before they may be used. This obviously allows for lazy evaluation, which is "a technique of delaying a computation until the result is required".

Start from this Wiki article


Solution:4

I do not know Haskell, but I suspect that in your case, it works because of lazy evaluation. Because it allows you to work with list infinitely long, when you access it, it will compute the result as you need it.

See http://en.wikipedia.org/wiki/Lazy_evaluation


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »