folds again -- myCycle

classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

folds again -- myCycle

7stud-2
I spent a long time working on a solution for an exercise in RWH: if you can,
use foldr to mimic haskell's cycle function.  At first, I wondered whether
it was even possible.  Then I worked on some ideas, and finally I came up with
a solution.  Surprisingly, my solution ended up being very simple:

myCycle [] = []
myCycle xs = helperFunc xs [1..]
    where helperFunc ys foldrXs = foldr accFunc [] foldrXs
            where accFunc _ acc = ys ++ acc  

I tested it out, and it worked like a charm:

*Main> let x = myCycle [1, 2, 3]
*Main> take 2 x  
[1,2]
*Main> take 10 x
[1,2,3,1,2,3,1,2,3,1]
*Main> take 30 x
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]

After re-examining my solution, I decided that this line:

--where accFunc _ acc = ys ++ acc

read better like this:

--where accFunc _ acc =  acc ++ ys

The altered function returns a list just fine.  But when I use take on the
list, I get a stack overflow. What is being thunked in both cases?
                                     
Thanks.




Reply | Threaded
Open this post in threaded view
|

folds again -- myCycle

Daniel Fischer-4
Am Samstag, 14. M?rz 2009 08:57 schrieb 7stud:

> I spent a long time working on a solution for an exercise in RWH: if you
> can, use foldr to mimic haskell's cycle function.  At first, I wondered
> whether it was even possible.  Then I worked on some ideas, and finally I
> came up with a solution.  Surprisingly, my solution ended up being very
> simple:
>
> myCycle [] = []
> myCycle xs = helperFunc xs [1..]
>     where helperFunc ys foldrXs = foldr accFunc [] foldrXs
>             where accFunc _ acc = ys ++ acc
>
> I tested it out, and it worked like a charm:
>
> *Main> let x = myCycle [1, 2, 3]
> *Main> take 2 x
> [1,2]
> *Main> take 10 x
> [1,2,3,1,2,3,1,2,3,1]
> *Main> take 30 x
> [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
>
> After re-examining my solution, I decided that this line:
>
> --where accFunc _ acc = ys ++ acc
>
> read better like this:
>
> --where accFunc _ acc =  acc ++ ys
>
> The altered function returns a list just fine.  But when I use take on the
> list, I get a stack overflow. What is being thunked in both cases?

Let us rewrite the definition a little (looking only at the case for nonempty
lists):

Variant 1:
myCycle xs = foldr leftAdd [] [1 .. ]
   where
      leftAdd _ acc = xs ++ acc

foldr leftAdd [] [1 .. ]
   ~> leftAdd 1 (foldr leftAdd [] [2 .. ])
   ~> xs ++ (foldr leftAdd [] [2 .. ])
   ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
   ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
   ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))

Variant 2:
myCycle xs = foldr rightAdd [] [1 .. ]
   where
      rightAdd _ acc = acc ++ xs

