why isnt this optimized?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

why isnt this optimized?

Gunnar Quehl
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?

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.

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

Gunnar Quehl
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?

Guillaume Bouchard
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