[Haskell] Per-type function namespaces (was: Data.Set whishes)

[ozone at algorithm.com.au]

On 27/02/2004, at 4:48 PM, Brandon Michael Moore wrote:

> On Fri, 27 Feb 2004 ozone at algorithm.com.au wrote:
>
>> On 27/02/2004, at 1:13 PM, oleg at pobox.com wrote:
>>
>> 1) now I have to manually declare a class definition for every single
>> function, and I have to declare it in advance before any module 
>> defines
>> that function (most serious problem; see below),
>>
>> 2) I then have to declare instances of that type class for every
>> function I define,
>>
>> 3) the type signature for phase reveals no clues about how to use that
>> function.
>
> Declaring a type class instance is really no problem.

I agree that declaring a type class instance per function is not a huge 
deal (if it can be automatically done by the compiler).  However, 
declaring the instance first requires declaring the type class itself, 
and that _is_ a problem, because that's exactly what I'm trying to work 
around.  Without 20/20 hindsight, you cannot say with certainty what 
type signatures a "generic" function (like 'phase' or even 'add') can 
support, because it's not a generic function, it's a function which is

When you declare a type class, you are making a trade-off: you are 
saying that the interface for this function is forever set in stone, 
and it cannot be changed by any instances under any circumstances.  In 
return for saying that interface is immutable, you get two major 
benefits: (1) an immutable interface, i.e. so you can guarantee that 
whenever you use ==, you _know_ the type signature is :: Eq a => a -> a 
-> Bool, and no instance can try to subvert that (unless your name is 
Oleg ;), and (2) you get very powerful overloading capabilities.

However, the disadvantage of this tradeoff is that because the type 
signature is now set, you just used up another function name in the 
namespace.  So type classes are the wrong approach to solve this 
problem, because what I'm after is being able to clutter up a namespace 
as much as I like with whatever names I like, but I don't want a 
polymorphic function--I want a function which only operates on one 
specific, primary data type.

>> With the per-type namespace separation I'm advocating, you do not need
>> to know and declare in advance that each function "will be" 
>> overloaded,
>> you simply write a FiniteMap.add function and a Set.add function, and
>> you get a simpler form of namespace separation (or overloading) based
>> on the first parameter that's passed to it.  It is a solution which is
>> more _flexible_ than requiring type class definitions, and it is 
>> better
>> than having hungarian notation for functions.  In fact, I think that,
>> right now, if we replaced the current namespace separation offered by
>> the hierarchical module system, and instead only had this sort of
>> per-type namespace separation, things would still be better!
>
> How much of the structure of the first paramater would you look at? 
> Could
> you an implementation for pairs that depended on the actual types in 
> the
> pair? I think you should try to take advantage of the existing type 
> class
> machinery as much as possible here, even if what you want are not 
> exactly
> (standard) type classes.

The idea is if you write "fm.add", you look at the type of fm as much 
as possible.  If you see that fm is polymorphic, all bets are off, and 
the compiler raises an error and quits with prejudice.  If fm is 
monomorphic, you should be able to infer its type (which includes 
pairs/tuples) and thus know which namespace to select to find the 
correct add function.   So the main requirement for this to work is 
whether it's possible to infer the type of fm; since I'm not a type 
theorist, I have no idea if that is in fact possible at all.

>> I realise my idea isn't very general in that it only allows this
>> namespace lookup/overloading based on the type of a single argument
>> parameter, and I think it would be possible with a bit more thinking 
>> to
>> generalise it to work based on multiple arguments (e.g. via
>> argument-dependent lookup, or whatnot).  But even in its current form,
>> I honestly think it offers far more flexibility and would lead to
>> cleaner APIs than is currently possible.
>
> Read the paper and see if you think something like that might be 
> useful.
> In any case, I think there's a decent chance that something useful for
> this would also be useful for building interfaces to object-oriented
> libraries, and vicea versa. I think there's probably something that 
> covers
> both cases nicely and uniformly.

I've had a read of both the SPJ/Shields paper on OO-style overloading 
in Haskell, and I've also had a skim over another paper called "A 
Second Look at Overloading" which describes another overloading 
calculus called System O.  I don't think either paper directly 
addresses the problem I'm trying to solve, although some elements in 
the paper (e.g. closed classes) may provide a framework which is 
capable of addressing the problem, if something like fm.add can be 
translated to such a framework via major syntactic sugar :).


-- 
% Andre Pang : trust.in.love.to.save