foldr rightAdd [] [1 .. ]
   ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
   ~> (foldr rightAdd [] [2 .. ]) ++ xs
   ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
   ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
   ~> (((... ++ xs) ++ xs) ++ xs

So in the first variant, where the cycled list is added to the front of the
accumulator, the first elements of the list can be accessed before the
accumulator is evaluated.
In the second variant, the front of the result list is the accumulator, so it
has to be evaluated before any part of the result can be accessed.
Unfortunately, the front is an infinite nesting of concatenations, so its
evaluation never finishes.

The thing is that leftAdd is lazy in its second argument, while rightAdd is
strict in it.
If the accumulation function used in foldr is strict in its second argument,
before any part of the result can be accessed, the whole list has to be
traversed (which obviously will never finish for infinite lists).

Let us rewrite it a little more.
Obviously, it doesn't matter which list is passed into
foldr leftAdd []
, as long as it's infinite. So instead of passing [1 .. ], let us pass a
simpler infinite list, say
ones = 1:ones
(or ones = repeat 1).
Then the evaluation becomes

foldr leftAdd [] ones
   ~> foldr leftAdd [] (1:ones)
   ~> leftAdd 1 (foldr leftAdd [] ones)
   ~> xs ++ (foldr leftAdd [] ones)

foldr rightAdd [] ones
   ~> foldr rightAdd [] (1:ones)
   ~> rightAdd 1 (foldr rightAdd [] ones)
   ~> (foldr rightAdd [] ones) ++ xs

So variant 1 amounts to
myCycle xs = let ys = xs ++ ys in ys
and variant 2 to
myCycle2 xs = let ys = ys ++ xs in ys

Now it should be easy to see why the first works, but not the second.

And from the rewriting, we can read off another representation of cycle as a
fold.
We have, for all lists ks, ms:
ks ++ ms = foldr (:) ms ks

So we can write variant 1 as the snappy

myCycle xs = let ys = foldr (:) ys xs in ys

>
> Thanks.

HTH,
Daniel
Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

>
> Am Samstag, 14. M?rz 2009 08:57 schrieb 7stud:
> > I spent a long time working on a solution for an exercise in RWH: if you
> > can, use foldr to mimic haskell's cycle function.  At first, I wondered
>
> So variant 1 amounts to
> myCycle xs = let ys = xs ++ ys in ys

i.e.

myCycle xs = ys where ys = xs ++ ys

or

myCycle xs = xs ++ myCycle xs

- "right recursion" - good (kind of) even under strict semantics - will
actually construct an infinite list in memory (although useless under strict,
since it'll never stop).


> and variant 2 to
> myCycle2 xs = let ys = ys ++ xs in ys

i.e.

myCycle2 xs = ys where ys = ys ++ xs

or

myCycle2 xs = myCycle2 xs ++ xs

- "left recursion" - does nothing under both strict and non-strict semantics -
just goes into infinite loop trying to figure out what to do but never gets to
do anything really.


> We have, for all lists ks, ms:
> ks ++ ms = foldr (:) ms ks


which then by direct application yields

-- myCycle xs = xs ++ myCycle xs

myCycle xs = foldr (:) (myCycle xs) xs


>
> So we can write variant 1 as the snappy
>
> myCycle xs = let ys = foldr (:) ys xs in ys


which is then just rewritable as:

myCycle xs = ys where ys = foldr (:) ys xs

or (arriving at the same result)

myCycle xs = foldr (:) (myCycle xs) xs


I find that "where" rewrites are easier to comprehend for me, more often than
not. :)

Cheers,


Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Bas van Dijk-2
On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <[hidden email]> wrote:
> which is then just rewritable as:
>
> myCycle xs = ys where ys = foldr (:) ys xs
>
> or (arriving at the same result)
>
> myCycle xs = foldr (:) (myCycle xs) xs

Note that, because 'ys' only has to be calculated once, GHC makes the
most efficient code for the former one. In the latter 'myCycle xs' has
to be calculated each time 'xs' runs empty.

Here are some efficiency tests:

(All programs are compiled with GHC with -O2. I excluded the first run
of each program because of possible initialisation overhead.)

------------------------------------------------------------
module Main where

import System.Environment (getArgs)

myCycle1 xs = ys where ys = foldr (:) ys xs
myCycle2 xs = foldr (:) (myCycle2 xs) xs
myCycle3 xs = ys where ys = xs ++ ys

main = do ns:ms:_ <- getArgs
          print $ sum $ take (read ns) (myCycle1 [1..read ms])

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle1 30000000 1000; done;
15015000000

real 0m4.854s
user 0m4.801s
sys 0m0.017s
15015000000

real 0m3.921s
user 0m3.870s
sys 0m0.016s
15015000000

real 0m3.861s
user 0m3.806s
sys 0m0.023s
15015000000

real 0m3.857s
user 0m3.806s
sys 0m0.018s
15015000000

real 0m4.382s
user 0m4.331s
sys 0m0.022s
15015000000

real 0m3.976s
user 0m3.923s
sys 0m0.020s

(3.870 + 3.806 + 3.806 + 4.331 + 3.923) / 5 = 3.9471999999999996

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle2 30000000 1000; done;
15015000000

real 0m4.675s
user 0m4.629s
sys 0m0.016s
15015000000

real 0m5.076s
user 0m5.024s
sys 0m0.022s
15015000000

real 0m4.735s
user 0m4.687s
sys 0m0.015s
15015000000

real 0m4.727s
user 0m4.676s
sys 0m0.021s
15015000000

real 0m4.677s
user 0m4.632s
sys 0m0.018s
15015000000

real 0m5.023s
user 0m4.971s
sys 0m0.016s

(5.024 + 4.687 + 4.676 + 4.632 + 4.971) / 5 = 4.798

------------------------------------------------------------
$ for i in 1 2 3 4 5 6; do time ./cycle3 30000000 1000; done;
15015000000

real 0m4.150s
user 0m4.102s
sys 0m0.018s
15015000000

real 0m3.823s
user 0m3.784s
sys 0m0.014s
15015000000

real 0m4.918s
user 0m4.863s
sys 0m0.021s
15015000000

real 0m3.807s
user 0m3.769s
sys 0m0.015s
15015000000

real 0m4.129s
user 0m4.082s
sys 0m0.016s
15015000000

real 0m4.420s
user 0m4.366s
sys 0m0.021s

(3.784 + 4.863 + 3.769 + 4.082 + 4.366) / 5 = 4.1728000000000005

------------------------------------------------------------

Summary:

cycle1: 3.94
cycle2: 4.79
cycle3: 4.17

regards,

Bas
Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Daniel Fischer-4
Am Sonntag, 15. M?rz 2009 22:14 schrieb Bas van Dijk:

> On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <[hidden email]> wrote:
> > which is then just rewritable as:
> >
> > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > or (arriving at the same result)
> >
> > myCycle xs = foldr (:) (myCycle xs) xs
>
> Note that, because 'ys' only has to be calculated once, GHC makes the
> most efficient code for the former one. In the latter 'myCycle xs' has
> to be calculated each time 'xs' runs empty.
>
> Here are some efficiency tests:
>
> (All programs are compiled with GHC with -O2. I excluded the first run
> of each program because of possible initialisation overhead.)
>
> ------------------------------------------------------------
> module Main where
>
> import System.Environment (getArgs)
>
> myCycle1 xs = ys where ys = foldr (:) ys xs
> myCycle2 xs = foldr (:) (myCycle2 xs) xs
> myCycle3 xs = ys where ys = xs ++ ys
>
> main = do ns:ms:_ <- getArgs
>           print $ sum $ take (read ns) (myCycle1 [1..read ms])
>
> ------------------------------------------------------------
> Summary:
>
> cycle1: 3.94
> cycle2: 4.79
> cycle3: 4.17
>
> regards,
>
> Bas
Somewhat more stable timings on my box. Since it's slower, I did only take
10000000 instead of 30000000:
myCycle1: myCycle1 xs = ys where ys = foldr (:) ys xs
5005000000

real    0m2.972s
user    0m2.920s
sys     0m0.000s
5005000000

real    0m2.978s
user    0m2.920s
sys     0m0.010s
5005000000

real    0m2.952s
user    0m2.890s
sys     0m0.010s
5005000000

real    0m2.968s
user    0m2.910s
sys     0m0.010s
5005000000

real    0m2.997s
user    0m2.940s
sys     0m0.010s
5005000000

real    0m2.944s
user    0m2.890s
sys     0m0.000s
myCycle2: myCycle2 xs = foldr (:) (myCycle2 xs) xs
5005000000

real    0m4.267s
user    0m4.220s
sys     0m0.000s
5005000000

real    0m4.320s
user    0m4.220s
sys     0m0.000s
5005000000

real    0m4.227s
user    0m4.160s
sys     0m0.020s
5005000000

real    0m4.194s
user    0m4.130s
sys     0m0.010s
5005000000

real    0m4.297s
user    0m4.190s
sys     0m0.010s
5005000000

real    0m4.229s
user    0m4.180s
sys     0m0.000s
myCycle3: myCycle3 xs = ys where ys = xs ++ ys
5005000000

real    0m2.974s
user    0m2.900s
sys     0m0.020s
5005000000

real    0m2.954s
user    0m2.900s
sys     0m0.010s
5005000000

real    0m2.950s
user    0m2.900s
sys     0m0.000s
5005000000

real    0m2.959s
user    0m2.890s
sys     0m0.020s
5005000000

real    0m2.973s
user    0m2.910s
sys     0m0.010s
5005000000

real    0m2.965s
user    0m2.890s
sys     0m0.000s

Summary:
myCycle1: 2.9116s
myCycle2: 4.1833s
myCycle3: 2.8983s
Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

7stud-2
In reply to this post by Daniel Fischer-4
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> Let us rewrite the definition a little (looking only at the case for
> nonempty lists):
>
> Variant 1:
> myCycle xs = foldr leftAdd [] [1 .. ]
>    where
>       leftAdd _ acc = xs ++ acc
>
> foldr leftAdd [] [1 .. ]
>    ~> leftAdd 1 (foldr leftAdd [] [2 .. ])
>    ~> xs ++ (foldr leftAdd [] [2 .. ])
>    ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
>    ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
>    ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
>
> Variant 2:
> myCycle xs = foldr rightAdd [] [1 .. ]
>    where
>       rightAdd _ acc = acc ++ xs
>
> foldr rightAdd [] [1 .. ]
>    ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
>    ~> (foldr rightAdd [] [2 .. ]) ++ xs
>    ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
>    ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
>    ~> (((... ++ xs) ++ xs) ++ xs
>

Thanks for the explanation.  After reading your post, I practiced writing
a few foldr's out by hand.  It really helped me to understand what foldr
was doing.  The part that initially confused me was the step in the third
line:

> foldr rightAdd [] [1 .. ]
>    ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
>    ~> (foldr rightAdd [] [2 .. ]) ++ xs

In case any other beginner reads this thread and is confused by  
that, here's what's going on.  In RWH foldr is defined on p. 94
like this:

foldr step zero (x:xs) = step x (foldr step zero xs)

Daniel Fischer's example is calling foldr like this:

foldr rightAdd [] [1 .. ]

matching the foldr definition to that foldr function call:

foldr step zero (x:xs)
foldr rightAdd [] [1 .. ]

you can see that step is the function rightAdd, zero's value is [],
x = 1, and xs = [2..].  Therefore, from the definition of foldr:

foldr rightAdd [] [1..] = rightAdd 1 (foldr rightAdd [] [2..])

The right hand side of that equation is a function call to
rightAdd.  It specifies two arguments: the first argument
is 1, and the second argument is the expression in the
parentheses.  Now, look at the definition of rightAdd:

> rightAdd _ acc = acc ++ xs

rightAdd is a function that ignores its first argument,
then concatenates xs to the right side of its second
argument.  Applying that to this function call:  

rightAdd 1 (foldr rightAdd [] [2..])

rightAdd ignores the first argument, the 1, and
concatenates xs to the right side of its second
argument, which in this case is the expression
in parentheses, so you get:

(foldr rightAdd [] [2..]) ++ xs

Therefore:

rightAdd 1 (foldr rightAdd [] [2..]) =
(foldr rightAdd [] [2..]) ++ xs

Then it's just a matter of expanding the expression
in the parentheses a few more times until you understand
what the pattern is.


> Let us rewrite it a little more.
> Obviously, it doesn't matter which list is passed into
> foldr leftAdd []
> , as long as it's infinite. So instead of passing [1 .. ], let us pass a
> simpler infinite list, say
> ones = 1:ones
> (or ones = repeat 1).
> Then the evaluation becomes
>
> foldr leftAdd [] ones
>    ~> foldr leftAdd [] (1:ones)
>    ~> leftAdd 1 (foldr leftAdd [] ones)
>    ~> xs ++ (foldr leftAdd [] ones)
>
> foldr rightAdd [] ones
>    ~> foldr rightAdd [] (1:ones)
>    ~> rightAdd 1 (foldr rightAdd [] ones)
>    ~> (foldr rightAdd [] ones) ++ xs
>
> So variant 1 amounts to
> myCycle xs = let ys = xs ++ ys in ys
> and variant 2 to
> myCycle2 xs = let ys = ys ++ xs in ys
>
> Now it should be easy to see why the first works, but not the second.
>

No.  I could tell from the example at the beginning of your post
that there was an infinite expression on the front of the result list, but
I can't see that in those equations. What am I failing to recognize there?
 
> And from the rewriting, we can read off another representation of
> cycle  a  fold.
> We have, for all lists ks, ms:
> ks ++ ms = foldr (:) ms ks
>
> So we can write variant 1 as the snappy
>
> myCycle xs = let ys = foldr (:) ys xs in ys
>

I can't understand that one.  I'll have to write it out:

definition of foldr so I can refer to it:
foldr step zero (x:xs) = step x (foldr step zero xs)

myCycle2 [1, 2] =>
ys = foldr (:) ys [1, 2]
---------------
Here's the left hand side of the foldr definition:
foldr step zero (x:xs)  =>match these parameters to the args in the call:
foldr   (:)    ys  [1, 2] =

Now writing out what's on the right hand side of the equals sign in the foldr
definition using the args from the line above:
= (:) 1 (foldr (:) ys 2:[])
= 1:(foldr (:) ys 2:[])
Expand the term in the parentheses:
= 1:( (:) 2 (foldr (:) ys []) )
= 1:( 2:(foldr (:) ys []) )
= 1:2:(foldr (:) ys [])
= 1:2:(ys)
= 1:2:ys

But ys is defined to be:

foldr (:) ys [1, 2]

So substituting into the last line:

= 1:2:(foldr (:) ys [1, 2])
= 1:2:( (:) 1 (foldr (:) ys 2:[])
= 1:2:(1:(foldr (:) ys 2:[])
= 1:2:1:( (:) 2 (foldr (:) ys [])
= 1:2:1:( 2:(foldr (:) ys [])
= 1:2:1:2:(foldr (:) ys [])
= 1:2:1:2:(ys)
= 1:2:1:2:ys

But ys is defined to be:

foldr (:) ys [1, 2]

Therefore, that process goes on and on ad infinitum.  Pretty slick.

I guess haskell thunks the whole infinite expression, therefore
the let expression:

let ys = ....
in ys

doesn't cause an infinite loop in the ys = ... line, which means
the second line executes, which means ys is returned as the
result of the function call myCycle2 [1,2]?






   





Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Daniel Fischer-4
Am Dienstag, 17. M?rz 2009 02:24 schrieb 7stud:

> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Let us rewrite the definition a little (looking only at the case for
> > nonempty lists):
> >
> > Variant 1:
> > myCycle xs = foldr leftAdd [] [1 .. ]
> >    where
> >       leftAdd _ acc = xs ++ acc
> >
> > foldr leftAdd [] [1 .. ]
> >    ~> leftAdd 1 (foldr leftAdd [] [2 .. ])
> >    ~> xs ++ (foldr leftAdd [] [2 .. ])
> >    ~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
> >    ~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
> >    ~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
> >
> > Variant 2:
> > myCycle xs = foldr rightAdd [] [1 .. ]
> >    where
> >       rightAdd _ acc = acc ++ xs
> >
> > foldr rightAdd [] [1 .. ]
> >    ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> >    ~> (foldr rightAdd [] [2 .. ]) ++ xs
> >    ~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
> >    ~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
> >    ~> (((... ++ xs) ++ xs) ++ xs
>
> Thanks for the explanation.  After reading your post, I practiced writing
> a few foldr's out by hand.  It really helped me to understand what foldr
> was doing.  The part that initially confused me was the step in the third
>
> line:
> > foldr rightAdd [] [1 .. ]
> >    ~> rightAdd 1 (foldr rightAdd [] [2 .. ])
> >    ~> (foldr rightAdd [] [2 .. ]) ++ xs
>

Sorry. I was too lazy to write out the intermediate step. However, since that
resulted in you doing it manually and so getting more familiar with foldr, it
had a good effect :)

> In case any other beginner reads this thread and is confused by
> that, here's what's going on.  In RWH foldr is defined on p. 94
> like this:
>
> foldr step zero (x:xs) = step x (foldr step zero xs)
>
> Daniel Fischer's example is calling foldr like this:
>
> foldr rightAdd [] [1 .. ]
>
> matching the foldr definition to that foldr function call:
>
> foldr step zero (x:xs)
> foldr rightAdd [] [1 .. ]
>
> you can see that step is the function rightAdd, zero's value is [],
> x = 1, and xs = [2..].  Therefore, from the definition of foldr:
>
> foldr rightAdd [] [1..] = rightAdd 1 (foldr rightAdd [] [2..])
>
> The right hand side of that equation is a function call to
> rightAdd.  It specifies two arguments: the first argument
> is 1, and the second argument is the expression in the
>
> parentheses.  Now, look at the definition of rightAdd:
> > rightAdd _ acc = acc ++ xs
>
> rightAdd is a function that ignores its first argument,
> then concatenates xs to the right side of its second
> argument.  Applying that to this function call:
>
> rightAdd 1 (foldr rightAdd [] [2..])
>
> rightAdd ignores the first argument, the 1, and
> concatenates xs to the right side of its second
> argument, which in this case is the expression
> in parentheses, so you get:
>
> (foldr rightAdd [] [2..]) ++ xs
>
> Therefore:
>
> rightAdd 1 (foldr rightAdd [] [2..]) =
> (foldr rightAdd [] [2..]) ++ xs
>
> Then it's just a matter of expanding the expression
> in the parentheses a few more times until you understand
> what the pattern is.
>
> > Let us rewrite it a little more.
> > Obviously, it doesn't matter which list is passed into
> > foldr leftAdd []
> > , as long as it's infinite. So instead of passing [1 .. ], let us pass a
> > simpler infinite list, say
> > ones = 1:ones
> > (or ones = repeat 1).
> > Then the evaluation becomes
> >
> > foldr leftAdd [] ones
> >    ~> foldr leftAdd [] (1:ones)
> >    ~> leftAdd 1 (foldr leftAdd [] ones)
> >    ~> xs ++ (foldr leftAdd [] ones)
> >
> > foldr rightAdd [] ones
> >    ~> foldr rightAdd [] (1:ones)
> >    ~> rightAdd 1 (foldr rightAdd [] ones)
> >    ~> (foldr rightAdd [] ones) ++ xs
> >
> > So variant 1 amounts to
> > myCycle xs = let ys = xs ++ ys in ys
> > and variant 2 to
> > myCycle2 xs = let ys = ys ++ xs in ys
> >
> > Now it should be easy to see why the first works, but not the second.
>
> No.  I could tell from the example at the beginning of your post
> that there was an infinite expression on the front of the result list, but
> I can't see that in those equations. What am I failing to recognize there?

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]) is basically the same as a definition

ys = ys ++ [1,2,3]

at top level.
Now to find out what ys is, we look at the right hand side of its definition,
ys ++ [1,2,3]
, good, so we have a concatenation of someList with [1,2,3], the first part of
ys is then someList. To determine ys, we must therefore first determine
someList. So, what is someList? someList = ys, so to determine the first part
of ys, we must find the whole of ys first -- oops, infinite recursion.

>
> > And from the rewriting, we can read off another representation of
> > cycle  a  fold.
> > We have, for all lists ks, ms:
> > ks ++ ms = foldr (:) ms ks
> >
> > So we can write variant 1 as the snappy
> >
> > myCycle xs = let ys = foldr (:) ys xs in ys
>
> I can't understand that one.  I'll have to write it out:
>
> definition of foldr so I can refer to it:
> foldr step zero (x:xs) = step x (foldr step zero xs)
>
> myCycle2 [1, 2] =>
> ys = foldr (:) ys [1, 2]
> ---------------
> Here's the left hand side of the foldr definition:
> foldr step zero (x:xs)  =>match these parameters to the args in the call:
> foldr   (:)    ys  [1, 2] =
>
> Now writing out what's on the right hand side of the equals sign in the
> foldr definition using the args from the line above:
> = (:) 1 (foldr (:) ys 2:[])
> = 1:(foldr (:) ys 2:[])
> Expand the term in the parentheses:
> = 1:( (:) 2 (foldr (:) ys []) )
> = 1:( 2:(foldr (:) ys []) )
> = 1:2:(foldr (:) ys [])
> = 1:2:(ys)
> = 1:2:ys
>
> But ys is defined to be:
>
> foldr (:) ys [1, 2]

Actually, the implementation shouldn't need to go back to that definition at
this stage, it should now have reduced the thunk to
ys = 1:2:ys
, hopefully even by constructing a true cyclic list, making the ys on the
right hand side a pointer to the front of the list.

>
> So substituting into the last line:
>
> = 1:2:(foldr (:) ys [1, 2])
> = 1:2:( (:) 1 (foldr (:) ys 2:[])
> = 1:2:(1:(foldr (:) ys 2:[])
> = 1:2:1:( (:) 2 (foldr (:) ys [])
> = 1:2:1:( 2:(foldr (:) ys [])
> = 1:2:1:2:(foldr (:) ys [])
> = 1:2:1:2:(ys)
> = 1:2:1:2:ys
>
> But ys is defined to be:
>
> foldr (:) ys [1, 2]
>
> Therefore, that process goes on and on ad infinitum.  Pretty slick.
>
> I guess haskell thunks the whole infinite expression, therefore
> the let expression:
>
> let ys = ....
> in ys
>
> doesn't cause an infinite loop in the ys = ... line, which means
> the second line executes, which means ys is returned as the
> result of the function call myCycle2 [1,2]?
>
>

Yes, it's thunked. It works because we can now determine the start of ys
without knowing anything about ys (provided that xs is nonempty). The result
of myCycle2 [1,2] is the thunk that says how to evaluate it. We give a name
to the result to be able to reference it in the calculation.

Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

7stud-2
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?
Well, ys is equal to ys ++ [1, 2, 3].  So substituting
the value ys ++ [1, 2, 3] for ys in the right hand side
of the last line gives:

ys = (ys ++ [1, 2, 3]) ++ [1, 2, 3]
 
and then you need to substitute the value for ys
again on the right hand side, and so on ad infinitum.
That's bad because as in the earlier foldr example
ys is an infinite expression on the front of the list, and
any operation on the list will cause haskell to try and evaluate
that infinite expression.


> > myCycle2 [1, 2] =>
> > ys = foldr (:) ys [1, 2]
> > ---------------
> > Here's the left hand side of the foldr definition:
> > foldr step zero (x:xs)  =>match these parameters to the args in the call:
> > foldr   (:)    ys  [1, 2] =
> >
> > Now writing out what's on the right hand side of the equals sign in the
> > foldr definition using the args from the line above:
> > = (:) 1 (foldr (:) ys 2:[])
> > = 1:(foldr (:) ys 2:[])
> > Expand the term in the parentheses:
> > = 1:( (:) 2 (foldr (:) ys []) )
> > = 1:( 2:(foldr (:) ys []) )
> > = 1:2:(foldr (:) ys [])
> > = 1:2:(ys)
> > = 1:2:ys
> >
> > But ys is defined to be:
> >
> > foldr (:) ys [1, 2]
>
> Actually, the implementation shouldn't need to go back to that definition at
> this stage, it should now have reduced the thunk to
> ys = 1:2:ys
>

I figured haskell thunked the expression earlier than my last expansion:

>= 1:2:(foldr (:) ys [1, 2])
>= 1:2:( (:) 1 (foldr (:) ys 2:[])
>= 1:2:(1:(foldr (:) ys 2:[])
>= 1:2:1:( (:) 2 (foldr (:) ys [])
>= 1:2:1:( 2:(foldr (:) ys [])
>= 1:2:1:2:(foldr (:) ys [])
>= 1:2:1:2:(ys)
>= 1:2:1:2:ys


but I wanted to keep expanding the expression to show that it was creating
an infinite cycle.

> , hopefully even by constructing a true cyclic list, making the ys on the
> right hand side a pointer to the front of the list.
> >

Ok.

> > I guess haskell thunks the whole infinite expression, therefore
> > the let expression:
> >
> > let ys = ....
> > in ys
> >
> > doesn't cause an infinite loop in the ys = ... line, which means
> > the second line executes, which means ys is returned as the
> > result of the function call myCycle2 [1,2]?
> >
> >
>
> Yes, it's thunked. It works because we can now determine the start of ys
> without knowing anything about ys (provided that xs is nonempty). The result
> of myCycle2 [1,2] is the thunk that says how to evaluate it. We give a name
> to the result to be able to reference it in the calculation.
>

Thanks again for the great explanations.




Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
In reply to this post by Bas van Dijk-2
Bas van Dijk <v.dijk.bas <at> gmail.com> writes:

>
> On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com> wrote:
> > which is then just rewritable as:
> >
> > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > or (arriving at the same result)
> >
> > myCycle xs = foldr (:) (myCycle xs) xs
>
> Note that, because 'ys' only has to be calculated once, GHC makes the
> most efficient code for the former one. In the latter 'myCycle xs' has
> to be calculated each time 'xs' runs empty.
>
> Here are some efficiency tests:
>
> myCycle1 xs = ys where ys = foldr (:) ys xs
> myCycle2 xs = foldr (:) (myCycle2 xs) xs
> myCycle3 xs = ys where ys = xs ++ ys
>
> main = do ns:ms:_ <- getArgs
>           print $ sum $ take (read ns) (myCycle1 [1..read ms])
>

So you've discovered an inefficiency in GHC, which should probably improve on
its deforestation skills. :)

"Smart" compiler would NOT allocate any extra storage in the three cases above,
only altering the access to it. The meaning of all the three is the same - they
are all rewritable one into another - it's a loop around on access past end.

The "very bright" compiler would just translate

sum $ take 30000000 [1..1000]

into

sum [1..1000]*30000

producing the same result:

Prelude> sum [1..1000]*30000
15015000000


Cheers,


Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
In reply to this post by Bas van Dijk-2
Bas van Dijk <v.dijk.bas <at> gmail.com> writes:

>
> On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com> wrote:
> > which is then just rewritable as:
> >
> > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > or (arriving at the same result)
> >
> > myCycle xs = foldr (:) (myCycle xs) xs
>
> Note that, because 'ys' only has to be calculated once, GHC makes the
> most efficient code for the former one. In the latter 'myCycle xs' has
> to be calculated each time 'xs' runs empty.
>

Actually my point was, that

" I find that "where" rewrites are easier to comprehend for me,
  more often than not. :) "

"  myCycle xs = ys where ys = foldr (:) ys xs "

which should be exactly as the one with the let.



Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
In reply to this post by 7stud-2
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.



Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Daniel Fischer-4
In reply to this post by Will Ness-2
Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness:
> Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
wrote:

> > > which is then just rewritable as:
> > >
> > > myCycle xs = ys where ys = foldr (:) ys xs
> > >
> > > or (arriving at the same result)
> > >
> > > myCycle xs = foldr (:) (myCycle xs) xs
> >
> > Note that, because 'ys' only has to be calculated once, GHC makes the
> > most efficient code for the former one. In the latter 'myCycle xs' has
> > to be calculated each time 'xs' runs empty.
>
> Actually my point was, that
>
> " I find that "where" rewrites are easier to comprehend for me,
>   more often than not. :) "

Of course a matter of personal preference, but I tend to prefer where clauses,
too, in general. However, my preferred layout is

some code
      where
        local declarations

I deeply loathe not having the where on a separate line :-/

>
> "  myCycle xs = ys where ys = foldr (:) ys xs "
>
> which should be exactly as the one with the let.
>
AFAIK,

myCycle1 [] = []
myCycle1 xs = let ys = foldr (:) ys xs in ys

and

myCycle2 [] = []
myCycle2 xs = ys
      where
        ys = foldr (:) ys xs

are compiled to exactly the same code. In GHC, I think the first thing that
happens to myCycle2 is that it's rewritten to myCycle1.

What matters if whether you give a name to the result to get it shared or not.

Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

>
> Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness:
> > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> wrote:
> > > >
> > > > myCycle xs = ys where ys = foldr (:) ys xs

> Of course a matter of personal preference, but I tend to prefer where
> clauses, too, in general. However, my preferred layout is
>
> some code
>       where
>         local declarations
>
> I deeply loathe not having the where on a separate line :-/


Will try not to offend in the future. :)

> AFAIK,
>
> [let and where versions of myCycle] are compiled to exactly the same code.

since there are no guards there with shared variables, I guess.

> What matters is whether you give a name to the result to get it shared or not.

I was hoping GHC is smarter than that in finding shared expressions. Is it
what's called deforestation?

Also, one can imagine this rewrite to be arrived at automagically by a compiler:

sum $ take m $ cycle [1..k]
  | n > 0  = x*n+y
  where
     (n,r) = quotRem m k
     x     = sum [1..k]
     y     = sum [1..r]

Any human is certainly capable of seen this almost immediately, presented with
the big k's and huge m's. It's automagical. :)

Cheers,


Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Daniel Fischer-4
Am Mittwoch, 18. M?rz 2009 16:14 schrieb Will Ness:

> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness:
> > > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> >
> > wrote:
> > > > > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > Of course a matter of personal preference, but I tend to prefer where
> > clauses, too, in general. However, my preferred layout is
> >
> > some code
> >       where
> >         local declarations
> >
> > I deeply loathe not having the where on a separate line :-/
>
> Will try not to offend in the future. :)

Very kind of you. But stick to your own style, I can live with loathing the
layout of some code :-)

>
> > AFAIK,
> >
> > [let and where versions of myCycle] are compiled to exactly the same
> > code.
>
> since there are no guards there with shared variables, I guess.

No, that doesn't matter. GHC-core has no where, only let, so all where clauses
must be rewritten to use let.

>
> > What matters is whether you give a name to the result to get it shared or
> > not.
>
> I was hoping GHC is smarter than that in finding shared expressions. Is it
> what's called deforestation?

Sorry, don't know about that, but I think not,
common-subexpression-elimination sounds more like it. But I'm guessing here.

>
> Also, one can imagine this rewrite to be arrived at automagically by a
> compiler:
>
> sum $ take m $ cycle [1..k]
>
>   | n > 0  = x*n+y
>
>   where
>      (n,r) = quotRem m k
>      x     = sum [1..k]
>      y     = sum [1..r]
>
> Any human is certainly capable of seen this almost immediately, presented
> with the big k's and huge m's. It's automagical. :)

But it's too much of a special case to have a special rule for it in the
compiler code.
Humans are much less principled and can thus spot a greater variety of
patterns (but they are also better in overlooking such patterns).

>
> Cheers,
>

Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

>
> Am Mittwoch, 18. M?rz 2009 16:14 schrieb Will Ness:
> > Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > > Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness:
> > > > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> > >
> > > wrote:
> > > > > > myCycle xs = ys where ys = foldr (:) ys xs
> > >
> > > AFAIK,
> > >
> > > [let and where versions of myCycle] are compiled to exactly the same
> > > code.
> >
> > since there are no guards there with shared variables, I guess.
>
> No, that doesn't matter. GHC-core has no where, only let, so all where
clauses
> must be rewritten to use let.


So it must be a more extensive re-write then, for guards, with explicit (case
test of True -> ) etc... :)

> > Also, one can imagine this rewrite to be arrived at automagically by a
> > compiler:
> >
> > sum $ take m $ cycle [1..k]
> >
> >   | n > 0  = x*n+y
> >
> >   where
> >      (n,r) = quotRem m k
> >      x     = sum [1..k]
> >      y     = sum [1..r]
> >
> > Any human is certainly capable of seen this almost immediately, presented
> > with the big k's and huge m's. It's automagical. :)
>
> But it's too much of a special case to have a special rule for it in the
> compiler code.

What I was driving at, is having a compiler so smart it'd figure this out on
its own, if needed (i.e. faced with huge m's), not having this specific special
case programmed by a compiler-writer.

> Humans are much less principled and can thus spot a greater variety of
> patterns (but they are also better in overlooking such patterns).

I think it is because we're constantly trying out, unconsciously, various ways
to achieve our goals. It's like a forward-chaining churning in the background,
providing us with currently-known-possibilities sphere, like a cloud of
possibilities around us. Touch the goal with the sphere's surface and - boom! -
we've got ourselves an intuitive solution that's "just there".

Sometimes I think precompilation - pre-evaluation - is the essence of human
creativity. We just invent things in advance, in case we'd ever need them. Same
with dreams. It's just a training engine for us to learn how to run away from a
tiger better, or how to better kill a mammoth. :)

I think it's called speculative eager evaluation.

Cheers,


Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
In reply to this post by Daniel Fischer-4
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

>
> Am Mittwoch, 18. Maerz 2009 16:14 schrieb Will Ness:
> >
> > sum $ take m $ cycle [1..k]
> >   | n > 0  = x*n+y
> >   where
> >      (n,r) = quotRem m k
> >      x     = sum [1..k]
> >      y     = sum [1..r]

In fact, the super-brilliant deducting compiler would make it

sum $ take m $ cycle [1..k]
   | n > 0  = x*n+y
   where
      (n,r) = quotRem m k
      x     = k*(k+1)/2
      y     = r*(r+1)/2

:) :)

Now THAT would be a deductive power to behold!


Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

7stud-2
In reply to this post by Will Ness-2
Will Ness <will_n48 <at> yahoo.com> writes:

> In our case, having
> 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
>

I'm confused by your statement that ws is getting matched against the
(a:as) pattern in the foldr definition, and therefore it is immediately
evaluated.   I didn't think the let expression:

> let ws = foldr (:) [1,2,3] ws

would cause infinite looping.

Wouldn't it be the head pattern that is being matched, and therefore head
triggers the evaluation?  Although, I'm not seeing a pattern match here:

>head (x:xs) = x
>head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))


..
...
...
..
..
,,,
...
....




Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Daniel Fischer-4
Am Donnerstag, 19. M?rz 2009 20:32 schrieb 7stud:

> Will Ness <will_n48 <at> yahoo.com> writes:
> > In our case, having
> > 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
>
> I'm confused by your statement that ws is getting matched against the
> (a:as) pattern in the foldr definition, and therefore it is immediately
>
> evaluated.   I didn't think the let expression:
> > let ws = foldr (:) [1,2,3] ws
>
> would cause infinite looping.

Note this is again the left recursive bad definition. As long as we don't want
to know anything about ws, the definition

ws = foldr (:) [1,2,3] ws

sleeps peacefully.

>
> Wouldn't it be the head pattern that is being matched, and therefore head
>
> triggers the evaluation?

If we need to know about the structure of ws, for example if we query

head ws

the evaluation of ws is triggered. In the case of head, we want to know if ws
matches the pattern (_:_), in which case head returns the head of ws, or not,
in which case head throws an exception.

So the implementation tries to match ws with the pattern (_:_). To see if it
matches, it must evaluate ws, first replacing ws by the right hand side of
its definition, foldr (:) [1,2,3] ws. Doesn't yet say if ws matches (_:_), so
the foldr must be evaluated.

foldr (:) [1,2,3] [] ~> [1,2,3]
foldr (:) [1,2,3] (y:ys) = y:foldr (:) [1,2,3] ys

To know which equation to use, the implementation tries to match ws with [].
Unfortunately, there is no information about the structure of ws available
yet. So ws is replaced by the right hand side of its definition to find out
whether it matches [], leading to

head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)).

