CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41899

Haskell Type Variable

Learn You a Haskell creates a Tree Algebraic Data Type:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

My understanding is that a can be any type.

So I tried to create a treeInsert function that puts a Tree on the left or right side depending upon its Side value:

data Side = L | R

singletonTree :: a -> Tree a
singletonTree x = Node x EmptyTree EmptyTree

treeInsert :: a -> Tree a -> Tree a
treeInsert x EmptyTree = singletonTree x
treeInsert x@(L, _) (Node a left right) = Node a (treeInsert x left) right -- ERROR
treeInsert x@(R, _) (Node a left right) = Node a left (treeInsert x right)

But I got a compile-time error:

    Couldn't match expected type `a' with actual type `(Side, t0)'
      `a' is a rigid type variable bound by
          the type signature for treeInsert :: a -> Tree a -> Tree a
          at File.hs:10:15
    In the pattern: (L, _)
    In an equation for `treeInsert':
        treeInsert x@(L, _) (Node a left right)
          = Node a (treeInsert x left) right
Failed, modules loaded: none.

Perhaps a is still any type, but my pattern matching is invalid?

Upvotes: 3

Views: 618

Answers (2)

Ben
Ben

Reputation: 71400

treeInsert :: a -> Tree a -> Tree a

So treeInsert is going to get a value of any type, and a tree containing the same type, and result in a tree of the same type.

Your equations try to match x against the patterns (L, _) and the (R, _). But wait; the type said I could call it with any type I liked. I should be able to call it like treeInsert ["this", "is", "a", "list", "of", "String"] EmptyTree. How can I match something of type [String] against a pattern like (L, _); that only works for types of the form (Side, t0) (for any type t0).

Type variables like a are extremely flexible when you call the function; you can use any value at all of any type you like, and the function will just work.

But you're not calling treeInsert, you're implementing it. For the implementer, type variables like a are extremely restrictive rather than flexible. This is an inevitable trade off1. The caller gets the freedom to pick anything they want; the implementer has to provide code that will work for anything the caller might choose (even types that the caller's program made up long after you finish implementing your function).

So you can't test it against a pattern like (L, _). Or any other meaningful pattern. Nor can you pass it to any "concrete" function, only to other functions which will accept any possible type. So in fact in treeInsert with type a -> Tree a -> Tree a, there's no way to use any property at all of the values you're inserting to decide where they'll go; for any property you might like to use to decide whether to put it in the left or right tree, there's no guarantee that the property will be meaningfully defined.

You'll either need to do your insertion based on something you can examine (like the structure of the tree that's also passed in), or use a type that provides less flexibility to the caller and actually gives you some information about the values you're inserting, such as treeInsert :: (Side, t) -> Tree (Side, t) -> Tree (Side, t), as Ørjan Johansen suggested.

1 And that very restrictiveness is actually where Haskell as a whole gets a lot of its power, since a lot of really useful and generic code relies on what functions with certain types can't do.

Upvotes: 4

Ørjan Johansen
Ørjan Johansen

Reputation: 18189

Just because a can be any type in a Tree a in general, doesn't mean it can be any type in a tree passed to treeInsert. You need to refine it to a type that actually allows the (L, _) and (R, _) pattern matches on it.

In fact, you can delete the type annotation on treeInsert and it will compile, after which you can ask GHCi with :t for the correct type (and then re-add that annotation if you want):

treeInsert :: (Side, t) -> Tree (Side, t) -> Tree (Side, t)

Upvotes: 7

Related Questions