haskell - 递归添加到二叉树

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。这是 GADT 的工作:

{-# 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” ”。