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

[Jacek Generowicz]

On 2010 Oct 14, at 09:56, Max Bolingbroke wrote:

> On 14 October 2010 08:34, Jacek Generowicz  
> <jacek.generowicz at cern.ch> wrote:
>> Those other data might be the functions' arguments, or they might  
>> be other
>> functions with which they are to be combined, or both.
>
> You can represent these as existential packages. However, as Oleg
> shows you can always use skolemisation to eliminate the existential:
> http://okmij.org/ftp/Computation/Existentials.html
>
> This trick is basically what Brandon and Evan pointed out earlier when
> they suggested you replace the list :: [exists b. (b -> a, b)] with a
> list :: [a].

Aaah. The link between the last two paragraphs is important. Thanks  
very much.

>> Here's an example where lazy evaluation isn't enough:
>>
>> def memoize(fn):
>>    cache = {}
>>    def memoized_fn(*args):
>>        if args not in cache:
>>            cache[args] = fn(*args)
>>        return cache[args]
>>    return memoized_fn
>>
>> You memoize a function once, but it will be given different  
>> arguments, many
>> times, at a later time.
>
> I'm not sure why you would use existentials for this. Isn't the type
> of memoized_fn just :: Ord a => (a -> b) -> a -> b?

I don't think so.

The Python Duck Type of memoized_fn (and fn), expressed in Haskell  
syntax is

a -> b |
a -> b -> c |
a -> b -> c -> d |
etc.

The type of memoize would be

(a -> b) -> a -> b |
(a -> b -> c) -> a -> b -> c |
(a -> b -> c -> d) -> a -> b -> c -> d |
etc.

Which is the whole point of the * in *args.

(Not sure why you specified Ord a. In Python you *would* need Hashable  
a,b,c,d.)

Of course, you could argue that the type is

(a -> b) -> a -> b |
(a -> b -> c) -> (a, b) -> c |
(a -> b -> c -> d) -> (a, b, c) -> d |
etc.

But does that change things significantly?

> This doesn't deal with argument *lists* so you may have to
> curry/uncurry to get functions of a different arity to go through, but
> that is IMHO a reasonable requirement for Haskell, where
> multi-argument functions do not have special status.

I would argue that easily dealing with different arities is an  
important requirement of the "arithmetic test" motivating example.

> (In the absence of side effects, I can't see an obvious way to
> implement it without some way to enumerate the domain "a" though.
> Conal Elliot uses type classes to solve this issue, see
> http://hackage.haskell.org/package/MemoTrie, where memo :: HasTrie t
> => (t -> a) -> t -> a).

Thanks for the heads-up.

>> will do. So please allow me to store (fnA1, fnA2) and (fnB1, fnB2)  
>> in the
>> same place. The program can tell that it can combine them with (.)  
>> because
>> the type of
>
> But if the only operation you ever do on this pair is (.), you may as
> well skolemise and just store (fnA1 . fnA2) directly. What is the
> advantage of doing otherwise?

(.) is not the *only* operation I will do. But I think that's a red  
herring. Regardless of what operation I will do, I think that the  
problem is
that some of the components are known earlier than others. But I think  
that currying trivially solves this particular problem. So I think  
that, as you say, skolemisation will do the trick.

Though I still haven't delved sufficiently into the article you cite  
at the top, to be sure that extensibility won't be curtailed by this  
approach. If it is, then existentials should do the job.