[Haskell-cafe] Memoization

[Isaac Dupree]

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


Isaac
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGXZPDHgcxvIWYTTURAi9fAJ44oIE85tZd+OtUOKswZnleBdt7eACeJuET
65AkQ2zI15CH6pnMHFmQddE=
=n5OS
-----END PGP SIGNATURE-----