Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org

## Advertising

You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. why isnt this optimized? (Gunnar Quehl) 2. Re: why isnt this optimized? (Guillaume Bouchard) 3. Re: why isnt this optimized? (Gunnar Quehl) 4. Re: why isnt this optimized? (Guillaume Bouchard) ---------------------------------------------------------------------- Message: 1 Date: Fri, 16 Sep 2016 04:24:18 +0200 From: Gunnar Quehl <hasqu...@gmx.de> To: beginners@haskell.org Subject: [Haskell-beginners] why isnt this optimized? Message-ID: <dc96d48d-32ae-64cc-848c-e9425da48...@gmx.de> Content-Type: text/plain; charset=utf-8; format=flowed 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 ------------------------------ Message: 2 Date: Fri, 16 Sep 2016 10:54:05 +0200 From: Guillaume Bouchard <guillaum.bouchard+hask...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] why isnt this optimized? Message-ID: <cagh0hcdbfuczn9a+9thhgrhlnbas7va1rsh8cx0wa9frljx...@mail.gmail.com> Content-Type: text/plain; charset=UTF-8 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. -- G. On Fri, Sep 16, 2016 at 4:24 AM, Gunnar Quehl <hasqu...@gmx.de> 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 > Beginners@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners ------------------------------ Message: 3 Date: Fri, 16 Sep 2016 12:01:12 +0200 From: Gunnar Quehl <hasqu...@gmx.de> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] why isnt this optimized? Message-ID: <d90e1558-4212-cb48-40c2-d743cceca...@gmx.de> Content-Type: text/plain; charset=utf-8; format=flowed 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 ------------------------------ Message: 4 Date: Fri, 16 Sep 2016 13:52:39 +0200 From: Guillaume Bouchard <guillaum.bouchard+hask...@gmail.com> To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <beginners@haskell.org> Subject: Re: [Haskell-beginners] why isnt this optimized? Message-ID: <CAGh0HCCzm4snCQoab=prmme506g7j9cpzop-kaoqbuq_jkm...@mail.gmail.com> Content-Type: text/plain; charset=UTF-8 Glad I was able to help you, some added informations : On Fri, Sep 16, 2016 at 12:01 PM, Gunnar Quehl <hasqu...@gmx.de> 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. ------------------------------ Subject: Digest Footer _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners ------------------------------ End of Beginners Digest, Vol 99, Issue 11 *****************************************