[Haskell-cafe] How to build an "Indicator Type" for a type class?
Brent Yorgey
byorgey at seas.upenn.edu
Tue Jun 1 21:59:30 EDT 2010
Perhaps something here may be of use?
http://okmij.org/ftp/Haskell/types.html#class-based-overloading
http://okmij.org/ftp/Haskell/types.html#class-based-dispatch
-Brent
On Mon, May 31, 2010 at 01:32:18PM +0200, Steffen Schuldenzucker wrote:
> Dear Cafe,
>
> let:
>
> > data True
> > data False
> >
> > class C a
>
> (arbitrary instances for C may follow)
>
> Now, how to obtain an "Indicator Type" for C, i.e. a type IndC that is defined
> via a type family / fundep / ... , so that
>
> IndC a = True forall a which are instances of C
> IndC a = False for all other a.
>
> I've collected some failed approaches here[1]. My key problem is that if I
> define (in the 3rd try):
>
> > instance (C a) => IndC3 a True
>
> , it does *not* mean "Define this instance for all a which are an instance of
> C", but "Define the instance IndC3 a True for all types a, but it's not gonna
> work if a is not an instance of C".
>
> Does anyone have another idea?
>
> Background:
>
> After having implemented type-level lists[2] and a quicksort on them[3], I'd
> like to have type-level sets. In their most simple implementation, sets are
> just (unsorted) lists like this:
>
> > data Nil
> > data Cons a b
> > class Elem x l
> (instances for Elem so that Elem x l iff x is an element of the list l)
>
> Now I want:
>
> > type family Insert x s :: *
>
> Insert x s = s forall (x, s) with (Elem x s)
> Insert x s = Cons x s for all other (x, s).
>
>
> Thanks a lot!
>
> Steffen
>
>
> [1] http://hpaste.org/fastcgi/hpaste.fcgi/view?id=25832#a25832
> [2] Kiselyov, Peyton-Jones, Shan: "Fun with type functions"
>
> http://research.microsoft.com/en-us/um/people/simonpj/papers/assoc-types/fun-with-type-funs/typefun.pdf
> [3] I rewrote this algorithm using type families instead of fundeps:
>
> http://www.haskell.org/haskellwiki/Type_arithmetic#An_Advanced_Example_:_Type-Level_Quicksort
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list