Re: [Haskell-cafe] Client-extensible heterogeneous types (Duck-typed variadic functions?)

On 2010 Oct 14, at 15:24, Ketil Malde wrote:

Jacek Generowicz writes:

...

def memoize(fn): cache = {} def memoized_fn(*args): if args not in cache: cache[args] = fn(*args) return cache[args] return memoized_fn

Here's a simplified memoizer for Haskell:

memoize :: (Integral t) => (t -> a) -> t -> a memoize f = ([f i | i <- [0..]]!!) . fromIntegral

This is a very cute snippet, but I think that its cuteness circumvents the whole point of the Python code, which was to demonstrate how heterogeneous duck-typed values can be used safely. The Python memoizer memoizes functions of *any* type: yours allows very limited heterogeneity, so I'm failing to see how it addresses the issue.

...

But what should the type of fn be? What should the type of args be?

The args to fn must be of a type that is indexable by the memoizing structure. My example is simplistic, and will only memoize functions where the first argument is a integral, non-negative number, and it uses a list (with O(n) access), but you can probably improve it as you see fit.

I think that now we're starting to concentrate on the memoizer in particular, rather that the more general issue that the memoizer was meant to exemplify.

I think this will work for multi-parameter functions too, because of currying.

...

In Python, I don't care, as long no type error occurs when they are combined thus:

...

fn(*args)

In Haskell, the type of 'memoize g' is the same as 'g', so you don't have to care - the compiler cares for you. :-)

Same in Python (except that the run-time cares for you, rather than the compiler). But in Haskell it sometimes also cares about fn and args separately, even when it shouldn't. My questions are about persuading it that it shouldn't.

Perhaps I'm missing something obvious?

I think that what you might have missed is that the only interesting type is that of fn(*args): that I don't care about the type of fn on its own, or the type of args on its own, but that together they make up whatever type is required. And that Haskell's type system gets in the way by insisting on checking the types of fn and args separately; while Python's gets out of the way, by only caring when the two are brought together and actually *used*. But maybe it is I who has missed you addressing this point. Either way, I think that pursuing the memoizer any further (interesting though it is in its own right) takes us too far off track. I think that the answer (well, one important answer) to my earlier question is: a) Existential Quantification allows you to do this. b) Skolemization allows you to do this without the Existential Quantification extension. From what little I've read around this subject, it seems that considerations similar to the ones I'm talking about are repeatedly used as motivations for Existential Quantification, so I'm pretty confident that I'm not completely full of crap; or if I am, then I'm in good company :-)