[Haskell-cafe] Restricted type classes
wren ng thornton
wren at freegeek.org
Tue Sep 7 00:24:35 EDT 2010
On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote:
>> Perhaps this just means that union/insert should be part of some other
> 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
> 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
More information about the Haskell-Cafe