組成哈斯克爾

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 

注意，這是許多定義組成相反的順序。我只是把關係看作是一組對，它特別清楚這個方向，並且相反地混淆。 「試圖做出關係的組成」