CODEWITHSUNDEEP
haskellbinary-search-tree
darrrrUC
darrrrUC

Reputation: 311

Recursively adding to binary tree

I'm trying to recursively add to a binary tree in Haskell. I'm following Learn You A Haskell on this, only with a few changes, but I'm getting errors, which I do not understand:

data Male = Male { maleName :: String
                 , maleDOB :: Int
                 } deriving (Show, Read, Eq, Ord)

data Female = Female { femaleName :: String
                     , femaleDOB :: Int
                     } deriving (Show, Read, Eq, Ord)

data FamilyTree a = EmptyTree 
                  | Node a (FamilyTree Female) (FamilyTree Male)
                  deriving (Show, Read, Eq, Ord)

singleton :: a -> FamilyTree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> FamilyTree a -> FamilyTree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node x left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)

Here is the error message I'm getting:

Couldn't match type `Female' with `Male'
Expected type: Male
  Actual type: a
In the first argument of `treeInsert', namely `x'
In the third argument of `Node', namely `(treeInsert x right)'
In the expression: Node a left (treeInsert x right)

I'm quite new to Haskell and can't wrap my head around what is happening here. Any pointer in the right direction would be welcome!

Upvotes: 3

Views: 243

Answers (1)

effectfully
effectfully

Reputation: 12715

When you write

treeInsert :: Ord a => a -> FamilyTree a -> FamilyTree a

the type system ensures that the type of the first argument equals the index of the second. It means that you can insert a Male only in a tree that starts from a Male. I guess, this is not what you want.

However it's a nice question and I'll answer it. The problem in

treeInsert :: Ord a => a -> FamilyTree a -> FamilyTree a

is that a is far to general. What would

treeInsert :: Int -> FamilyTree Int -> FamilyTree Int

mean? You need to restrict a to be either Female or Male. That's a job for GADTs:

{-# LANGUAGE GADTs #-}

data Person a where
    PFemale :: Female -> Person Female
    PMale   :: Male   -> Person Male

Person contains either Female or Male and carries at the type level information about which one. Having this we can define

runPerson :: Person a -> a
runPerson (PFemale x) = x
runPerson (PMale   x) = x

treeInsert :: Person a -> FamilyTree a -> FamilyTree a
treeInsert p              EmptyTree          = singleton (runPerson p)
treeInsert p@(PFemale x) (Node a left right)
    | x == a    = Node x left right
    | otherwise = treeInsert p left
treeInsert p@(PMale   x) (Node a left right)
    | x == a    = Node x left right
    | otherwise = treeInsert p right

The trick is that when you pattern match on Person a a gets instantiated either to Female or Male and never to something else. When a is Female, you continue to insert into the "Female" subtree, otherwise — into the "Male".

Upvotes: 2

Related Questions