CODEWITHSUNDEEP
haskellbinary-search-tree
Phirip
Phirip

Reputation: 93

Binary Search Tree to list in Haskell

I've been given a BST in haskell that is capable of adding, removing, lookup, findingMax, and removingMax. I have to make a function that converts the data to a list structure.

bstToList:: (BST k v) -> [String]
bstToList EmptyBST = ["hi"]
bstToList (BSTNode k v nl nr) = bstToList nl ++ bstToList nr

The reason I have EmptyBST = ["hi"] in there was to check what it was returning. When given an input of 

bstToList (bstAdd 1 "Phil" (bstAdd 2 "Ip" EmptyBST))

returns a list of ["hi","hi","hi"] And I'm unclear as to why everything is returning the empty list. Assume that all functions other than bstToList is correct and working properly. Any help is appreciated!

Upvotes: 0

Views: 2310

Answers (1)

AndrewC
AndrewC

Reputation: 32455

The line 

bstToList (BSTNode k v nl nr) = bstToList nl ++ bstToList nr

doesn't use the value at the node, which is why you only ever get data from the EmptyBST bits.

You need

BstToList :: BST k v -> [v] 
bstToList EmptyBST = []
bstToList (BSTNode k v nl nr) = bstToList nl ++ [v] ++ bstToList nr

so that the value at this node is inserted between the values on the left and the right of it. (This is called an in order traversal.)

If you want to list both the keys and values you need

BstToList :: BST k v -> [(k,v)] 
bstToList EmptyBST = []
bstToList (BSTNode k v nl nr) = bstToList nl ++ [(k,v)] ++ bstToList nr

Notice the brackets around (k, v) - they turn two items into a pair. The same goes for the type signature. (The missing pair syntax is why you got a kind error.)

[k,v] can only work as data if k and v are the same type, and [k,v] can't work as a type.

Upvotes: 3

Related Questions