[Haskell-cafe] Set Operations In Haskell's Type System

[Bartek Ćwikłowski]

hello,

2010/5/4 John Creighton <johns243a at gmail.com>:
> I will continue to try to solve the problem on my own but at the
> moment I'm able to get IsSuperSet to work but not the classes Isa,
> Child and IsSubSet to work. Unlike set theory IsSubSet is not the same
> as switching the order arguments in IsSuperSet because the searching
> is done in the opposite direction. In one case we are searching the
> parents and each child only has one parent. In the other Case we are
> searching the children and each parent could have multiple children).

Since Subset is the opposite of Superset, you can search in the
"easier" (up) direction, so it really is as easy as reversing the
order of arguments.

It's not possible to write class/type-level function Child a b | a ->
b, because functions (classes with fun-deps) must be deterministic. If
you want to enumerate all children (based on Parent class instances),
it's also impossible in this setup, it's probably possible with Oleg's
second-order typeclass programming[1].

[1] http://okmij.org/ftp/Haskell/types.html#poly2

But what are you actually trying to achieve? I can't thing of anything
useful that would require walking down the hierarchy tree (and
backtracking) and it has to be done at the type level.

Please use more descriptive type-variable names, type-level code
should also be easy to read:)

regards,
Bartek Ćwikłowski