Defining recursive data types with tuples in Haskell

11
votes

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?

2
haskell

2 Answers

17
votes

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.

5
votes

What you desire is a "true union" type, which is not present in Haskell. Haskell provides only tagged unions, where the programmer must attach additional information to all data. There are tradeoffs to using true unions vs tagged unions; I won't try to sell you one way or the other on that. However, you can define a type exactly as desired by using a language that provides true union types, such as Typed Racket.

#lang typed/racket

(define-type Num-Pair
  (Rec R
    (U (Pair Integer Integer)
       (Pair Integer R))))

(: foo Num-Pair)
(define foo '(0 . (4 . (3 . 121))))