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

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

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

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

问题描述

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

1
2
3
type Name = String
type Born = Int
data Fam = Fam Name Born [Fam]

如:

1
2
3
4
5
6
7
8
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。

解答

1
2
3
4
5
6
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]

结果

完美运行

1
2
3
4
5
6
*Main> family "E" fam
["C","C"]
*Main> family "C" fam
["A"]
*Main> family "A" fam
[]