Haskell 家谱 - 考试准备

Question

我即将参加考试，需要有关家谱的考试问题的帮助。我以前做过树，但只有这种格式:

数据树 a = 空 |叶一个 |节点a(树a)(树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.

抱歉，这是我能画出的最好的论文中显示的树 - 但很明显，丹在最上面与多丽丝结婚，然后有 3 个 child jack 、克里斯汀和菲尔等。

所以我使用的树类型不能在这里使用，我想知道这次的类型定义是什么(基本上是问题2.(i)，以及(ii)的任何想法？

Answer 1

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

data Tree a = Node a [Tree a]

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

• 您需要区分已婚夫妇(有任意数量的 child )和单例(没有 child )的情况
• 您可能还想添加一棵空树

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