# why isnt this optimized? Classic List Threaded 4 messages Reply | Threaded
Open this post in threaded view
|

## why isnt this optimized?

 Hi, I wrote a recursive fibonacci function in ghci: :set +m let f 0 = 0 f 1 = 1 f n = f (n-1) + f (n-2) As expected calculation f 30 takes a while. About 5s on my machine. What I don't understand is that let x = f 30 in (x,x) takes twice as long. Why is ghci reevaluating the x twice? Isn't in always said, that it can optimize because we can replace same by same and so on. Actually if compiled the behaviour is as expected. main = print \$ let x = f 34 in (x) and main = print  \$ let x = f 34 in (x,x) both take about 3s. Why is this not the case in the interactive enviroment? Thanks Gunnar _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

## Re: why isnt this optimized?

 Hello, Observe this example : Prelude> let x = f 30 in (x,x) (832040,832040) (3.70 secs, 1,649,318,104 bytes) Prelude> let x = (f 30) :: Int in (x,x) (832040,832040) (1.77 secs, 854,498,640 bytes) If we force the result type of f 30 to Int, the result is shared as expected. This is related to the monomorphism restriction https://wiki.haskell.org/Monomorphism_restrictionWe can observe the type of (x, x) : Prelude> let y = (let x = f 30 in (x, x)) Prelude> :t y y :: (Num t1, Num t) => (t, t1) Both value does not have the same type. Actually `f` is a polymorphic function which can compute the result for any type t as long as t is a `Num`. So we can compute it for `Double`, `Float`, `BigMatriceOf100GigaBytesOfInfinitePrecisionRationalNumbers`. The compiler will only know the final type when needed, later. Actually, the (x, x) tuple is already computed (but `x` are unevaluated) when, by displaying it, you decide to fix `x` as `Integer` for both (the default `Num`). The setting is a bit different for compiled code, because in this case, the compiler choose the type earlier. For example, in a file `Foo.hs` a = 10 y = (a, a) :: (Float, Integer) BlorkBlork.hs:2:9: error:     • Couldn't match expected type ‘Integer’ with actual type ‘Float’     • In the expression: a       In the expression: (a, a) :: (Float, Integer)       In an equation for ‘z’: z = (a, a) :: (Float, Integer) Failed, modules loaded: none. Because the compiler takes the first encountered type (Float) as the type of a. However you can keep the polymorphism with a type signature : a :: Num t => t a = 10 y = (a, a) :: (Float, Integer) This is one of the rare case where adding a type signature adds polymorphism compared to the infered type. Will works. Hope this help. -- G. On Fri, Sep 16, 2016 at 4:24 AM, Gunnar Quehl <[hidden email]> wrote: > Hi, > > I wrote a recursive fibonacci function in ghci: > > :set +m > > let > f 0 = 0 > f 1 = 1 > f n = f (n-1) + f (n-2) > > As expected calculation f 30 takes a while. About 5s on my machine. > What I don't understand is that > > let x = f 30 in (x,x) > > takes twice as long. Why is ghci reevaluating the x twice? Isn't in always > said, > that it can optimize because we can replace same by same and so on. > > Actually if compiled the behaviour is as expected. > > main = print \$ let x = f 34 in (x) > > and > > main = print  \$ let x = f 34 in (x,x) > > both take about 3s. > > Why is this not the case in the interactive enviroment? > > Thanks > Gunnar > > _______________________________________________ > Beginners mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

## Re: why isnt this optimized?

 Am 16.09.2016 um 10:54 schrieb Guillaume Bouchard: > Hello, > > Observe this example : > > Prelude> let x = f 30 in (x,x) > (832040,832040) > (3.70 secs, 1,649,318,104 bytes) > > Prelude> let x = (f 30) :: Int in (x,x) > (832040,832040) > (1.77 secs, 854,498,640 bytes) > > If we force the result type of f 30 to Int, the result is shared as expected. > > This is related to the monomorphism restriction > https://wiki.haskell.org/Monomorphism_restriction> > We can observe the type of (x, x) : > > Prelude> let y = (let x = f 30 in (x, x)) > Prelude> :t y > y :: (Num t1, Num t) => (t, t1) > > > Both value does not have the same type. Actually `f` is a polymorphic > function which can compute the result for any type t as long as t is a > `Num`. So we can compute it for `Double`, `Float`, > `BigMatriceOf100GigaBytesOfInfinitePrecisionRationalNumbers`. The > compiler will only know the final type when needed, later. Actually, > the (x, x) tuple is already computed (but `x` are unevaluated) when, > by displaying it, you decide to fix `x` as `Integer` for both (the > default `Num`). > > The setting is a bit different for compiled code, because in this > case, the compiler choose the type earlier. For example, in a file > `Foo.hs` > > a = 10 > y = (a, a) :: (Float, Integer) > > > BlorkBlork.hs:2:9: error: >      • Couldn't match expected type ‘Integer’ with actual type ‘Float’ >      • In the expression: a >        In the expression: (a, a) :: (Float, Integer) >        In an equation for ‘z’: z = (a, a) :: (Float, Integer) > Failed, modules loaded: none. > > Because the compiler takes the first encountered type (Float) as the type of a. > > However you can keep the polymorphism with a type signature : > > a :: Num t => t > a = 10 > > y = (a, a) :: (Float, Integer) > > This is one of the rare case where adding a type signature adds > polymorphism compared to the infered type. > > Will works. > > Hope this help. > Wow, this reply was much more than I expected. You are my heroe. I actually started off with the definition let fibs = 0:1:zipWith (+) fibs (tail fibs) and wondered why looking at a certain cell with  for example fibs !! 20000 always took some amount of time to evaluation, as I expected the second time it should be already there. Now I can explain (and do something about it, add a type signature). Thanks that starts to become a good day _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

## Re: why isnt this optimized?

 Glad I was able to help you, some added informations : On Fri, Sep 16, 2016 at 12:01 PM, Gunnar Quehl <[hidden email]> wrote: > Wow, this reply was much more than I expected. You are my heroe. > I actually started off with the definition > > let fibs = 0:1:zipWith (+) fibs (tail fibs) > > and wondered why looking at a certain cell with  for example > > fibs !! 20000 > > always took some amount of time to evaluation, as I expected the > second time it should be already there. Now I can explain (and do > something about it, add a type signature). You can use :set +s in ghci to get the time of the line. Also, you can use :sprint to display the evaluation status of the thunk, really useful to debug / understand lazyness issues. Prelude> let l = map (*2) [1::Int ..10] Prelude> :sprint l l = _ Prelude> length l 10 Prelude> :sprint l l = [_,_,_,_,_,_,_,_,_,_] Prelude> take 3 l [2,4,6] Prelude> Prelude> :sprint l l = [2,4,6,_,_,_,_,_,_,_] Finally, recal that (!!) is still an O(n) operator on the fibs list, but you can build an infinite fibs list with O(n log n) query using an infinite Tree see https://wiki.haskell.org/Memoization#Efficient_tree_data_structure_for_maps_from_Int_to_somewhere> Thanks that starts to become a good day ;) -- G. _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners