I've been stuck at this particular stage working on a problem I've been given, and my experience with haskell is still at a beginner level.
In trying to create a function to create a insert a Node (consisting of a String "Key" and a Value) into a Binary Search Tree, I attempted an approach using guard brackets. I seem to be misunderstanding how to do something here, and the error I am receiving doesn't make sense to me.
module Ex03 where
import Data.List ((\\))
-- Datatypes -------------------------------------------------------------------
-- do not change anything in this section !
-- Binary Tree
data BT a b
= Leaf
| Branch (BT a b) a b (BT a b)
deriving (Eq, Show)
-- association list
type Assoc a b = [(a,b)]
-- lookup binary (search) tree
lkpBST :: Ord a1 => BT a1 a -> a1 -> Maybe a
lkpBST Leaf _ = Nothing
lkpBST (Branch left k d right) k'
| k < k' = lkpBST left k'
| k > k' = lkpBST right k'
| otherwise = Just d
-- Coding Part 1 (13 Marks)
-- insert into binary (search) tree
insBST :: Ord a => a -> b -> BT a b -> BT a b
insBST labelX valueX Leaf = Branch Leaf labelX valueX Leaf
{-
insBST a 1 Branch Leaf b 1 Leaf
@?= Branch Branch Leaf a 1 Leaf b 2 Leaf
-}
insBST labelX valueX (Branch left labelRoot valueRoot right)
| valueX < valueRoot = (Branch (insBST labelX valueX left) labelRoot valueRoot right)
| valueX > valueRoot = (Branch left labelRoot valueRoot (insBST labelX valueX right))
| otherwise = Branch left labelX valueX right
-- Coding Part 2 (6 Marks)
-- convert an association list to a binary search tree
assoc2bst :: Ord a => Assoc a b -> BT a b
assoc2bst _ = error "assoc2bst not yet implemented"
-- Coding Part 3 (6 Marks)
-- convert a binary search tree into an (ordered) association list
bst2assoc :: Ord c => BT c e -> Assoc c e
bst2assoc _ = error "bst2assoc not yet
The error I am receiving is the following
Hours of hacking await!
If I break, you can:
1. Restart: M-x haskell-process-restart
2. Configure logging: C-h v haskell-process-log (useful for debugging)
3. General config: M-x customize-mode
4. Hide these tips: C-h v haskell-process-show-debug-tips
src/Ex03.hs:35:14: Could not deduce (Ord b) arising from a use of ‘<’ …
from the context (Ord a)
bound by the type signature for
insBST :: Ord a => a -> b -> BT a b -> BT a b
at /Users/eoindowling/college/3year2/michaelmas/CS3016-_Introduction_to_Functional_Programming/CSU34016-1920/Exercise03/src/Ex03.hs:28:11-45
Possible fix:
add (Ord b) to the context of
the type signature for
insBST :: Ord a => a -> b -> BT a b -> BT a b
In the expression: valueX < valueRoot
In a stmt of a pattern guard for
an equation for ‘insBST’:
valueX < valueRoot
In an equation for ‘insBST’:
insBST labelX valueX (Branch left labelRoot valueRoot right)
| valueX < valueRoot
= (Branch (insBST labelX valueX left) labelRoot valueRoot right)
| valueX > valueRoot
= (Branch left labelRoot valueRoot (insBST labelX valueX right))
| otherwise = Branch left labelX valueX right
Compilation failed.
What is wrong with my guard statements here? I've seen similiar approaches and I don't understand what I am doing wrong.
You are comparing valueX and valueRoot, of type b. The error message says that doing so requires a constraint Ord b, but you only have a constraint Ord a.
Perhaps you meant to compare labelX and labelRoot (which have type a) instead?