Defining recursive data types with tuples in Haskell

Question

I'm having trouble defining a new data type in Haskell.

I'm trying to create a data type NumPair that will be a tuple containing either two integers, or an integer and another NumPair.

So for instance, (2, 2), (0, 5), (1, (2, 3)) and (0, (4, (3, 121))) should all be valid NumPairs.

This is the code I've written to try to do this:

data NumPair = (Int, Int) | (Int, NumPair) deriving (Eq, Show)

Can someone explain why this doesn't work and what I should do instead, please?

Answer 1

You need to add constructor names for each alternative:

data NumPair = Pair (Int, Int) | More (Int, NumPair) deriving (Eq, Show)

Those constructor names are what let you pattern match on the data type like so:

f :: NumPair -> A
f (Pair (x, y )) = ...
f (More (x, np)) = ...

You can then build a value using the constructors to (which is why they are called constructors):

myNumPair :: NumPair
myNumPair = More (1, More (2, Pair (3, 4)))

There are two other ways you can improve your type. Haskell constructors have built-in support for multiple fields, so rather than using a tuple you can just list the values directly in the constructor like this:

data NumPair = Pair Int Int | More Int NumPair deriving (Eq, Show)

Another way you can improve upon it is to recognize that you've just written the type for a non-empty list. The best implementation for non-empty lists resides in Data.List.NonEmpty of the semigroups package, which you can find here.

Then your type just becomes:

type NumPair = NonEmpty Int

... and you get a bunch of function on non-empty lists for free from that module.

Edit: n.m. brought to my attention that what you probably wanted was:

data NumPair = Pair (Int, Int) | More ((Int, Int), NumPair)

... which is equivalent to:

type NumPair = NonEmpty (Int, Int)

The difference is that this latter one lets you append pairs of integers, where as the previous one that followed your question's type only lets you append integers.