7stud
Daniel Fischer
writes: variant 2: foldr rightAdd [] ones ~> foldr rightAdd [] (1:ones) ~> rightAdd 1 (foldr rightAdd [] ones) ~> (foldr rightAdd [] ones) ++ xs
and variant 2 [amounts] to: myCycle2 xs = let ys = ys ++ xs in ys
Ah, well. I again underestimated how much experience one needs to see it immediately, sorry once more.
The right hand side of myCycle2's definition (if we specialise xs to, say, [1,2,3])
Ok, I see now. Using this definition:
myCycle2 xs = let ys = ys ++ xs in ys
Then calling:
myCycle2 [1, 2, 3]
You get:
let ys = ys ++ [1, 2, 3]
But what is the value of ys on the right hand side? ... and then you need to substitute the value for ys again on the right hand side, and so on ad infinitum.
Exactly! That's what's called LEFT recursion: the 'ys' in the re-write expression is ON THE LEFT SIDE of the expression, and so is immediately needed, before the lazyness of list-access has a chance to kick in. Note that the definition itself doesn't cause any infinite looping, only the actual list access will do that. I would recommend first to think about Haskell code in terms of rewritable equivalence equations. Forget the supposed efficiency conserns, at first. Just think of definitions as of equations you can use to rewrite your expressions, in whichever order best suits you and assume the compiler will find the same way of simplifying your expression; and realize that simplification is triggered by _pattern_ _matching_ on _access_. That is, until a value is needed at the top level, the definition is just a definition, dormant and ready to be used, nothing more - regardless whether it's implemented via thunks or not. In our case, having head (x:xs) = x The access in (head ys) gets traslated in head ys = head (ys ++ [1,2,3]) = head ((ys ++ [1,2,3]) ++ [1,2,3]) but for the other defintion let zs = [1, 2, 3] ++ zs it's head zs = head([1, 2, 3] ++ zs) = head( (1:[2,3]) ++ zs) = head( 1:([2,3]++zs) ) = 1 according to the defintion of (++), (x:xs)++ys = x:(xs++ys) Were we to use the foldr definition, it'll get rewritten just the same, using the foldr definition (as long as it's not the left-recursive defintion): foldr f z (a:as) = a `f` foldr f z as let ws = foldr (:) [1,2,3] ws head ws = head (foldr (:) [1,2,3] ws) = head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)) because 'ws' is getting matched against (a:as) pattern in foldr definition, so is immediately needed, causing INFINITE looping. BUT let qs = foldr (:) qs [1,2,3] head qs = head( foldr (:) qs [1,2,3] ) = head( 1:foldr (:) qs [2,3]) = 1 So remember just these two rules: 1) the defintion is just a re-write equation, and 2) a value is forced by being pattern matched - and you'll be fine.