Beginners Digest, Vol 99, Issue 11

```Send Beginners mailing list submissions to

To subscribe or unsubscribe via the World Wide Web, visit
or, via email, send a message with subject or body 'help' to
```
You can reach the person managing the list at

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

Why is this not the case in the interactive enviroment?

Thanks
Gunnar

------------------------------

Message: 2
Date: Fri, 16 Sep 2016 10:54:05 +0200
To: The Haskell-Beginners Mailing List - Discussion of primarily
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

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)

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)
>
>
> Why is this not the case in the interactive enviroment?
>
> Thanks
> Gunnar
>
> _______________________________________________
> Beginners mailing list

------------------------------

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

Thanks that starts to become a good day

------------------------------

Message: 4
Date: Fri, 16 Sep 2016 13:52:39 +0200
To: The Haskell-Beginners Mailing List - Discussion of primarily
Subject: Re: [Haskell-beginners] why isnt this optimized?
Message-ID:
<CAGh0HCCzm4snCQoab=prmme506g7j9cpzop-kaoqbuq_jkm...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

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

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

> Thanks that starts to become a good day

;)

--
G.

------------------------------

Subject: Digest Footer

_______________________________________________
Beginners mailing list