# folds again -- myCycle

20 messages
Open this post in threaded view
|

## folds again -- myCycle

 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.
Open this post in threaded view
|

## folds again -- myCycle

Open this post in threaded view
|

## Re: folds again -- myCycle

 Daniel Fischer 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,
Open this post in threaded view
|

## Re: folds again -- myCycle

 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
Open this post in threaded view
|

## Re: folds again -- myCycle

 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
Open this post in threaded view
|

## Re: folds again -- myCycle

Open this post in threaded view
|

## Re: folds again -- myCycle

Open this post in threaded view
|

## Re: folds again -- myCycle

Open this post in threaded view
|

## Re: folds again -- myCycle

 In reply to this post by Bas van Dijk-2 Bas van Dijk gmail.com> writes: > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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,
Open this post in threaded view
|

## Re: folds again -- myCycle

 In reply to this post by Bas van Dijk-2 Bas van Dijk gmail.com> writes: > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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.
Open this post in threaded view
|

## Re: folds again -- myCycle

Open this post in threaded view
|

## Re: folds again -- myCycle

 In reply to this post by Will Ness-2 Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness: > Bas van Dijk gmail.com> writes: > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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.
Open this post in threaded view
|

## Re: folds again -- myCycle

 Daniel Fischer web.de> writes: > > Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness: > > Bas van Dijk gmail.com> writes: > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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,
Open this post in threaded view
|

## Re: folds again -- myCycle

 Am Mittwoch, 18. M?rz 2009 16:14 schrieb Will Ness: > Daniel Fischer web.de> writes: > > Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness: > > > Bas van Dijk gmail.com> writes: > > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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, >
Open this post in threaded view
|

## Re: folds again -- myCycle

 Daniel Fischer web.de> writes: > > Am Mittwoch, 18. M?rz 2009 16:14 schrieb Will Ness: > > Daniel Fischer web.de> writes: > > > Am Mittwoch, 18. M?rz 2009 12:19 schrieb Will Ness: > > > > Bas van Dijk gmail.com> writes: > > > > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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,
Open this post in threaded view
|

## Re: folds again -- myCycle

 In reply to this post by Daniel Fischer-4 Daniel Fischer 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!
Open this post in threaded view
|

## Re: folds again -- myCycle

Open this post in threaded view
|