递归添加到二叉树

Question

我正在尝试递归地添加到 Haskell 中的二叉树。我正在关注 Learn You A Haskell，只是做了一些更改，但我收到了我不理解的错误：

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)

这是我收到的错误消息：

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)

我对 Haskell 很陌生，无法理解这里发生的事情。欢迎任何指向正确方向的指针！

Answer 1

写的时候

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

类型系统确保第一个参数的类型等于第二个参数的索引。这意味着您只能在从 Male 开始的树中插入 Male。我猜，这不是你想要的。

不过这是一个很好的问题，我会回答的。

中的问题

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

就是a太一般了。什么会

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

是什么意思？您需要将 a 限制为 Female 或 Male。这是 GADTs:

的工作

{-# LANGUAGE GADTs #-}

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

Person 包含 Female 或 Male 并在类型级别上携带关于哪一个的信息。有了这个我们可以定义

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

诀窍在于，当您在 Person a 上进行模式匹配时，a 会被实例化为 Female 或 Male 而不会实例化为其他任何东西。当 a 为 Female 时，继续插入“Female”子树，否则 — 插入“Male”。

递归添加到二叉树

Recursively adding to binary tree

haskell

binary-search-tree