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

[Jacek Generowicz]

On 2010 Oct 14, at 05:39, Brandon Moore wrote:

> On Oct 13, 2010, at 7:44 PM, Jacek Generowicz <jacek.generowicz at cern.ch 
> > wrote:
>
>> On 2010 Oct 14, at 01:32, Evan Laforge wrote:
>>
>>>> I think I'm starting too see what my problem is. I think it boils  
>>>> down to
>>>> hankering for Duck Typing and variadic functions. I fully  
>>>> appreciate that
>>>> passing functions is a wonderful and powerful technique for  
>>>> catering for
>>>> variation, but Haskell's type system cramps my style by insisting  
>>>> that I
>>>> can't put a (Banana -> Cake) in the same container as an (Octopus  
>>>> ->
>>>> Truffles -> DogsBreakfast).
>>>>
>>>
>>> But the thing is, I don't use things like this, even in python.
>>
>>>
>> Shame. They're damn useful :-)
>>
>>> How are you expecting to call the functions in that container?   
>>> "for f in
>>> c: try: return f(*misc_args) except: pass"?
>>>
>>
>> to_do = [(call, (AuntMabel,)),
>>       (buy,  ([(12*kg, sugar), (6*bushel, wheat)])),
>>       (introduce, (Romeo, Juliet))]
>>
>> for do,it in to_do:
>>  do(*it)

> What is the point of doing that? If it's just to defer execution  
> until that loop, you should just rely on lazy evaluation, or [IO ()].

There's more to it than that: The point is to treat combinations of  
functions and other data (which may or may not come from different  
sources, but are brought together to make a coherent whole) as  
entities which are allowed to reside in the same variable or the same  
container.

Those other data might be the functions' arguments, or they might be  
other functions with which they are to be combined, or both.

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.

But what should the type of fn be? What should the type of args be? In  
Python, I don't care, as long no type error occurs when they are  
combined thus:

     fn(*args)

How do you let Haskell type check the combination of the types, rather  
than the individual types?

My answer seems to be: define a variant type for holding the  
combinations. The problem with this is that the set of allowed  
combinations is closed at library compile time. I want it to remain  
open for extension. In Duck Typing this happens trivially.

> If that's not the only thing you do, then the question is still how  
> you know enough about the structure of values In the list to do  
> anything useful with them.

There is a constraint on the *combination* of their types, while  
allowing the individual types to vary within that constraint. This  
constraint defines what I can do with them. Though, in practice, what  
I want to do with them defines the constraint.

(I guess that looking at how memoization is done in Haskell might  
teach me something relevant.)

> I suppose you haven't heard of parametricity theorems.

You suppose correctly :-)

> In Haskell, values have no hair. If you don't know anything about  
> the type of a values you can't inspect it. It's one of the major  
> tools that helps type signatures contribute to the correctness of  
> implementations.
> In Python, Java, and other similar languages there are lots of  
> things you can do with unknown values - get a string representation,  
> test for equality with another value, get the class it belongs to,  
> etc.
>
> So, we won't understand the point of your example without a little  
> more information on what you do to those heterogeneous values, and  
> how the program can tell which things to do wi which item,

Another example:

Let's say I need an Int -> String. Both

     (fnA2 :: Banana -> String) . (fnA1:: Int -> Banana)

and

     (fnB2 :: Onion -> String) . (fnB1 :: Int -> Onion)

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

     let (fn1, fn2) = pair in fn2 . fn1

is always

    Int -> String.

The whole thing could be summarized by saying:

       Please type check the whole, not the individual parts; let me  
store the parts in the same place.

> In Haskell it may be fun to turn on -XGADTs and write

Now you're just trying to burst my todo list, aren't you :-)

> data DelayedApp result where
> Base :: a -> DelayedApp a
> App :: DelayedApp (a -> b) -> a -> DelayedApp b
>
> but it turns out to be isomorphic to data DelayedResult r = DR a Nat
> - at least until you add some more data to the constructors.