组成哈斯克尔

Question

一个“名单表”我在这里相当多的初学者，我试图使关系正列表

funComp :: Ord a => [[a,a]] -> [[a,a]] -> [[a,a]] 
funComp [[a,b]] [[c,d]] 
| b == c = [[a,d]] 

为两个给定名单的组成（https://en.wikipedia.org/wiki/Composition_of_relations）例如，给定：

[[1,1],[1,2],[2,2],[2,3],[3,3],[3,4],[4,4]] 

和

[[1,4],[1,4],[2,3],[2,3],[3,2],[3,1],[4,1]] 

应该返回：

[[1,4],[1,4],[1,3],[2,2],[2,1],[3,2],[3,1],[4,1]] 

你是怎么做到的？

Answer 1

我在下面列出了一个完整的答案，希望您可能会发现它有帮助。我同意@erisco，如果你刚刚开始，这个问题可能会有点高级。你可能想从一些问题开始，只涉及使用一个列表/关系，而不是组合两个。 （例如，你将如何通过删除形式×R个X？中的所有元素作出关系自反你如何产生该组的所有值的ý使得X RŸ为固定值X ？您是否可以通过内置的Haskell函数和从头开始解决这些问题？）

无论如何，要开始，您可能会发现它有帮助，只是从更容易阅读的角度，使用元组来表示关系元素，所以你的两个例子关系如下：

r1 = [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4)] 
r2 = [(1,4),(1,4),(2,3),(2,3),(3,2),(3,1),(4,1)] 

你想要做的是构造是一个关系，它由从r1和r2的任何有序对元素创建的所有复合元素组成。这是诸如此类的事情列表理解是良好的：

result = [ combine x y | x <- r1, y <- r2 ] 

这个表达式创建每对x，y从两个关系运行combine x y的结果列表。 combine应该是什么？那么，它有两个元素，并生成它们的组成，所以你可能第一次尝试这样的：

combine (a,b) (c,d) | b == c = (a,d) 

这类型检查，但combine只是一个局部的功能 - 它没有价值对于那些对，不要”结合 - 所以这不会让你太过分。您需要一种编写combine的方法，如果存在，则允许您返回组合，否则不返回任何内容。

的标准方式在Haskell做，这是使用Maybe类型：

combine (a,b) (c,d) | b == c = Just (a,d) 
        | otherwise = Nothing 

这种类型的检查和运行，但result值的样子：

[Just (1,4),Just (1,4),Nothing,Nothing...] 

幸运的是，有一个功能在Data.Maybe中调用catMaybes，这正是我们在这种情况下所需要的 - 它将全部删除Nothing s并将Just值拉到一起，同时删除文字Just构造函数：

> catMaybes result 
[(1,4),(1,4),(1,3),...] 

有一些重复的应删除，让我们用删除它们nub从Data.List：

> nub (catMaybes result) 
[(1,4),(1,3),(2,3),(2,2),(2,1),(3,2),(3,1),(4,1)] 

，它看起来像你可能想要的答案，但我想你错过您的示例输出中为(2,3)。

完整的程序，稍微一概而论，看起来是这样的：

module Relations where 

import Data.List 
import Data.Maybe 

r1 = [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4)] 
r2 = [(1,4),(1,4),(2,3),(2,3),(3,2),(3,1),(4,1)] 

combine (a,b) (c,d) | b == c = Just (a,d) 
        | otherwise = Nothing 

funcComp r1 r2 
    = nub $ catMaybes [ combine x y | x <- r1, y <- r2 ] 

result = funcComp r1 r2 

如果您尚未：

• 获得至少考虑列表内涵的习惯，在任何情况下，你'从一个或多个现有列表生成项目
• 请阅读关键模块（如Prelude,Data.List和Data.Maybe）的文档，以便您熟悉那里可用的功能

Answer 2

很多关于“集合理解”的数学定义对列表理解具有相当直接的翻译。 （从左到右）关系组成的定义是：

R; S = {（x，z）|。 （X，Y）∈R，（Y，Z）∈S}

即，x由跳频至R一些Y，然后从跳频如果可以涉及到z在复合从X到Z的y到z到S.

您可以几乎准确地翻译此内容 - 我们只需要分解y的两个提及，因为您只能绑定到模式中的新变量。

compose r s = [ (x,z) | (x,y) <- r, (y',z) <- s, y == y' ] 

给它一个类型签名我会做一个类型的同义词，然后

type Relation a b = [(a,b)] 
compose :: Relation a b -> Relation b c -> Relation a c 

注意，这是许多定义组成相反的顺序。我只是把关系看作是一组对，它特别清楚这个方向，并且相反地混淆。 “试图做出关系的组成”