Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Disappointing thought on Haskell -- a simple space leak
on "insert" is hard bug to catch (Heinrich Apfelmus)
2. Re: Disappointing thought on Haskell -- a simple space leak
on "insert" is hard bug to catch (KC)
3. Re: Disappointing thought on Haskell -- a simple space leak
on "insert" is hard bug to catch (Brandon Allbery)
4. understanding curried function calls (Dimitri DeFigueiredo)
5. Question on evaluating function compostion (Chul-Woong Yang)
6. Re: understanding curried function calls (John Wiegley)
----------------------------------------------------------------------
Message: 1
Date: Tue, 19 Aug 2014 16:42:22 +0200
From: Heinrich Apfelmus <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Disappointing thought on Haskell -- a
simple space leak on "insert" is hard bug to catch
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Dimitri DeFigueiredo wrote:
> Hi Heinrich,
>
> Thanks so much! :-)
>
> Wow! I was totally wrong on that one then. I got it that lazy evaluation
> is the culprit here. Now, I am still a little uneasy about insert
> producing a new version of the tree when it is not needed. Can't that
> come back to bite me later depending on how I use it?
>
> In your explanation, you say that "the old path is usually not
> referenced anywhere, and can be garbage collected immediately."
> I am a little uneasy about the "usually". Could you expand on that? What
> if it is? Could that happen? Or does that just imply a bigger constant?
First, note that a new version of the tree has to be created whenever
the element you insert was not in the tree. Most likely, your
"higher-up" algorithm that makes use of the tree structure doesn't treat
these two cases too differently, so you probably have to think about the
case where the tree is copied anyway.
Second, you may want to look up on how lazy evaluation, respectively
*graph reduction* work. This will answer your questions. For instance,
the new code that you wrote implicitly builds a new version of the tree
as well (building a tower of expressions of the form `>>= \r -> return $
MkTree a x r`) but discards it level by level when it turns out that the
end result is `Nothing`. Without an understanding of the evaluation
model, you will always feel uneasy.
The basic tenet of garbage collection is that the binding for any name
which does not occur in the current expression can be discard. For
instance, in the expression
let x = "A String which uses a lot of memory"
y = 12
in y + 2
we can safely discard the name `x` and its value, as the name `x` does
not occur in the expression `y + 2`.
But in the expression,
let x = "A String which uses a lot of memory"
y = 12
in snd (x,y+2)
we may not discard `x` just yet, because it still occurs in the
expression `snd (x,y+2)`. Of course, performing reduction step will turn
this into `y+2` and now the memory used by binding for `x` can be freed.
Note that the runtime may choose to wait some time before freeing the
associated memory. In fact, at periodic intervals, the runtime will stop
the current evaluation and instead perform a process called "garbage
collection", where it looks for all variable names and frees the memory
of those that are no longer needed.
A "space leak" generally refers to the situation where a name is no
longer needed but still occurs in the expression to be evaluated. This
is very much like the `x` in the second example: it's "not really
needed", because we humans know that `snd` doesn't use it, but it's
still written there, so the runtime can't throw it away.
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 2
Date: Tue, 19 Aug 2014 08:34:53 -0700
From: KC <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Disappointing thought on Haskell -- a
simple space leak on "insert" is hard bug to catch
Message-ID:
<CAMLKXynQHEtf=Ph4zfWT7-PK--=hnqq+rjcfl9pbuptagi3...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi:
Heinrich Apfelmus wrote:
"But in the expression,
let x = "A String which uses a lot of memory"
y = 12
in snd (x,y+2)
we may not discard `x` just yet, because it still occurs in the expression
`snd (x,y+2)`. Of course, performing reduction step will turn this into
`y+2` and now the memory used by binding for `x` can be freed."
Wouldn't the compiler know how "snd" works and therefore know that the
first argument isn't needed?
Isn't the above the advantage of pure code - same inputs ~ same outputs?
On Tue, Aug 19, 2014 at 7:42 AM, Heinrich Apfelmus <
[email protected]> wrote:
> Dimitri DeFigueiredo wrote:
>
>> Hi Heinrich,
>>
>> Thanks so much! :-)
>>
>> Wow! I was totally wrong on that one then. I got it that lazy evaluation
>> is the culprit here. Now, I am still a little uneasy about insert producing
>> a new version of the tree when it is not needed. Can't that come back to
>> bite me later depending on how I use it?
>>
>> In your explanation, you say that "the old path is usually not referenced
>> anywhere, and can be garbage collected immediately."
>> I am a little uneasy about the "usually". Could you expand on that? What
>> if it is? Could that happen? Or does that just imply a bigger constant?
>>
>
> First, note that a new version of the tree has to be created whenever the
> element you insert was not in the tree. Most likely, your "higher-up"
> algorithm that makes use of the tree structure doesn't treat these two
> cases too differently, so you probably have to think about the case where
> the tree is copied anyway.
>
> Second, you may want to look up on how lazy evaluation, respectively
> *graph reduction* work. This will answer your questions. For instance, the
> new code that you wrote implicitly builds a new version of the tree as well
> (building a tower of expressions of the form `>>= \r -> return $ MkTree a x
> r`) but discards it level by level when it turns out that the end result is
> `Nothing`. Without an understanding of the evaluation model, you will
> always feel uneasy.
>
> The basic tenet of garbage collection is that the binding for any name
> which does not occur in the current expression can be discard. For
> instance, in the expression
>
> let x = "A String which uses a lot of memory"
> y = 12
> in y + 2
>
> we can safely discard the name `x` and its value, as the name `x` does not
> occur in the expression `y + 2`.
>
> But in the expression,
>
> let x = "A String which uses a lot of memory"
> y = 12
> in snd (x,y+2)
>
> we may not discard `x` just yet, because it still occurs in the expression
> `snd (x,y+2)`. Of course, performing reduction step will turn this into
> `y+2` and now the memory used by binding for `x` can be freed.
>
> Note that the runtime may choose to wait some time before freeing the
> associated memory. In fact, at periodic intervals, the runtime will stop
> the current evaluation and instead perform a process called "garbage
> collection", where it looks for all variable names and frees the memory of
> those that are no longer needed.
>
> A "space leak" generally refers to the situation where a name is no longer
> needed but still occurs in the expression to be evaluated. This is very
> much like the `x` in the second example: it's "not really needed", because
> we humans know that `snd` doesn't use it, but it's still written there, so
> the runtime can't throw it away.
>
>
>
> Best regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
--
Sent from an expensive device which will be obsolete in a few months! :D
Casey
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140819/8824c9fc/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 19 Aug 2014 12:48:50 -0400
From: Brandon Allbery <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Disappointing thought on Haskell -- a
simple space leak on "insert" is hard bug to catch
Message-ID:
<CAKFCL4VoicUxtMrC2HBY8KkeOMTCY-fi-q=wxdwu_smqoob...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Aug 19, 2014 at 11:34 AM, KC <[email protected]> wrote:
> Wouldn't the compiler know how "snd" works and therefore know that the
> first argument isn't needed?
No, snd is not a compiler built-in.
--
brandon s allbery kf8nh sine nomine associates
[email protected] [email protected]
unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140819/6f1518fc/attachment-0001.html>
------------------------------
Message: 4
Date: Wed, 20 Aug 2014 02:19:16 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] understanding curried function calls
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Here's a simple exercise from Stephanie Weirich's class [1] that I am
having a hard time with.
consider
doTwice :: (a -> a) -> a -> a
doTwice f x = f (f x)
what does this do?
ex1 :: (a -> a) -> a -> a
ex1 = doTwice doTwice
At least, it is clear that there is a parameter to doTwice missing. So,
I wanted to do:
ex1 y = (doTwice doTwice) y
but this gets me nowhere as I don't know how to apply the definition of
doTwice inside
the parenthesis without naming the arguments.
What is the systematic way to evaluate these expressions? I actually got
really
stumped when I considered.
ex2 :: (a -> a) -> a -> a
ex2 = doTwice doTwice doTwice doTwice
I assume this is not the same as
ex2 = (doTwice doTwice doTwice) doTwice
what's being applied to what here!?
Are there any resources with many practice exercises like this one?
Thanks,
Dimitri
[1] http://www.seas.upenn.edu/~cis552/lectures/Lec2.html
------------------------------
Message: 5
Date: Wed, 20 Aug 2014 18:59:13 +0900
From: Chul-Woong Yang <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Question on evaluating function
compostion
Message-ID:
<CALmycjr1PeNEQoExd=zbsLc=jnbcwnqwr7zfx0e4z7eqqq2...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi, all
I'm having trouble in understanding function evaluation in Haskell.
I came across the following line, which is somewhat cryptic to me.
(liftM . (+)) 1 [2]
Could you explain how the expression evaluates?
I thought that to evalutate two composed functions,
I should apply right function to get a result and then
apply left function with the result.
e.g. f.g x y = f (g x y) = f z = result
So I guessed that Haskell evaluated above expression
as follows:
(liftM . (+)) 1 [2] --->
((liftM . (+)) 1) [2] ---> (A)
(liftM (+1)) [2] -->
[3]
Why did Haskell, however, not try to fully evaluate addition,
like following?
(liftM . (+)) 1 [2] --->
liftM ((+) 1 [2]) --->
error
Does (f . g) x y z equal ((((f . g) x) y) z) in haskell?
Any guide will be appreciated.
Chul-Woong
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140820/d0531972/attachment-0001.html>
------------------------------
Message: 6
Date: Wed, 20 Aug 2014 05:10:57 -0500
From: "John Wiegley" <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] understanding curried function calls
Message-ID: <[email protected]>
Content-Type: text/plain
>>>>> Dimitri DeFigueiredo <[email protected]> writes:
> Here's a simple exercise from Stephanie Weirich's class [1] that I am having
> a hard time with.
> consider
> doTwice :: (a -> a) -> a -> a
> doTwice f x = f (f x)
> what does this do?
> ex1 :: (a -> a) -> a -> a
> ex1 = doTwice doTwice
Another way to write doTwice is:
doTwice :: (a -> a) -> (a -> a)
doTwice f = \x -> f (f x)
This is equivalent. If you stare it for a while, it should answer the rest of
your questions.
John
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 74, Issue 17
*****************************************