Dang, to see whether the inner foldr returns an empty list or not, we need to
know whether ws is empty or not, so we must replace ws in the inner foldr
with the right hand side of its definition...

>  Although, I'm not seeing a pattern match here:
> >head (x:xs) = x
         ^^^^^^ the pattern
> >head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
the expression which is matched against the pattern

Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

7stud-2
Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> Am Donnerstag, 19. M?rz 2009 20:32 schrieb 7stud:
> > Will Ness <will_n48 <at> yahoo.com> writes:
> > > 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
> >
> > I'm confused by your statement that ws is getting matched against the
> > (a:as) pattern in the foldr definition, and therefore it is immediately
> >
> > evaluated.   I didn't think the let expression:
> > > let ws = foldr (:) [1,2,3] ws
> >
> > would cause infinite looping.
>
> Note this is again the left recursive bad definition. As long as we don't want
> to know anything about ws, the definition
>
> ws = foldr (:) [1,2,3] ws
>
> sleeps peacefully.
>

Check...................................................
..............................................................
............................................................
.............................................................
 

> > Wouldn't it be the head pattern that is being matched, and therefore head
> >
> > triggers the evaluation?
>
> If we need to know about the structure of ws, for example if we query
>
> head ws
>
> the evaluation of ws is triggered. In the case of head, we want to know if ws
> matches the pattern (_:_), in which case head returns the head of ws, or not,
> in which case head throws an exception.
>
> So the implementation tries to match ws with the pattern (_:_). To see if it
> matches, it must evaluate ws, first replacing ws by the right hand side of
> its definition, foldr (:) [1,2,3] ws. Doesn't yet say if ws matches (_:_), so
> the foldr must be evaluated.
.........................
.........................
.........................
.........................
.........................

  foldr  _    zero  []  =  zero  (from def of foldr)
