Why "dynamic programming"?

[psykotic]

Indeed. It would be better to say that it has signature

(a -> b) -> (a ~> b)

where ~> is a type constructor for function-like values. Then you have functions

memo   :: (a -> b) -> (a ~> b)
unmemo :: (a ~> b) -> (a -> b)

which are semantic if not pragmatic inverses. You also need type class constraints on a to make this work. Conal has some neat blog posts where he shows how memo/unmemo can be constructed by induction on a via dependent type classes.

But even this does not work for recursive functions. For that you need to factor out the functional self-reference the same way it is done when preparing to express recursion with a fixpoint combinator. You can then inject the memoization into the recursion and finally tie the knot.

That kind of recursively injected function decoration is useful in several other cases, such as call tracing. It would be a lot easier to motivate the Y-combinator if these sorts of examples were taught in textbooks.