Haskell如何基于元组列表实现关系复合函数

你要实现的是二元关系的复合运算，以下是具体实现方法：

基础实现（列表推导式，最直观） #

列表推导式的语法和你给出的集合定义形式完全对应，代码如下：

relation :: [(Integer, Integer)] -> [(Integer, Integer)] -> [(Integer, Integer)]
relation r1 r2 = [(a, c) | (a, b1) <- r1, (b2, c) <- r2, b1 == b2]

代码解释： #

• 遍历r1的所有元组，通过模式匹配直接取出第一个元素a、第二个元素b1
• 遍历r2的所有元组，通过模式匹配直接取出第一个元素b2、第二个元素c
• 过滤条件b1 == b2对应定义里的「存在公共中间元素b」
• 最终返回所有满足条件的(a,c)元组构成的列表

基于fst/snd的等价实现 #

如果你还不熟悉模式匹配，也可以用Haskell内置的元组访问函数实现：

• fst：取二元组的第一个元素
• snd：取二元组的第二个元素
  对应代码如下：

relation :: [(Integer, Integer)] -> [(Integer, Integer)] -> [(Integer, Integer)]
relation r1 r2 = [(fst x, snd y) | x <- r1, y <- r2, snd x == fst y]

测试示例 #

你可以在ghci中运行以下测试验证正确性：

-- 测试用例
r1 = [(1,2), (3,4), (2,4)]
r2 = [(2,5), (4,6)]
-- 调用函数
relation r1 r2
-- 预期输出：[(1,5),(3,6),(2,6)]

内容的提问来源于stack exchange，提问作者proceeder