CODEWITHSUNDEEP
haskellrecursion
fangyc
fangyc

Reputation: 93

What's the real procedure of evaluating recursive data in Haskell?

I'm trying to understand recursive data, and I'm a little confused. I tried this:

m = 1 : map (+1) m

and this produced a list identical to [1..]. I tried to complete the evaluation procedure like this:

m = 1 : map (+1) m
  = 1 : map (+1) (1 : map (+1) m)
  = 1 : 2 : map (+1) (map (+1) m)
  = 1 : 2 : map (+1) (map (+1) (1 : 2 : map (+1) (map (+1) m)) )
  = 1 : 2 : map (+1) (2 : map (+1) (2 : (map (+1) (map (+1) m)) )
  = 1 : 2 : 3 : map (+1) (map (+1) (2 : (map (+1) (map (+1) m)))
  = 1 : 2 : 3 : map (+1) (3 : map (+1) ( (map (+1) (map (+1) m))) )
  = 1 : 2 : 3 : 4 : map (+1) (map (+1) ( (map (+1) (map (+1) m)) ))
  = ...

there are a lot of map (+1) stuff in the tail and increasing with the procedure. Are there really so many map (+1) and repeated calculation of map (+1) ... ? I've read other posts mentioning thunks, but how to actually relate them all together? Thank you very much.

Upvotes: 1

Views: 123

Answers (1)

bheklilr
bheklilr

Reputation: 54058

What would happen is more like the following

m = 1 : map (+1) m
    1 : map (+1) (1 : _)
        ^------------<|     Points to the same thunk in memory
    1 : a : map (+1) (a : _) where a = ((+1) 1)
            ^------------<|
    1 : 2 : map (+1) (2 : _)
            ^------------<|
    1 : 2 : a : map (+1) (a : _) where a = ((+1) 2)
                ^------------<|
    1 : 2 : 3 : map (+1) (3 : _)
                ^------------<|
    1 : 2 : 3 : a : map (+1) (a : _) where a = ((+1) 3)
                    ^------------<|
    1 : 2 : 3 : 4 : map (+1) (4 : _)
                    ^------------<|

The next element in the list passed to map always points back to the element map is about to generate.

However, it is important to note that the Haskell specification states that it must be lazy, but the manner in which the laziness is implemented is up to the compiler. It may choose to optimize away a lot of this into a simple loop in assembly, or depending on how the output is used, it might do some loop fusion to combine several traversals into one.

Upvotes: 1

Related Questions