haskell - Is there any type-algebra function mapping an ADT to the set of elements of that ADT? -

for simple adts, can obtain adt of sets of adt data set = full set (*repeated n times) | empty set(*repeated n times), n number of non terminal constructors of adt. more solid example, take nat:

data nat = succ nat | 0 

we can obtain type sets of nats follows:

data natset = full natset | empty natset 

so, example,

empty :: natset empty = empty empty  insert :: nat -> natset -> natset insert 0 (empty natverse)       = full natverse insert 0 (full natverse)        = full natverse insert (succ nat) (empty natverse) = empty (insert nat natverse) insert (succ nat) (full natverse)  = full (insert nat natverse)  member :: nat -> natset -> bool  member 0 (full natverse)        = true member 0 (empty natverse)       = false member (succ nat) (empty natverse) = member nat natverse member (succ nat) (full natverse)  = member nat natverse  main =     let set = foldr insert empty [zero, succ (succ zero), succ (succ (succ (succ (succ zero))))]     print $ member 0 set     print $ member (succ zero) set     print $ member (succ (succ zero)) set     print $ member (succ (succ (succ zero))) set     print $ member (succ (succ (succ (succ zero)))) set     print $ member (succ (succ (succ (succ (succ zero))))) set 

for other types, equally simple:

data bin = bin | b bin | c data binset = empty binset binset | full binset binset 

but types branch? isn't obvious me:

data tree = branch tree tree | tip data treeset = ??? 

is there type-algebraic argument maps adts adts of sets of type?

let's take @ set type.

data natset = full natset | empty natset 

there's natset inside one; 2 branches of sum type indicate whether current nat present in set. structural representation of sets. observed, structure of set depends on structure of values.

it's equivalent stream of booleans: test membership indexing stream.

data natset = natset bool natset  empty = natset false empty  insert z (natset _ bs) = natset true bs insert (s n) (natset b bs) = natset b (insert n bs)  (natset b _) `contains` z = b (natset _ bs) `contains` (s n) = bs `contains` n 

based on insight set membership indexing collection of booleans, let's pursue generic implementation of sets of values of types formed fixed point of polynomial functor (what's problem?).

---

first things first. observed, set's structure depends on type of things inside it. here's class of things can elements of set,

class el     data set     empty :: set     full :: set      insert :: -> set -> set     remove :: -> set -> set      contains :: set -> -> bool 

for first example, i'll modify natset above suit format.

instance el nat     data set nat = natset bool (set nat)      empty = natset false empty     full = natset true empty      insert z (natset _ bs) = natset true bs     insert (s n) (natset b bs) = natset b (insert n bs)      remove z (natset _ bs) = natset false bs     remove (s n) (natset b bs) = natset b (remove n bs)      (natset b _) `contains` z = b     (natset _ bs) `contains` (s n) = bs `contains` n 

another simple el instance we'll need later (). set of ()s either full or empty, nothing in between.

instance el ()     newtype set () = unitset bool     empty = unitset false     full = unitset true     insert () _ = unitset true     remove () _ = unitset false     (unitset b) `contains` () = b 

---

the fixed point of functor f,

newtype fix f = fix (f (fix f)) 

in instance of el whenever f instance of following el1 class.

class el1 f     data set1 f     empty1 :: el => set1 f (set a)     full1 :: el => set1 f (set a)     insert1 :: el => f -> set1 f (set a) -> set1 f (set a)     remove1 :: el => f -> set1 f (set a) -> set1 f (set a)     contains1 :: el => set1 f (set a) -> f -> bool  instance el1 f => el (fix f)     newtype set (fix f) = fixset (set1 f (set (fix f)))     empty = fixset empty1     full = fixset full1     insert (fix x) (fixset s) = fixset (insert1 x s)     remove (fix x) (fixset s) = fixset (remove1 x s)     (fixset s) `contains` (fix x) = s `contains1` x 

as usual we'll composing bits of functors bigger functors, before taking resulting functor's fixed point produce concrete type.

newtype = newtype k c = k c data (f :* g) = f :* g data (f :+ g) = l (f a) | r (g a) type n = k () 

for example,

type nat = fix (n :+ n) type tree = fix (n :+ (i :* i)) 

let's make sets of these things.

i (for identity) location in polynomial fix plug in recursive substructure. can delegate implementation of el_ fix's.

instance el1     newtype set1 = iset1     empty1 = iset1 empty     full1 = iset1 full     insert1 (i x) (iset1 s) = iset1 (insert x s)     remove1 (i x) (iset1 s) = iset1 (remove x s)     (iset1 s) `contains1` (i x) = s `contains` x 

