[Haskell-cafe] Restricted type classes

[Ivan Lazar Miljenovic]

On 7 September 2010 14:24, wren ng thornton <wren at freegeek.org> wrote:
> 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.

I'm talking about the build-foldr fusion rule from A Shortcut to
Deforestation, which (in my admittedly brief search) seems to be the
easiest to adapt to a wide range of containers (assuming there is some
linearity involved).

Yes, for specific types without mempty, we can possibly define
specific fusion rules; but I'd like to be able to say "if we're doing
a foldr over a build from any sequential type to another sequential
type, then we can just fuse the intermediary type".

>> (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...

Well, even given those constraints: it's a bit hard to say
"Associative (a -> b), Communtative (a -> b), Idempotent (a -> b) =>
... " for a specific function...

>
>>> 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.

Huh; didn't know that ZipList did that.  OK, so there's a definite
mis-match between what we'd want a "singleton" function to do and what
pure appears to do.  How can we specify such a hierarchy given that
for the majority of containers they will be the same?

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com