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
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
*****************************************
