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

3
votes

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

2
haskelltypes
Go back to the first error shown - the problem seems to be because you've defined treeFromList as taking 2 inputs, a list and a tree, while calling it with just the first, list argument. So how do you want this function to behave? The name to me implies that it should take a list and output a tree, and the way you called it suggests you want it to work that way. But in this case your definition is wrong. (It looks to me that what you have should be a helper function internal to the function, and the main function should call that with EmptyTree as the second argument.) – Robin Zigmond
If you are interested, treeFromList is "just" execState . traverse (modify . treeInsert). – chepner
Or treeFromList = flip (foldl' (flip treeInsert)). – chepner

2 Answers

7
votes
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
6
votes

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