> foldr (:) [1,2,3] [] ~> [1,2,3]  
> foldr (:) [1,2,3] (y:ys) =   y  :  foldr  (:) [1,2,3] ys
                           =  (:) y (foldr  (:) [1,2,3] ys)
  foldr step  zero  (x:xs) = step x (foldr  step  zero  xs)
                  (from definition of foldr)

...........................
...........................
..........................
..........................
> To know which equation to use, the implementation tries to match ws with [].
> Unfortunately, there is no information about the structure of ws available
> yet. So ws is replaced by the right hand side of its definition to find out
> whether it matches [], leading to
>
> head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)).
>

> Dang, to see whether the inner foldr returns an empty list or not

??

I think you meant to say something like, "to see whether ws is an empty
list and therefore foldr returns [1, 2, 3]:

  foldr (:) [1,2,3] ws
> foldr (:) [1,2,3] [] = [1,2,3]  

we need to know whether ws is empty or not."

> so we must replace ws in the inner foldr
> with the right hand side of its definition...
>
> >  Although, I'm not seeing a pattern match here:
> > >head (x:xs) = x
>          ^^^^^^ the pattern
> > >head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
>             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> the expression which is *trying*(?) to be matched against the pattern
>
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
....
...
...
...
...





Reply | Threaded
Open this post in threaded view
|

