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

Based on the answers bellow and their comments: it looks like, exporting the top most type with some helper functions to create that type from the lower types is the best way of going about this. — Tom Carstens
– Tom Carstens, Commented Dec 17, 2012 at 7:48
Though it does seem that you'll need to have type-classes for your input types (So if SubA Int, SubB Float, and SuperB String; then you'll need a SubInput class instance for Int and Float and a SuperInput class instance for Int, Float, and String.) At the very least, these classes can be empty. But then you can have mkSub :: SubInput a => a -> Super — Tom Carstens
– Tom Carstens, Commented Dec 17, 2012 at 8:00
there isn't one anymore. i got the feedback i wanted... now for the hard part of figuring out which of the 2 answers is more of an answer... — Tom Carstens
– Tom Carstens, Commented Dec 18, 2012 at 5:06

Thomas M. DuBuisson · Accepted Answer · 2012-12-17 06:43:28Z

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?

answered Dec 17, 2012 at 6:43

Thomas M. DuBuisson

64.8k7 gold badges113 silver badges170 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Tom Carstens Over a year ago

No, that's what I meant. The type system will tell you, but you still have to do it (just a wording difference.) It's kind of annoying that you have to wrap the Sub type in vanilla Haskell, but I guess if I was doing this more I wouldn't mind using Template Haskell...

Thomas M. DuBuisson Over a year ago

You could make a CanBeSuper class with a mkSuper method. For example instance CanBeSuper Super where mkSuper = id and instance CanBeSuper Sub where mkSuper = Sub. Then all you need to do is apply mkSuper to the arguments - a where clause or the ViewPatterns extension would be best. The functions would then look something like someFunc (mkSuper -> s) = ....

Tom Carstens Over a year ago

I'm generally hesitant to use extensions, but that idea for a type-class is interesting. I'm going to play with the idea for a little while, see what happens when I go to 3 or 4 nested sub-types.

Thomas M. DuBuisson Over a year ago

I suspect the class solution will become cludgy in such a situation (but I'm not trying to discourage you from experimenting). This will be cleanest/most useful in cases where you have very few functions with many call sites and many different input types.

Satvik · Accepted Answer · 2012-12-17 07:27:35Z

0

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

edited Dec 17, 2012 at 7:27

answered Dec 17, 2012 at 6:45

Satvik

11.2k1 gold badge40 silver badges46 bronze badges

4 Comments

Tom Carstens Over a year ago

Technically, SubA would be both Sub and Super. But this gets us more into a set based type system... 1 issue with using type-classes like that would be that going from a depth of 2 to a depth of 3 ends up with a lot of extra work (Wrapping isn't much better though.)

Satvik Over a year ago

Technically haskell semantics does not allow SubA to be of both type. You can check declaring two data types with the same constructor. I don't see any problem with wrapping. You can use lenses if you are afraid of deeper levels modifications.

Tom Carstens Over a year ago

I know, I was merely saying that you'd need a set based type system to express SubA as both Sub and Super (which Haskell doesn't have.) Nor is there anything wrong with wrapping, it is what I would consider the best way of doing it. I was just curious about other ways to do it (for example, I was struggling to come up with a type-class implementation; so thanks for spelling that out... still thinking about how to expand it nicely without ending up having to do every combination of types and type-classes.)

Satvik Over a year ago

@TomCarstens I have expanded my typeclass example to additional level. But I myself don't like this solution as it does not allow you to group types. So you should better use the wrapper.

Davorak · Accepted Answer · 2013-01-03 01:46:15Z

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

Collectives™ on Stack Overflow

Nested/Sub data types in haskell

3 Answers 3

4 Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related