Comments on A Neighborhood of Infinity: Memoizing Polymorphic Functions with High School A...

Dear Author blog.sigfpe.com ! It you have correct...

2009-11-29T16:57:21.869-08:00

Dear Author blog.sigfpe.com !
It you have correctly told :)

This was great and challenging. I followed the lin...

2009-11-09T10:46:52.940-08:00

This was great and challenging. I followed the link back to your old post about data and codata and a few more lights turned on upstairs. Kind of like skiing a blue run after a black. Thanks for continuing this blog!

ertai, Thanks for that. It makes me grumpy when ...

2009-11-09T10:34:41.672-08:00

ertai,

Thanks for that.

It makes me grumpy when the Haskell compiler forces me to implement a function of type voidElim ∷ Void → ∀ a· a when it seems obvious to me that a complete implementation should take zero lines of code. :-)

I also think that a n=0 version would help underst...

2009-11-09T06:43:56.088-08:00

I also think that a n=0 version would help understanding better the solution.

> type T0 f = T f Void

> voidElim ∷ Void → ∀ a· a
> voidElim _ = error "voidElim: impossible"

> memoize0 ∷ Functor f ⇒ (∀ a· [a] → f a) → T0 f
> memoize0 f = memoize (λ(_ , xs) → f xs)

> memoize0' ∷ Functor f ⇒ T0 f → ∀ a· [a] → f a
> memoize0' t xs = memoize' t (voidElim, xs)

Shin no Noir, The constraint is missing only beca...

2009-11-08T13:10:01.101-08:00

Shin no Noir,

The constraint is missing only because I could accidentally get away with it without the compiler complaining.

Is there a reason why you don't include the (F...

2009-11-08T12:43:03.541-08:00

Is there a reason why you don't include the (Functor f =>) constraint in the type of yoneda? It would make yoneda less general, but on the other hand would make it more symmetric with its inverse yoneda'.

Sjoerd, Maybe I should have said ir more clearly,...

2009-11-08T07:11:57.793-08:00

Sjoerd,

Maybe I should have said ir more clearly, but for n=0, (n->a,[a]) -> f a is the same as [a]. I could add a line to exhibit that isomorphism.

Or maybe you meant the more philosophical question of "why when looking to memoize [a] -> f a are we led to a whole family of types?". Which I'm not sure how to answer.

What I don't understand is that you want to me...

2009-11-08T02:47:20.949-08:00

What I don't understand is that you want to memoize forall a. [a] -> f a, and end up with memoization for forall a. (n -> a, [a]) -> f a

Great work! I will still need some time to fully d...

2009-11-08T01:36:28.414-08:00

Great work! I will still need some time to fully digest this but...

Just a quick remark, in your definition of Exists:

data Exists f a = forall a. Exists (f a)

The type parameter 'a' is useless and misleading since it is different
from the forall one. I suggest:

data Exists f = forall a. Exists (f a)