Haskell谱系树-考试准备

Question

我马上就要考试了，需要帮助解答一道关于家谱的考题。我以前做过树，但只是这种格式：

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

所以基本上是一棵树，它要么是空节点，要么是叶节点，或者是一个有两棵树递归跟随的节点。现在我被问到了这个问题：

                                DAN=DORIS

               /                   |                          \
        JACK-PEGGY            CHRISTINE-PAUL                PHIL-JILL 
      /     |     \                                      /    /     |     \  
 JENNIFER LILLIAN TONY                              SCULA KENTON DAVID ELIZABETH

This shows that Dan married Doris and their children were Jack (who married Peggy), 
Christine (who married Paul) and Phil (who married Jill). The children of Jack and Peggy 
were Jennifer, Lillian and Tony. Christine and Paul had no children. Phil and Jill’s 
children were Shula, Kenton, David and Elizabeth. 
Assume that any name appears in the tree at most once. Neglect the possibility of 
second marriages. 

(i) Give a Haskell algebraic datatype definition for family trees, and show how the 
    above tree would be represented using your datatype
(ii) Using your datatype definition, write a Haskell function which, given the name 
     of a person and a family tree, returns the names of that person’s children, if 
     any.

抱歉，这是我能画的最好的树了--但是很明显，Dan和Doris结婚了，然后有了三个孩子，Jack，Christine和Phil，等等。

Answer 1

树中的子代数量是可变的。标准库类型Data.Tree，对这样的树进行建模，大致如下：

data Tree a = Node a [Tree a]

这也适用于您的情况，除了

• 您需要区分一对夫妇(有任意数量的孩子)和一个人(没有孩子)的情况
• 您可能还想添加一个空树

因此，在不放弃太多的情况下，一棵树可以有三种形式:空的、有任意数量孩子的夫妇和没有孩子的单身者。把最后一句从英语翻译成Haskell，你就完成了。

Answer 2

import Data.Foldable as F

data Family a = Single a | Couple a a [Family a]
    deriving Show -- useful for ghci

isCouple :: Family a -> Bool
isCouple (Couple _ _ _) = True
isCouple _ = False

isFamily :: Eq a => a -> Family a -> Bool
isFamily n (Single a) = n == a
isFamily n (Couple a b _) = n == a || n == b

q1 :: Family String
q1 = Couple "Dan" "Doris" [Couple "Peggy" "Jack" [Single "Jennifer", Single "Lillian", Single "Tony"], Couple "Christine" "Paul" [], Couple "Phil" "Jill" [Single "Scula", Single "Kenton", Single "David", Single "Elizabeth"]]

q2 :: String -> Maybe [Family String]
q2 n = q2' n [q1]

q2' :: Eq a => a -> [Family a] -> Maybe [Family a]
q2' n f = case find (isFamily n) f of
    Just (Single _) -> Just []
    Just (Couple _ _ c) -> Just c
    _ -> case filter isCouple f of
        [] -> Nothing
        cs -> q2' n $ F.concatMap (\(Couple _ _ c) -> c) cs