Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
On 8/20/07, Stefan O'Rear [EMAIL PROTECTED] wrote: ... (I need to find some way to automate making these trails :) ) ... I think you can come a long way with the debugger in GHC HEAD. It provides a :trace command that, when applied to an expression with some breakpoint in it, remembers the history of evaluation steps. You can view the history with :hist. See: http://www.haskell.org/ghc/dist/current/docs/users_guide/ghci-debugger.html#tracing regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
Stefan O'Rear wrote: sum = sum' 0 sum' k [] = k sum' k (x:xs) = (sum' $! (k+x)) xs enum x y | x = y= 0 | otherwise = x : enum (x+1) y sum (enum 1 10) = sum' 0 (enum 1 10) = sum' 0 (1 : enum (1+1) 10) = (sum' $! (0+1)) (enum (1+1) 10) = sum' 1 (enum (1+1) 10) = sum' 1 (2 : enum (2+1) 10) = (sum' $! (1+2)) (enum (2+1) 10) = sum' 3 (enum (2+1) 10) = sum' 3 (3 : enum (3+1) 10) = (sum' $! (3+3)) (enum (3+1) 10) = sum' 6 (enum (3+1) 10) = sum' 6 (4 : enum (4+1) 10) = (sum' $! (6+4)) (enum (4+1) 10) = sum' 10 (enum (4+1) 10) = ... sum' 36 (9 : enum (9+1) 10) = (sum' $! (36+9)) (enum (9+1) 10) = sum' 45 (enum (9+1) 10) = sum' 45 [] = 45 (I need to find some way to automate making these trails :) ) I did have a fairly small Tcl implementation for this... I don't have the code now, and I wrote it early in my Haskell career, so there's masses of stuff it didn't handle. (*cough* type classes) Actually, I've often longed for some tool (maybe even integrated into Lambdabot) to show the reduction sequence of an arbitrary expression. But none exists, AFAIK... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
Not really more efficient but plays to the language implementation's strengths. Imagine take 10 $ foo (10^9) and take 10 $ bar (10^9) bar wouldn't evaluate until the 10^9 was done. (And I just ground my laptop to a halt checking that. :) foo on the other hand would run out to 10^6 and then conveniently finish the rest of your program waiting for the need of the other 10^9-10 values. If you *always* needed the result of the 10^9 calculations then tail-recursion should be better since you won't be holding onto the evaluation frames. -ljr Peter Verswyvelen wrote: Now if I understand this correctly, this just means that when writing something like: foo n = if n0 then [] else n : foo (n-1) bar n = aux 0 [] where aux i xs = if in then xs else aux (i+1) (i:xs) that foo is more efficient than bar because lazy evaluation of foo just puts the delayed computation in the cdr of the list, while lazy evaluation of bar has to keep track of all aux calls (the closures) which gives much more overhead, maybe even stack overflow? Something like that? Thanks, Peter -- Lanny Ripple [EMAIL PROTECTED] ScmDB / Cisco Systems, Inc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
Lanny Ripple wrote: Not really more efficient but plays to the language implementation's strengths. Imagine take 10 $ foo (10^9) and take 10 $ bar (10^9) bar wouldn't evaluate until the 10^9 was done. (And I just ground my laptop to a halt checking that. :) foo on the other hand would run out to 10^6 and then conveniently finish the rest of your program waiting s/10^6/10/ That's what I get for not proof-reading after making a change after the first proof-read. for the need of the other 10^9-10 values. If you *always* needed the result of the 10^9 calculations then tail-recursion should be better since you won't be holding onto the evaluation frames. -ljr Peter Verswyvelen wrote: Now if I understand this correctly, this just means that when writing something like: foo n = if n0 then [] else n : foo (n-1) bar n = aux 0 [] where aux i xs = if in then xs else aux (i+1) (i:xs) that foo is more efficient than bar because lazy evaluation of foo just puts the delayed computation in the cdr of the list, while lazy evaluation of bar has to keep track of all aux calls (the closures) which gives much more overhead, maybe even stack overflow? Something like that? Thanks, Peter -- Lanny Ripple [EMAIL PROTECTED] ScmDB / Cisco Systems, Inc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
On Mon, Aug 20, 2007 at 11:21:01AM -0500, Lanny Ripple wrote: Not really more efficient but plays to the language implementation's strengths. Imagine take 10 $ foo (10^9) and take 10 $ bar (10^9) bar wouldn't evaluate until the 10^9 was done. (And I just ground my laptop to a halt checking that. :) foo on the other hand would run out to 10^6 and then conveniently finish the rest of your program waiting for the need of the other 10^9-10 values. If you *always* needed the result of the 10^9 calculations then tail-recursion should be better since you won't be holding onto the evaluation frames. Even if you did, in the presense of laziness it's not useful to make list producers tail recursive. Consider: sum = sum' 0 sum' k [] = k sum' k (x:xs) = (sum' $! (k+x)) xs enum x y | x = y= 0 | otherwise = x : enum (x+1) y sum (enum 1 10) = sum' 0 (enum 1 10) = sum' 0 (1 : enum (1+1) 10) = (sum' $! (0+1)) (enum (1+1) 10) = sum' 1 (enum (1+1) 10) = sum' 1 (2 : enum (2+1) 10) = (sum' $! (1+2)) (enum (2+1) 10) = sum' 3 (enum (2+1) 10) = sum' 3 (3 : enum (3+1) 10) = (sum' $! (3+3)) (enum (3+1) 10) = sum' 6 (enum (3+1) 10) = sum' 6 (4 : enum (4+1) 10) = (sum' $! (6+4)) (enum (4+1) 10) = sum' 10 (enum (4+1) 10) = ... sum' 36 (9 : enum (9+1) 10) = (sum' $! (36+9)) (enum (9+1) 10) = sum' 45 (enum (9+1) 10) = sum' 45 [] = 45 (I need to find some way to automate making these trails :) ) It runs in constant space, despite the producer's non-tail-recursion. Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
Thanks. I got confused because the StackOverflow link on http://www.haskell.org/haskellwiki/HaWiki_migration is dead. -Original Message- From: Derek Elkins [mailto:[EMAIL PROTECTED] Sent: Saturday, August 18, 2007 8:54 PM To: Peter Verswyvelen Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki? On Sat, 2007-08-18 at 20:35 +0200, Peter Verswyvelen wrote: When reading an article about tail recursion (http://themechanicalbride.blogspot.com/2007/04/haskell-for-c-3-programmers. html) I came across the follow statements: If you can write a non-recursive function that uses the colon syntax it is probably better than a tail recursive one that doesn't. This is because Haskell's lazy evaluation enabled you to use the non-tail recursive version on an infinite stream without getting a stack overflow. and Unfortunately, laziness gets in the way. While transforming non-tail-recursive code to a tail-recursive form is important and useful for functional programming in general, dealing with laziness requires a little more care, and often non-tail-recursive versions are preferrable. flatten is an example of this, the first version is better in many ways. While I don't believe it happens in this case, oftentimes naively writing code tail-recursively in Haskell will actually -make- it overflow the stack. Another (actual) benefit of the first version of flatten is that it will work on infinite lists. http://www.haskell.org/hawiki/StackOverflow gives a simple example and some explanation. That page was migrated here: http://www.haskell.org/haskellwiki/Stack_overflow ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
On Sat, 2007-08-18 at 20:35 +0200, Peter Verswyvelen wrote: When reading an article about tail recursion (http://themechanicalbride.blogspot.com/2007/04/haskell-for-c-3-programmers. html) I came across the follow statements: If you can write a non-recursive function that uses the colon syntax it is probably better than a tail recursive one that doesn't. This is because Haskell's lazy evaluation enabled you to use the non-tail recursive version on an infinite stream without getting a stack overflow. and Unfortunately, laziness gets in the way. While transforming non-tail-recursive code to a tail-recursive form is important and useful for functional programming in general, dealing with laziness requires a little more care, and often non-tail-recursive versions are preferrable. flatten is an example of this, the first version is better in many ways. While I don't believe it happens in this case, oftentimes naively writing code tail-recursively in Haskell will actually -make- it overflow the stack. Another (actual) benefit of the first version of flatten is that it will work on infinite lists. http://www.haskell.org/hawiki/StackOverflow gives a simple example and some explanation. That page was migrated here: http://www.haskell.org/haskellwiki/Stack_overflow ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question: Where is StackOverflow on the Wiki?
foo n = if n0 then [] else n : foo (n-1) bar n = aux 0 [] where aux i xs = if in then xs else aux (i+1) (i:xs) that foo is more efficient than bar because lazy evaluation of foo just puts the delayed computation in the cdr of the list, while lazy evaluation of bar has to keep track of all aux calls (the closures) which gives much more overhead, maybe even stack overflow? Something like that? There is absolutely no problem with bar, it will not stack overflow since it _is_ tail-recursive _and_ the comparison i n force the evaluation of i avoiding the risk of constructing a too big thunk for the first parameter of aux which could bring a stack overflow like in this example : nonStrictLength n [] = n nonStrictLength n (_:xs) = nonStrictLength (n+1) xs (try nonStrictLength 0 [1..1000] in GHCi to see the stack overflow, GHC strictness analysis would avoid the problem with -O) Though foo is still more interesting than bar since it will work on infinite list, bar is too strict. -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
