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

[Jacek Generowicz]

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

> Jacek Generowicz <jacek.generowicz at cern.ch> 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 :-)