Haskell Instance of Show for user defined type - constructor not in scope

Question

Fairly new to Haskell and trying to wrap my head around user defined classes and, after lots of messing around and reading learnyouahaskell, I managed to define the following class for a binary tree:

data BTree a = EmptyTree | Node (BTree a) a (BTree a) deriving (Ord, Eq, Show)

{- compares value of new node x to root
if same, don't insert (no duplicates); if smaller, insert into left subtree lSub; if larger, insert into right subtree rSub -}
treeInsert :: (Ord a) => a -> BTree a -> BTree a
treeInsert x EmptyTree = Node EmptyTree x EmptyTree
treeInsert x (Node lSub root rSub)
    | x == root = Node lSub x rSub
    | x < root = Node (treeInsert x lSub) root rSub
    | x > root = Node lSub root (treeInsert x rSub)

--recurses over list of nodes to add
treeFromList :: (Ord a) => [a] -> BTree a -> BTree a
treeFromList [] tree = tree
treeFromList (node:nodes) tree = treeFromList nodes (treeInsert node tree)

The code above compiles, but when I try to run the following:

treeFromList [1,2,3]

I get an error saying "No instance for (Show (BTree Integer -> BTree Integer)) arising from a use of `print'"

So I tried to define some instances of show (working from a stack overflow post on a similar example)

instance Show (BTree a) where
    show (BTree a) = show a

instance Show EmptyTree where
    show (EmptyTree) = ""

instance Show (Node (BTree a) a (BTree a)) where
    show (Node (BTree a) b (BTree c)) = show BTree a ++ " " ++ b ++ " " ++ show BTree c

But the code doesn't compile and all of my reference to either BTree, Node, or EmptyTree give the error "Not in scope: data constructor"

I can't figure out why they wouldn't be in scope, so I'm wondering if my definition of the instances are wrong somehow. Thanks in advance for any help

Answer 1

treeFromList [1,2,3]

No instance for (Show (BTree Integer -> BTree Integer)) arising from a use of `print'

This is because treeFromList takes two arguments.

λ> treeFromList [1,2,3] EmptyTree
Node EmptyTree 1 (Node EmptyTree 2 (Node EmptyTree 3 EmptyTree))

You probably want to rearrange treeFromList so that it only takes one argument and initially assumes an empty tree. For example like:

treeFromList :: (Ord a) => [a] -> BTree a
treeFromList [] = EmptyTree
treeFromList (node:nodes) = treeInsert node (treeFromList nodes)

or using a fold,

treeFromList :: (Ord a) => [a] -> BTree a
treeFromList = foldr treeInsert EmptyTree

Answer 2

You are confusing the type constructors (BTree), with the data constructors (EmptyTree and Node). If you define instance …, then you are on the type level, so instance Show EmptyTree makes no sense. You can only define this with BTree a (and you likely want to add a type constraint to a).

Furthermore in your defininition of show … = ... you are are working with values, so show (Node (BTree a) b (BTree c)) = … makes no sense either.

You thus can define an instance for Show as:

instance Show a => Show (BTree a) where
    show EmptyTree = ""
    show (Node a b c) = show a ++ " " ++ show b ++ " " ++ show c

Here we thus map EmptyTree to the empty string, and for a Node a b c with a and c values of the type BTree a, we return show a ++ " " ++ show b ++ " " + show c.

Note however that your implementation of Show will result in strings that are ambiguous, since different trees can return the same string.

That being said, defining an instance for Show (BTree a) will not solve the underlying problem. Indeed the reason it complains is not because it can not show a Show a => BTree a, the error says it can not display a BTree Integer -> BTree Integer, that is a function.

You should construct a tree with:

treeFromList [1,2,3] EmptyTree