[Haskell-beginners] Re: folds again -- myCycle
Will Ness
will_n48 at yahoo.com
Wed Mar 18 07:23:57 EDT 2009
7stud <bbxx789_05ss <at> yahoo.com> writes:
>
> Daniel Fischer <daniel.is.fischer <at> web.de> 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.
More information about the Beginners
mailing list