Re: folds again -- myCycle

Will Ness-2
7stud <bbxx789_05ss <at> yahoo.com> writes:

>
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Donnerstag, 19. M?rz 2009 20:32 schrieb 7stud:
> > > Will Ness <will_n48 <at> yahoo.com> writes:
> > > > 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
> > >
> > > I'm confused by your statement that ws is getting matched against the
> > > (a:as) pattern in the foldr definition, and therefore it is immediately
> > >
> > > evaluated.   I didn't think the let expression:
> > > > let ws = foldr (:) [1,2,3] ws
> > >
> > > would cause infinite looping.
> >
> > Note this is again the left recursive bad definition. As long as we don't
want
> > to know anything about ws, the definition
> >
> > ws = foldr (:) [1,2,3] ws
> >
> > sleeps peacefully.
> >
..............

> I think you meant to say something like, "to see whether ws is an empty
> list and therefore foldr returns [1, 2, 3]:
>
>   foldr (:) [1,2,3] ws
> > foldr (:) [1,2,3] [] = [1,2,3]  
>
> we need to know whether ws is empty or not."
>
> > so we must replace ws in the inner foldr
> > with the right hand side of its definition...
> >
> > >  Although, I'm not seeing a pattern match here:
> > > >head (x:xs) = x
> >          ^^^^^^ the pattern
> > > >head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
> >             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > the expression which is *trying*(?) to be matched against the pattern
> >


