1

私は次の命令型コードをHaskellの機能的なソリューションに変換しようとしています。セットのsメンバーをセットs'および更新セットのメンバーと比較し、その比較tにt'基づいて行いたい。命令型の擬似コードは次のとおりです。

-- s, s', t, t' are of type Data.Set a
-- foo x y returns a Just a or Nothing 
foo :: a -> a -> Just a

-- Initialize t and t' to s and s'
t = s
t = s'

foreach x in s
  foreach y in s'
      if (foo x y) == Just z
        insert z into t
        delete x from t
        delete y from t'

return (t, t')

私が望んでいるHaskell関数のタイプは次のようなものかもしれません。

mergeSets :: S.Set -> S.Set -> (S.Set, S.Set)
mergeSets s s' = ...

ここで、Sはtypeであり、関数の結果は新しいセットとData.Setのペアになります（またはセットとの両方を返す他の方法）。tt'tt'

4

2 に答える 2

4

1つの可能性があります：

bar s s' =
  foldl (\ (t,t') (z,(x,y)) -> 
              ( delete x (insert z t) , delete y t' ))
    (s,s')
    [(z,(x,y)) | x <- toList s, y <- toList s', Just z <- [foo x y]]

ここでの主な質問は、挿入と削除がforeachメカニズムに干渉することを意図していたかどうかです。上記はあなたがしなかったことを前提としています。

セットが大きい場合は、サンクの爆発を避けるために、厳密さを追加する必要があります。

bar s s' = foldl (\ (t,t') (z,(x,y)) ->
             let a=insert z t; b=delete x a; c=delete y t' 
             in a `seq` b `seq` c `seq` (b,c) )
    ....
于 2013-03-02T22:52:18.093 に答える
2

Set通常、要素にループを記述しないようなコレクションデータ型を使用している場合。これはリストに適しています。したがって、アルゴリズムですべての要素をネストされた方法で列挙する必要がある場合は、セットをリストに変換します。

したがって、ネストされたループアルゴリズムを完全にセットで使用することは避け、代わりに、セット操作（交差、和集合、差など）の観点から宣言型の仕様を探します。

それが不可能な場合は、リストへの素朴な翻訳が確かに可能です。

import qualified Data.Set as S

mergeSets :: Ord a => S.Set a -> S.Set a -> (S.Set a, S.Set a)
mergeSets s t = go1 (S.toList s) s t
    where
        go1 []     t t' = (t,t')
        go1 (x:xs) t t' = go1 xs u u'
            where
                (u, u') = go2 x (S.toList t) t t'

        go2 x []     t t'       = (t,t')
        go2 x (y:ys) t t'
            | Just z <- foo x y = go2 x ys (S.delete x (S.insert z t)) (S.delete y t')
            | otherwise         = go2 x ys t t'

-- for example
foo x y = if x == y then Just x else Nothing

簡単なことは、ネストされたループをモデル化することです。たとえばリスト内包表記を使用することもできます。ただし、アルゴは出力セットのミューテーションを使用するため、それを累積パラメーターとして渡す必要があります。

しかし、これをHaskellにうまく取り入れるためには、要素ごとの命令型スタイルを放棄し、自然なSetAPIの観点から作業する必要があります。それが素晴らしい解決策への道です。

于 2013-03-02T22:52:08.423 に答える