CODEWITHSUNDEEP
haskellfunctional-programmingbinary-tree
Pierre P.
Pierre P.

Reputation: 1065

Traversing a polymorphic finite binary tree

I have the following data type for my tree.

data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving ( Show )

I'd like to print a representation of a given tree using a left to right depth first traversal.

For the moment, I've decided to go with pattern matching. 

showt :: Tree a -> [Char]
showt ( Leaf a ) = [a]
...

When I try to run it using GHCi, here's the error I get

• Couldn't match expected type ‘Char’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          showt :: forall a. Tree a -> [Char]
        at 2016.hs:31:10
    • In the expression: a
      In the expression: [a]
      In an equation for ‘showt’: showt (Leaf a) = [a]
    • Relevant bindings include
        a :: a (bound at 2016.hs:32:14)
        showt :: Tree a -> [Char] (bound at 2016.hs:32:1)

I don't see where the problem comes from. Haskell should infer the type, no?

Upvotes: 1

Views: 225

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

Well it is not because a data Tree a = ... deriving Show, that it means that a is a Char.

It only means that Haskell has automatically added an type instance:

instance Show a => Show (Tree a) where
    -- ...

So as you can see, it adds a type constraint: a must be an instance of Show in order for Tree a to be an instance of Show. So our first conclusion is a can still be of any type.

Furthermore, even if a is an instance of Show, it does not mean that it is a String (or Char). It only means that there are some functions available like show :: (Show a) => a -> String.

So there some options here:

  • you add a type constraint, and use show:

    showt :: Show a => Tree a -> [Char]
showt ( Leaf a ) = show a
--- ...

  • you restrict yourself to trees of type String (or type Char):

    showt :: Tree Char -> [Char]
showt ( Leaf a ) = [a]
--- ...

Finally Haskell can infer the type of a function, but here you provide an explicit type signature. If you however omit the signature, you let Haskell derive it automatically:

Prelude> let showt ( Leaf a ) = [a]
Prelude> :t showt
showt :: Tree t -> [t]

Upvotes: 3

Related Questions