I'll try again, please follow me here.
We have these defintions:


head (x:xs) = x

foldr f z (a:as) = a `f` foldr f z as
foldr f z  []    = z


First, the WRONG DEFINITION:

zls = [1,2,3]
ws = foldr (:) zls ws


Why is it wrong?

In Haskell, evaluation is pattern-matching. When the left hand side matches,
right hand side IS the answer. That's one step, which gets repeated until we
hit some primitive which stops this process.

After loading these definitions, if we were to ask the top-level the value of
(head ws), what would happen?

The system tries to _reduce_ (head ws) ..... look! we have the definition {
head (x:xs)=x } , it says to itself.

OK, does its LHS (left hand side) match our expression?

-----
head ws
head (x:xs)
-----

Now the system looks to see whether { ws ?= (x:xs) } can be matched. That means
checking whether ws is a non-empty list. So the attempt to match 'ws' TRIGGERS
the attempt to find out its value, to "reduce" its definition.

Now, we have defined it as

ws = foldr (:) zls ws

Look! we have a definition for 'foldr' with LHS { foldr f z (a:as) }. Does it
match our definition, the system asks itself?

-----
foldr (:) zls ws
foldr f z (a:as)
-----

OK, f is (:), z is zls. No problem. WHAT ABOUT { ws ?= (a:as) } ? OOPS, we try
to see what's ws's value in order to find out its value. INFINITE LOOP!