the constant functor k c features no recursive substructure, feature value of type c. if c can put in set, k c can too.

instance el c => el1 (k c)     newtype set1 (k c) = kset1 (set c)     empty1 = kset1 empty     full1 = kset_ full     insert1 (k x) (kset1 s) = kset1 (insert x s)     remove1 (k x) (kset1 s) = kset1 (remove x s)     (kset1 s) `contains1` (k x) = s `contains` x 

note definition makes set1 n isomorphic bool.

for sums, let's use our intuition testing membership indexing. when index tuple, choose between left-hand , right-hand members of tuple.

instance (el1 f, el1 g) => el1 (f :+ g)     data set1 (f :+ g) = sumset1 (set1 f a) (set1 g a)     empty1 = sumset1 empty1 empty1     full1 = sumset1 full1 full1     insert1 (l x) (sumset1 l r) = sumset1 (insert1 x l) r     insert1 (r y) (sumset1 l r) = sumset1 l (insert1 y r)     remove1 (l x) (sumset1 l r) = sumset1 (remove1 x l) r     remove1 (r y) (sumset1 l r) = sumset1 l (remove1 y r)     (sumset1 l r) `contains1` (l x) = l `contains1` x     (sumset1 l r) `contains1` (r y) = r `contains1` y 

this enough sets of natural numbers. appropriate instances of show, can this:

ghci> let z = fix (l (k ())) ghci> let s n = fix (r (i n)) ghci> insert (s z) empty `contains` z false ghci> insert (s z) empty `contains` (s z) true ghci> empty :: set (fix (n :+ i)) fixset (sumset1 (kset1 (unitset false)) (iset1 (fixset (  -- infinity , beyond 

---

i still haven't answered original question, how should work product types? can think of few strategies, none of them work.

we make set1 (f :* g) a sum type. has pleasing symmetry: sets of sums products, , sets of products sums. in context of indexing idea, saying "in order bool out of set, have give index handle each of 2 possible cases", rather either b's elimination rule (a -> c) -> (b -> c) -> either b -> c. however, stuck when try come meaningful values empty1 , full1:

instance (el1 f, el1 g) => el1 (f :* g)     data set1 (f :* g) = lset1 (set1 f a) | rset1 (set1 g a)     insert1 (l :* r) (lset1 x) = lset1 (insert1 l x)     insert1 (l :* r) (rset1 y) = rset1 (insert1 r y)     remove1 (l :* r) (lset1 x) = lset1 (remove1 l x)     remove1 (l :* r) (rset1 y) = rset1 (remove1 r y)     (lset1 x) `contains1` (l :* r) = x `contains1` l     (rset1 y) `contains1` (l :* r) = y `contains1` r     empty1 = _     full1 = _ 

you try adding hacky empty , full constructors set1 (f :* g) you'd struggle implement insert1 , remove1.

you interpret set of product type pair of sets of 2 halves of product. item in set if both of halves in respective sets. sort of generalised intersection.

instance (el1 f, el1 g) => el1 (f :* g)     data set1 (f :* g) = prodset1 (set1 f a) (set1 g a)     insert1 (l :* r) (prodset1 s t) = prodset1 (insert1 l s) (insert1 r t)     remove1 (l :* r) (prodset1 s t) = prodset1 (remove1 l s) (remove1 r t)     (prodset1 s t) `contains1` (l :* r) = (s `contains1` l) && (t `contains1` r)     empty1 = prodset1 empty1 empty1     full1 = prodset1 full1 full1 

but implementation doesn't work correctly. observe:

ghci> let tip = fix (l (k ())) ghci> let fork l r = fix (r (i l :* r)) ghci> let s1 = insert (fork tip tip) empty ghci> let s2 = remove (fork tip (fork tip tip)) s1 ghci> s2 `contains` (fork tip tip) false 

removing fork tip (fork tip tip) removed fork tip tip. tip got removed left-hand half of set, meant tree left-hand branch tip got removed it. removed more items intended. (however, if don't need remove operation on sets, implementation works - though that's disappointing asymmetry.) implement contains || instead of && you'll end inserting more items intended.

finally, thought treating set of products set of sets.

data set1 (f :* g) = prodset1 (set1 f (set1 g a)) 

this doesn't work - try implementing of el1's methods , you'll stuck right away.

so @ end of day intuition right. product types problem. there's no meaningful structural representation of sets product types.

of course, academic really. fixed points of polynomial functors have well-defined notion of equality , ordering, can else , use data.set.set represent sets, product types. won't have such asymptotics, though: equality , ordering tests on such values o(n) (where n size of value), making membership operations on such sets o(n log m) (where m size of set) because set represented balanced tree. contrast our generic structural sets, membership operations o(n).