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

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

On 14 October 2010 08:34, Jacek Generowicz 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.