Not because of any language feature, but because our definition defines itself
immediately as itself. That's LEFT recursion. The good, RIGHT recursion, has
some intervening case first, so that it'll make sense.

Like, what is a natural number? "It's a number!" would be WRONG, LEFT RECURSIVE
definition. But saying "It's either 1, or a successor of a natural number" is
OK, because we have the terminal clause first ( which gives us an immediate
answer, 1).

So now, THE RIGHT DEFINITION:

zls = [1,2,3]
ws = foldr (:) ws zls

Here, (head ws) _causes_ the system to check { ws ?= (x:xs) }, so again, its
definition is looked into. It's defined in terms of foldr:

foldr (:) ws zls   -- our definition for 'w'
foldr f z (a:as) -- LHS of 'foldr' definiton

Do  they match? Asks the system.

OK, f is (:), z is ws. No problem, both are variables, so we don't need to look
inside _their_ values just yet, nothing's forcing us to do that just yet.

OK, so what's left is { zls ?= (a:as) }. Aha! No problem again, BECAUSE zls is
KNOWN at this point already. So  that's OK.

Why the two definitions were different?

ws = foldr (:) zls ws
ws = foldr (:) ws zls

Because, foldr is "forcing" in its last argument. Why? Because its definition
is { foldr f z (a:as) = ... } so it TRIES TO MATCH ITS LAST ARGUMENT, i.e. it
FORCES its value to be found.

So we can't put our value that we're defining, into the forcing position of
FOLDR call, because that would mean that our value is looked into in order to
define its value, BEFORE it is defined. If it were looked into AFTER, there
would be no problem.

Cheers,