Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Thanks for the memo trick! Now I understand that the haskell compiler cannot memoize functions of integers, because it could change the space behaviour. However I think it could memoize everything else. Because all types that are data objects sitting in memory (so the arg is essentially a reference) can be memoized, without changing the space properties (except for overall constants). Does haskell do this? And if it doesn't can you turn it on? Cheers, Gerben -- View this message in context: http://www.nabble.com/Reduction-Sequence-of-simple-Fibonacci-sequence-implementation-tp25178377p25187256.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Hello staafmeister, Friday, August 28, 2009, 1:54:38 PM, you wrote: it just works other way. imagine a whole haskell program as a graph. i.e. expression 1+2, for example, forms a node with (=) in its root and 1 and 2 as its subtrees. computation of program is a series of graph reductions, replacing nodes with results, f.e. 1+2 = 3 this graph can share computations in only one way - when you give sharec node a name and use this name twice. for example, the following sum[1..1000] + prod[1..1000] don't share anything, but this let list = [1..1000] in sum list + prod list share the list. performing sharing via explicit naming common subexpressions is the only way to memoize results you imagine something highly inefficient like storing results of every computation ever done. are you think it really makes a sense? sometimes haskell compilers may deduce that some computation is used twice. if result of this computation definitely require less memory than computation itself, compiler may perform optimization by storing its result. it's called Common Subexpression Elimination. but its' not guaranteed, and afaik is pretty limited in ghc Thanks for the memo trick! Now I understand that the haskell compiler cannot memoize functions of integers, because it could change the space behaviour. However I think it could memoize everything else. Because all types that are data objects sitting in memory (so the arg is essentially a reference) can be memoized, without changing the space properties (except for overall constants). Does haskell do this? And if it doesn't can you turn it on? Cheers, Gerben -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
On Fri, Aug 28, 2009 at 3:54 AM, staafmeisterg.c.stave...@uu.nl wrote: Thanks for the memo trick! Now I understand that the haskell compiler cannot memoize functions of integers, because it could change the space behaviour. However I think it could memoize everything else. Because all types that are data objects sitting in memory (so the arg is essentially a reference) can be memoized, without changing the space properties (except for overall constants). Does haskell do this? And if it doesn't can you turn it on? Integers are nothing special. Consider functions on: data Nat = Zero | Succ Nat Now, perhaps you mean memoize specific Nat *references* (a meaningless question for Haskell, only for specific implementations) rather than the *values*. Eg., for some f: would not. let x = Succ Zero in f x + f x would memoize the result of f, but: f (Succ Zero) + f (Succ Zero) would not. GHC does not do this. However, I am working in my free time on an experimental graph reducer which does. It implements a semantics called complete laziness[1]. I'm experimenting to see how that changes the engineering trade-offs (I have a blog post about what I expect those to be: http://lukepalmer.wordpress.com/2009/07/07/emphasizing-specialization/) For programs that do not benefit from the extra sharing, I should be lucky to run them only 50 times slower. This is an indication why GHC doesn't do this. Complete laziness is a fairly young research field. Maybe someday we'll get a smokin' fast completely lazy reducer. [1] http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/sinot-wrs07.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Hallo everyone, as Haskell uses the Lazy Evaluation reduction policy also known as Outermost Graph Reduction, I was wondering if the following simple implementation of the Fibonacci sequence would result in linear runtime behaviour. fib :: Integer - Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) Is the following reduction sequence realistic, or am I admitting to much intelligence to the Haskell Compiler? http://www.bilder-hochladen.net/files/bxlk-6-jpg.html http://www.bilder-hochladen.net/files/thumbs/bxlk-6.jpg I hope someone can help... -- View this message in context: http://www.nabble.com/Reduction-Sequence-of-simple-Fibonacci-sequence-implementation-tp25178377p25178377.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Hello SimonK77, Thursday, August 27, 2009, 11:24:14 PM, you wrote: for linear timing it needs memoization of previous results. haskell compilers doesn't do it automatically since it may change space properties of program. well-known example is: main = print (sum[1..1000] + prod[1..1000]) in order to use memoization you should declare fib as array: fib = array (1,999) ([1,1]++map (\i - fib!(i-1) + fib!(i-2)) [3..999]) Hallo everyone, as Haskell uses the Lazy Evaluation reduction policy also known as Outermost Graph Reduction, I was wondering if the following simple implementation of the Fibonacci sequence would result in linear runtime behaviour. fib :: Integer - Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) Is the following reduction sequence realistic, or am I admitting to much intelligence to the Haskell Compiler? I hope someone can help... View this message in context: Reduction Sequence of simple Fibonacci sequence implementation Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
On Thu, Aug 27, 2009 at 12:32 PM, Bulat Ziganshinbulat.zigans...@gmail.com wrote: Hello SimonK77, Thursday, August 27, 2009, 11:24:14 PM, you wrote: for linear timing it needs memoization of previous results. haskell compilers doesn't do it automatically since it may change space properties of program. well-known example is: main = print (sum[1..1000] + prod[1..1000]) in order to use memoization you should declare fib as array: fib = array (1,999) ([1,1]++map (\i - fib!(i-1) + fib!(i-2)) [3..999]) Unless I'm mistaken this one is also memoized and simpler: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) Then to get a specific fib, zero index, you do: fib n = fibs !! n Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Hello SimonK77, Thursday, August 27, 2009, 11:24:14 PM, you wrote: list-based memoization for fibs should look as fibs = 1 : 1 : map (sum.take 2) (tails fibs) Hallo everyone, as Haskell uses the Lazy Evaluation reduction policy also known as Outermost Graph Reduction, I was wondering if the following simple implementation of the Fibonacci sequence would result in linear runtime behaviour. fib :: Integer - Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) Is the following reduction sequence realistic, or am I admitting to much intelligence to the Haskell Compiler? I hope someone can help... View this message in context: Reduction Sequence of simple Fibonacci sequence implementation Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation
Am Donnerstag 27 August 2009 21:41:49 schrieb Jason Dagit: On Thu, Aug 27, 2009 at 12:32 PM, Bulat Ziganshinbulat.zigans...@gmail.com wrote: Hello SimonK77, Thursday, August 27, 2009, 11:24:14 PM, you wrote: for linear timing it needs memoization of previous results. haskell compilers doesn't do it automatically since it may change space properties of program. well-known example is: main = print (sum[1..1000] + prod[1..1000]) in order to use memoization you should declare fib as array: fib = array (1,999) ([1,1]++map (\i - fib!(i-1) + fib!(i-2)) [3..999]) Unless I'm mistaken this one is also memoized and simpler: fibs = 1 : 1 : zipWith (+) fibs (tail fibs) Should be fibs = 0:1:zipWith (+) fibs (tail fibs) of course. Then to get a specific fib, zero index, you do: fib n = fibs !! n Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
