Haskell 考试问题选解 + 结课有感

之前一直听叶同学说，Haskell 是个好东西。可我一直觉得反正我学函数式编程也没法用来做什么东西，于是就没有接触。直到我在报北大暑校时，发现其他课程要不就是太高级（大数据、人工智能之类的），要不就是报满了。最后只剩下函数式程序设计。我寻思着这课也没多少人报，而且因为是国际课程，收费也比 B 类普通课程高很多，其实一开始我是不太想报的。但觉得暑假不能什么也不学，总得学些什么东西吧，于是在各种机缘巧合中报了。

我现在完全不后悔当初的决定，甚至有些庆幸。Haskell 与普通的命令式语言很不一样，它有懒惰、纯净等特征。在写函数式程序的时候，思考的方式和一般的编程也是不一样的。就如同老师说的那样，管它好不好使，有趣就是了。随着上一周的过去，我在北大暑校的第一个考试也到来了。虽然前前后后只上了 6 节课（这是在我意料之外的，我报这门课的时候以为是上两整周），但也学到了不少东西。

所以这篇文章我是想从试卷中摘抄一个题目下来。为什么选这个题目呢，考试共有六道题，前五道题我在考试一半时就写完了，但最后一道题花了我剩下的一半时间。考完后我去问同学，他们也是这么说的（哦，当然排除北大的学霸们[捂脸]，他们考试一半的时候就都交卷走了）。下面进入正题。

问题描述

这是一个家庭树结构定义：

1
2
3

type Name = String
type Born = Int
data Fam = Fam Name Born [Fam]

如：

fam = Fam "A" 1900 [
    Fam "B" 1910 [],
    Fam "C" 1915 [
        Fam "D" 1925 [],
        Fam "E" 1930 [],
        Fam "F" 1940 []
        ]
    ]

问：请定义函数

1	family :: Name -> Fam -> [Name]

以查找给出名字的人所对应的所有家长（当该名字出现多次时，此人有多个家长）

问题解析

首先这是一个递归数据结构的问题，那么我就用递归来解决。基本思路是，f = [(在当前 Fam 的 [Fam] 下（即 family 函数的第二个参数 Fam 中的第三个数据 [Fam]）所有人是否存在 Name，若存在则返回当前 Fam 的 Name)] ++ f Name Fam。我认为这道题的主要难点是递归数据结构比较绕，容易绕晕。我一开始的思路也有些走歪，就是因为没有搞清楚函数的第二个参数 Fam 和 Fam 的第三个数据[Fam] 的关系。还有一点需要注意的是可能有重名的人，所以我这里用了 replicate 和 length 组合使用来返回多个 Name。

解答

family :: Name -> Fam -> [Name]
family _ (Fam _ _ []) = []
family n f = replicate (length $ filter (== n) child) name ++ concat (map (family n) fam)
    where
        Fam name _ fam = f
        child = [a | (Fam a _ _) <- fam]

结果

完美运行

*Main> family "E" fam
["C","C"]
*Main> family "C" fam
["A"]
*Main> family "A" fam
[]