[Haskell-cafe] Restricted type classes

[wren ng thornton]

On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote:
>> Perhaps this just means that union/insert should be part of some other
>> class.
>
> That is part of the plan (I'm tentatively calling the class with the
> "insert" method "Buildable" or "Extendable"); this means that if a
> type is an instance of Monoid (for mempty), Buildable/whatever (for
> insert) and Foldable (for foldr), then we can possibly define a
> build-fusion rule

You don't need mempty for fusion. All you need is a basis case, and 
singleton can give that. Actually, you don't even need a base case, you 
just need an inductive step and a coinductive step. So, insert from 
Whatever and msplit from MonadLogic, for example. The trick is just that 
the insertion and the extraction must be "trivial" in the sense that you 
needn't store additional structure along the way; e.g., when folding a 
list there's no structure "above the head", i.e. outside of the 
top-level constructor and any recursive tails. For Data.Set that isn't 
the case, since there are constructors along the path from the root to 
the current element (even if all structure "before the head" has been GCed).

> (note: I dont' think this will work on Sets, etc.
> unless we have some way of guarantee-ing that the folding function is
> strictly monotonic).

You should only have to require that mapping functions are injective, 
and that folding functions are associative and commutative. 
Alternatively, that the folding function is associative, commutative, 
and idempotent. There's no need for the target domain to be ordered nor 
for the folding function to be monotonic in that order...


>> Of course, I'd expect singleton to obey the pointed law as well, so
>> that other class would (most likely) be a subclass of pointed functors. In
>> any case, it does mean there's something of a mismatch between singleton vs
>> return/pure/point/unit.
>
> Not quite sure what you mean by a "mis-match"

Just that they're not the same thing. For example, ZipList supports pure 
but it has no meaningful instance of singleton since every ZipList is 
infinite.

-- 
Live well,
~wren