CODEWITHSUNDEEP
functionhaskelltypes
Daniel Porteous
Daniel Porteous

Reputation: 6343

How to define the types of parameters in a Haskell type constructor?

Imagine a standard construction of a Tree first:

data Tree k = Leaf | Node k (Tree k) (Tree k)

I want to implement a version of this where I deal with duplicate entries by counting them, so I have type like this:

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count)

Accordingly my code is:

tree_insert :: Ord k => k -> Tree k count -> Tree k count
tree_insert k Leaf = Node k 1 Leaf Leaf
tree_insert k (Node n count l r)
    | k == n = Node n (count+1) l r
    | k < n  = Node n count (tree_insert k l) r
    | k > n  = Node n count l (tree_insert k r)

If you try to use this code however, you will get the following error:

Could not deduce (Num count) arising from the literal ‘1’

To fix it I changed the type declaration for the function to this:

tree_insert :: (Ord k, Num count) => k -> Tree k count -> Tree k count

However down the line I ran into further problems. To me it seems like Haskell is telling me that, without the Num count, it doesn't know what type it is meant to be and therefore when I assign it as 1 in the first pattern, it produces the error. The Num count really doesn't seem like a good way to solve the problem. Ideally, I should be able to define what type count is when I make the initial type declaration, something like:

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count)
where count is Int

Obviously the above code is no good, but an example of the kind of thing I'm thinking of.

If what I want is possible, or less ideally if there is another way to approach this issue, I'd love to hear it. The emphasis is on definition of data types and functions and all, not just this specific problem.

Thanks!

Upvotes: 0

Views: 105

Answers (2)

chepner
chepner

Reputation: 531205

Your original tree type is already fully parametric in the type of data stored at each node; you can work with a tree that stores (k, Int) values instead of just k values.

data Tree k = Leaf | Node k (Tree k) (Tree k)

tree_insert :: a -> Tree (a, Int) -> Tree (a, Int)
tree_insert k Leaf = Node (k, 1) Leaf Leaf
tree_insert k (Node (n, count) l r)
  | k == n = Node (n, count+1) l r
  | k < n  = Node (n, count) (tree_insert k l) r
  | k > n  = Node (n, count) l (tree_insert k r)

Upvotes: 1

Alec
Alec

Reputation: 32309

Two alternatives here. The more straightforward one is to just not parametrize count over the Tree type.

data Tree k = Leaf | Node k Int (Tree k) (Tree k)

tree_insert :: Ord k => k -> Tree k -> Tree k
tree_insert ...

Alternately, if you envision yourself needing the more general tree type sometimes, you could stick with a type synonyn.

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count)
type TreeInt k = Tree k Int

tree_insert :: Ord k => k -> TreeInt k -> TreeInt k
tree_insert ...

Upvotes: 3

Related Questions