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. Relying on memoization (Russ Abbott)
2. Re: Functional Dependencies (Stephen Tetley)
3. Re: Relying on memoization (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Thu, 9 Dec 2010 20:39:32 -0800
From: Russ Abbott <[email protected]>
Subject: [Haskell-beginners] Relying on memoization
To: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
(Is that even the right term?)
Let's suppose I have a fairly complex computation to perform on a data
structure. Normally I would cache the computed value in a field of the
structure. The next time I need it I don't have to compute it again. (Of
course if the structure changes, I have to recompute the value and store it
again.)
In Haskell is it the case that caching of this sort is redundant since
Haskell does it for me? That is, if I call
f someStructure
multiple times at different places in my code and if both "f" and
"someStructure" refer to the same things each time, can I rely on Haskell
not to perform the computation multiple times but to look up the result it
previously computed?
Is there some limit to that? If every computation is stored, doesn't that
create a very large collection of stored results?
*
-- Russ *
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101209/454c21ad/attachment-0001.htm>
------------------------------
Message: 2
Date: Fri, 10 Dec 2010 09:04:40 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Functional Dependencies
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hello Dan
What is /unflt/ ? I'm presuming it can't be unflatten [*] as I don't
see how it would work.
If I was making a flatten class, I wouldn't want Monad as a constraint
on the result container. Monad doesn't really say anything about
"containers" - there are some containers that are Monads, but there
are monads that aren't containers and there are containers that aren't
monads.
The Foldable type class in Data.Foldable is quite like a class for
flattenable things, however it folds (flattens) into a monoidal thing
(often called a "summary" value). This isn't so good for flattening
into a list. List has a monoid instance but it is very inefficient. If
you want to flatten into a list-like thing rather than fold into a
summary value, you would really need a better class something like
"Cons"
class Cons t where
nil :: t a
cons :: a -> t a -> t a
By the way, there is no Monoid instance for Data.Tree at least at
version containers-0.3.0.0.
[*] If you are wanting unflatten as well, things get quite complicated...
------------------------------
Message: 3
Date: Fri, 10 Dec 2010 10:16:12 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Relying on memoization
To: [email protected]
Cc: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Fri, Dec 10, 2010 at 5:39 AM, Russ Abbott <[email protected]> wrote:
> (Is that even the right term?)
>
Yes.
> Let's suppose I have a fairly complex computation to perform on a data
> structure. Normally I would cache the computed value in a field of the
> structure. The next time I need it I don't have to compute it again. (Of
> course if the structure changes, I have to recompute the value and store it
> again.)
>
> In Haskell is it the case that caching of this sort is redundant since
> Haskell does it for me? That is, if I call
>
> f someStructure
>
>
> multiple times at different places in my code and if both "f" and
> "someStructure" refer to the same things each time, can I rely on Haskell
> not to perform the computation multiple times but to look up the result it
> previously computed?
>
No, you can't rely on that, and in general f someStructure will be computed
multiple times.
If two "f someStructure" appear in the same expression, there's a chance
they will be shared, but you can't rely on it. It's very hard to determine
when sharing common subexpressions is beneficial and when it's detrimental,
so at least in GHC, common subexpression elimination is not done much. If
you want something to be shared, give it a name in the enclosing scope, the
value that name is bound to will be computed only once (unless polymorphism
prevents sharing and forces the value to be recomputed).
>
> Is there some limit to that? If every computation is stored, doesn't that
> create a very large collection of stored results?
>
Right, and apart from needing a lot of memory, storing everything makes
finding the cached result slower than recomputing it in many cases.
> *
> -- Russ *
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101210/41c85144/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 30, Issue 13
*****************************************
