folds again -- myCycle

7stud

14 Mar 2009 14 Mar '09

3:57 a.m.

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.

Show replies by date

Daniel Fischer

14 Mar 14 Mar

6:47 a.m.

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

Will Ness

15 Mar 15 Mar

2:35 p.m.

Daniel Fischer 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,

Bas van Dijk

5:14 p.m.

On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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

Daniel Fischer

6:30 p.m.

Am Sonntag, 15. März 2009 22:14 schrieb Bas van Dijk:

...

On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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

Will Ness

18 Mar 18 Mar

6:33 a.m.

Bas van Dijk writes:

...

On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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,

Will Ness

7:19 a.m.

Bas van Dijk writes:

...

On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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.

Daniel Fischer

7:45 a.m.

Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:

...

Bas van Dijk writes:

...
On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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.

Will Ness

11:14 a.m.

Daniel Fischer writes:

...

Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:

...
Bas van Dijk writes:

...
On Sun, Mar 15, 2009 at 7:35 PM, Will Ness 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,

Daniel Fischer

12:03 p.m.

Am Mittwoch, 18. März 2009 16:14 schrieb Will Ness:

...

Daniel Fischer writes:

...
Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:

...
Bas van Dijk writes:

...
On Sun, Mar 15, 2009 at 7:35 PM, Will Ness

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,

Will Ness

2 p.m.

Daniel Fischer writes:

...

Am Mittwoch, 18. März 2009 16:14 schrieb Will Ness:

...
Daniel Fischer writes:

...
Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:

...
Bas van Dijk writes:

...
On Sun, Mar 15, 2009 at 7:35 PM, Will Ness

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,

Will Ness

2:43 p.m.

Daniel Fischer 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!

7stud

16 Mar 16 Mar

9:24 p.m.

Daniel Fischer 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]?

Daniel Fischer

17 Mar 17 Mar

7:28 a.m.

Am Dienstag, 17. März 2009 02:24 schrieb 7stud:

...

Daniel Fischer 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.

7stud

8:30 a.m.

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? 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.

Will Ness

18 Mar 18 Mar

7:23 a.m.

7stud writes:

...

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.

7stud

19 Mar 19 Mar

3:32 p.m.

Will Ness 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))

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

Daniel Fischer

4:01 p.m.

Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:

...

Will Ness 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?

...

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)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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... the expression which is matched against the pattern

7stud

20 Mar 20 Mar

4:21 a.m.

Daniel Fischer writes:

...

Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:

...
Will Ness 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...

...
...
head (x:xs) = x ^^^^^^ the pattern head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Although, I'm not seeing a pattern match here: the expression which is *trying*(?) to be matched against the pattern

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ...

Will Ness

24 Mar 24 Mar

4:21 p.m.

7stud writes:

...

Daniel Fischer writes:

...
Am Donnerstag, 19. März 2009 20:32 schrieb 7stud:

...
Will Ness 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...

...
...
head (x:xs) = x ^^^^^^ the pattern head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws)) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Although, I'm not seeing a pattern match here: 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,

5901

Age (days ago)

5911

Last active (days ago)

List overview

Download

19 comments

4 participants

participants (4)

7stud
Bas van Dijk
Daniel Fischer
Will Ness