Nested/Sub data types in haskell

Question

So what would be nice is if you could do something like the following (not necessarily with this format, just the general idea):

data Sub = SubA | SubB
data Super = Sub | SuperB

isSub :: Super -> Bool
isSub Sub = True
isSub _ = False

So isSub SubA would report True (instead of an error.) At the moment you might do something like:

data Super = SubA | SubB | SuperB

isSub :: Super -> Bool
isSub SubA = True
isSub SubB = True
isSub _ = False

It's not terrible or anything, but it doesn't expand nicely (as in if Sub when up to SubZ this would be terribly clunky) and it doesn't allow you to add the Sub types to their own type-class. To avoid that problem you can wrap Sub:

data Sub = SubA | SubB
data Super = SuperA Sub | SuperB

isSub :: Super -> Bool
isSub (SuperA _) = True
isSub _ = False

But now you have to make sure to wrap your Subs to use them as a Super... again not terrible; just doesn't really express the semantics I'd like very well (i.e. Super can be any Sub or SuperB). The first (legal) example is "Super can be SubA..." and the second is "Super can be SuperA that takes a Sub..."

EDTI: Change some names to avoid conflation with music stuff.

P.S. Technically, this started when I was thinking about how to represent Scheme's numeric tower in Haskell... but I'm really more interested in the more general issue of representing "Type1 can be any of Type2 plus x, y, ...)

Answer 1

It's not terrible or anything, but it doesn't expand nicely

It would be fine if you used some Template Haskell. I'd look at the derive tool's makeIs routine for guidance.

But now you have to make sure to wrap your Subs to use them as a Super

No, the type system will tell you if you forgot. For example, if you have

data Super = Sub Sub | Super
data Sub = SubA | SubB

Then any context in which you use a Sub but expect a Super will be caught. I'm guessing you already know that so did you mean something else?

Answer 2

You can not have anything like

data Sub = SubA | SubB
data Super = Sub | SuperB

Suppose the above syntax is allowed, then the problem is given the value constructor SubA you can not tell whether its type is Sub or Super. That's why you need to wrap your type in a constructor.

For your second example, the way you are doing should be the default way of doing but you can do a hack to make it easier although I don't recommend doing this as using show is much slower. You can try some other hack similar to this.

import Data.List
data Super = SubA | SubB | SuperB deriving Show
isSub :: Super -> Bool
isSub m = isPrefixOf "Sub" (show m)

If you really want to have something like above it is better to define function like you did. Using TH might save you sometime.

Your third case is what I would really recommend doing. You need to have a wrapper constructor like SuperA because of the reasons I told above. That's why you can't have exactly type1 is of type2 plus x,y,z. The closest thing you can have is to wrap elements in a constructor or using a typeclass.

data Sub = SubA | SubB
data Sup = SuperA | SuperB

class Super a where
  isSub :: a -> Bool
  isSub _ = True

instance Super Sup where
    isSub _ = False

instance Super Sub

data SupSup = SuperSuperA | SuperSuperB

class SuperSuper a where
    isSuper :: a -> Bool
    isSuper _ = True


instance SuperSuper SupSup where
    isSuper _ = False

instance SuperSuper Sup
instance SuperSuper Sub

You can think here Super (which is a typeclass and not a type) contains Sub and someting extra (Sup).

Answer 3

You might want to look into using the lens (Control.Lens) library with their instances for Data.Data and Data.Typleable. Lens is an attempt to solve these type of multi level problems in lists, tuples and all other data types.

>data Sub =  SubA | SubB deriving (Show, Data, Typeable, Eq)
>data Super =  SuperA Sub | SuperB deriving (Show, Data, Typeable, Eq)

-- A little bit of a hack, there is probably a better way of doing this
>isSub' :: Sub -> Bool
>isSub' x = typeOf x == typeOf SubA

>tmp1 = SuperA SubA
>tmp2 = SuperA SubB

>isSub x = anyOf biplate (isSub') x

>isSub tmp1
True
>issub tmp2
True

isSub is really too general it checks to see if any of the children of the provided data type is of type Sub. So if you had a tree and in the tree was a Sub then it would be True. It should be possible to restrict this to only your use case however.

The advantage of the Lens library is now I can add another layer to the type hierarchy.

>data SuperSuper =  SuperSuperA Super | SuperSuperB | SuperSuperC Sub deriving (Show,Data,Typeable)

>tmp3 = SuperSuperA (SuperA SubA)
>tmp4 = SuperSuperC SubB

>isSub tmp3
True
>isSub tmp4
True