[Haskell-cafe] Memoization

[Creighton Hogg]

On 5/30/07, Isaac Dupree <isaacdupree at charter.net> wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Creighton Hogg wrote:
> > Now maybe I'm being dense here, but would you really *want* a way in
> > Haskell
> > to do something like
> > memo :: (a->b) -> a->b
> > since it changes the semantics of the function?
> > It seems like a better abstraction would be to have
> > memo :: (a->b)-> M a b
> > where M is an instance of Arrow so that you can keep a proper notion of
> > composition between memoized functions.
> > Is there something wrong with my thinking?
>
> "memoize f gives you back a function that maintains a cache of
> previously computed values, so that subsequent calls with the same
> input will be faster."
>
> Speed isn't part of Haskell function semantics (luckily, or we wouldn't
> be able to have an optimizer in the first place).
>
> memoize does not change the semantics of the function (I think)
>
> Your "better abstraction" is, anyway, better in terms of being
> implementable in existing Haskell - you might need an (Eq a) context or
> something. However it interferes with code structure for a
> non-semantical change (strong effects on memory use and speed which you
> might _want_ to manage more explicitly, but that's not theoretically
> affecting purity)


Eh, I guess I was just being fascist.  I suppose that even if there are side
effects involved in the memoization, it doesn't break referential
transparency which is the real measure of purity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070530/87ddfdc4/attachment-0001.htm