Haskell lazy appreciation

Question

If I call the following Haskell code

find_first_occurrence :: (Eq a) => a -> [a] -> Int find_first_occurrence elem list = (snd . head) [x | x <- zip list [0..], fst x == elem] 

with arguments

 'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj" 

how many of the zipped list [('a',0), ('b',1), ] will be created?

UPDATE:

I tried to run

 find_first_occurrence 10 [1..] 

and returns 9 almost instantly, so I assume it uses a lazy rating, at least for simple cases? The response is also calculated “instantly” when I run

 let fn = 100 - n find_first_occurrence 10 (map f [1..]) 

Answer 1

All this.

Since StackOverflow does not allow me to post such a short answer: you cannot leave with less work than browsing the entire list if the thing you are looking for does not exist.

Edit: The question now asks something much more interesting. The short answer is that we will build a list:

 ('a',0):('b',1):('c',2):('d',3):('X',4):<thunk> 

(Actually, this answer is just the slightest bit subtle. Your type signature uses the Int monomorphic return type, which is strict mainly in all operations, so all numbers in the tuples above will be fully appreciated. Of course the Num implementations for which you would get something with lots of thunks though.)

Answer 2

Short answer: it will only be created before the item you are looking for. This means that only in the worst case you will need to build the entire list, that is, when not a single element satisfies the conditions.

Long answer: let me explain why with a couple of examples:

 ghci> head [a | (a,b) <- zip [1..] [1..], a > 10] 11 

In this case, zip should create an infinite list, but the tape allows Haskell to build it only up to (11,11) : as you can see, the execution does not diverge, but in fact gives us the correct answer.

Now let me consider another problem:

 ghci> find_first_occurrence 1 [0, 0, 1 `div` 0, 1] *** Exception: divide by zero ghci> find_first_occurrence 1 [0, 1, 1 `div` 0, 0] 1 it :: Int (0.02 secs, 1577136 bytes) 

Since the entire zip list is not built, haskell, obviously, will not even evaluate every expression that occurs in the list, therefore, when the element is before div 1 0 , the function is correctly calculated without any exceptions: division by zero does not occur.

Answer 3

You can easily answer such a question by entering undefined here and there. In our case, it is enough to change our inputs:

 find_first_occurrence 'X' ("abcdX" ++ undefined) 

You can see that it produces the result, which means that it does not even go beyond the found "X" (otherwise he would have chosen an exception). Obviously, a zipped list cannot be built without looking at the original list.

Another (possibly less reliable) way to analyze your laziness is to use the trace function from Debug.Trace :

 > let find_first_occurrence elem list = (snd . head) [x | x <- map (\i -> trace (show i) i) $ zip list [0..], fst x == elem] > find_first_occurrence 'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj" 

Print

 ('a',0) ('b',1) ('c',2) ('d',3) ('X',4) 4