5

Haskell を使用してリストに推移閉包を生成する必要があります。

これまでのところ、私はこれを得ました：

import Data.List
qq [] = []
qq [x] = [x]
qq x = vv (sort x)

vv (x:xs) = [x] ++ (member [x] [xs]) ++  (qq xs)

member x [y] = [(x1, y2) | (x1, x2) <- x, (y1, y2) <- qq (y), x2 == y1]

出力 1:

*Main> qq [(1,2),(2,3),(3,4)]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

出力 2:

*Main> qq [(1,2),(2,3),(3,1)]
[(1,2),(1,3),(1,1),(2,3),(2,1),(3,1)]

問題は2番目の出力にあります。新しく生成されたリストで追加の推移閉包をチェックする代わりに、単に結果を返します。

Haskell コードのプロトタイプを作成するために、次のPython コードを使用しました。

def transitive_closure(angel):
    closure = set(angel)
    while True:
        new_relations = set((x,w) for x,y in closure for q,w in closure if q == y)
        closure_until_now = closure | new_relations    
        if closure_until_now == closure:
            break    
        closure = closure_until_now    
    return closure

print transitive_closure([(1,2),(2,3),(3,1)])

出力：

set([(1, 2), (3, 2), (1, 3), (3, 3), (3, 1), (2, 1), (2, 3), (2, 2), (1, 1)])

これは、Haskell 関数で必要な正しい出力です。

Haskell コードで同じことを行うには? if( Python コードから Haskell コードへのステートメントを再作成する必要があります)

4

2 に答える 2

1

あなたの haskell コードが何をすべきかまったくわからないので、あなたの Python コードを (できるだけ厳密に) 逐語的に haskell に翻訳しました。

import Data.List
transitive_closure angel 
    | closure_until_now == closure = closure
    | otherwise                    = transitive_closure closure_until_now

        where new_relations = nub [(x,w) | (x,y) <- closure, (q,w) <- closure, q == y] 
              closure = nub angel
              closure_until_now = closure `union` new_relations

Python を調べて、どの行が Haskell の何に対応するかを分析してみましょう。

closure = set(angel)=> closure = nub angel. nubはちょうどsetです。

while True:=>何もありません！Haskell には「while」ループがないため、再帰が唯一の選択肢です。

new_relations = set((x,w) for x,y in closure for q,w in closure if q == y)
closure_until_now = closure | new_relations

になる

new_relations = nub [(x,w) | (x,y) <- closure, (q,w) <- closure, q == y]
closure_until_now = closure `union` new_relations

本質的に同じこと。命令型言語のように「実行」されないため、宣言の順序は重要ではありません。

if closure_until_now == closure:
    break

になる

| closure_until_now == closure = closure

あなたは警備員に精通していると思います。そうでない場合は、私より前に多くの人がはるかに優れた説明を行っています. Python コードのセマンティクスは、「この条件が true の場合、ループを終了して 'リターン クロージャ' に進む」と述べています。Haskell にはループがないため、終了条件に遭遇すると、再帰する代わりに単純に値を返します。

closure = closure_until_now

になる

| otherwise                    = transitive_closure closure_until_now

終了条件を渡すと、Python はループを続行します。ループの次の反復では、 に設定した入力として 'closure' を使用しますclosure_until_now。したがって、Haskell バージョンでは、「ループ」(すなわち再帰関数) の次の「反復」がclosure_until_now入力として使用されます。

堅牢性を高めるには、Data.Setを使用する必要があります。唯一の問題Setは、リスト内包表記を使用できないことです。mapただし、リスト内包表記をs に簡単に置き換えることができますSet。

for = flip map
new_relations = nub $ concat $ concat $ 
                for closure (\(x,y) -> 
                    for closure (\(q,w) -> 
                                 if q == y then [(x,w)] else []
                                 )
                             )

ちょっとしたハックです。条件が真でない場合に「何も返さない」ためにリストを使用するだけです。この場合のようなものを使用する方がおそらく良いでしょうMaybe。

于 2013-10-06T22:05:22.643 に答える