Editing Memoization (section)

== Memoization without recursion ==

You can just write a memoization function using a data structure that is suitable for your application.
We don't go into the details of this case.
If you want a general solution for several types,
you need a type class, say <code>Memoizable</code>.
<haskell>
memoize :: Memoizable a => (a->b) -> (a->b)
</haskell>

Now, how to implement something like this? Of course, one needs a finite
map that stores values <code>b</code> for keys of type <code>a</code>.
It turns out that such a map can be constructed recursively based on the structure of <code>a</code>:
<haskell>
  Map ()            b  := b
  Map (Either a a') b  := (Map a b, Map a' b)
  Map (a,a')        b  := Map a (Map a' b)
</haskell>

Here, <code>Map a b</code> is the type of a finite map from keys <code>a</code> to values <code>b</code>.
Its construction is based on the following laws for functions
<haskell>
        () -> b  =~=  b
  (a + a') -> b  =~=  (a -> b) × (a' -> b) -- = case analysis
  (a × a') -> b  =~=  a -> (a' -> b)       -- = currying
</haskell>

For further and detailed explanations, see

* Ralf Hinze: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3272 Memo functions, polytypically!]
* Ralf Hinze: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.4069 Generalizing generalized tries]
* Conal Elliott: [http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/ Elegant memoization with functional memo tries] and other [http://conal.net/blog/tag/memoization/ posts on memoization].
* Conal Elliott [http://conal.net/papers/type-class-morphisms/ Denotational design with type class morphisms], section 9 (Memo tries).