2

数式を操作するアルゴリズムを Haskell で実装しようとしています。私はこのデータ型を持っています:

data Exp = Var String | IVal Int | Add Exp Exp

私の質問にはこれで十分です。

一連の式変換が与えられた場合、たとえば次のようになります。

(ab を追加) => (ba を追加)

(Add (Add ab) c) => (Add a (Add bc))

x = (Add (Add xy) (Add zt)) のような式で、x の近傍にあるすべての式を見つけたいと考えています。x の近傍が y in Neighborhood(x) として定義されている場合、x から 1 回の変換で y に到達できる場合。

私はHaskellが初めてです。Haskell がこの仕事に適したツールであるかどうかさえ確信が持てません。

最終的な目標は、x と等価なすべての式のセットを返す関数 : 等価 x を取得することです。言い換えれば、x の近傍の閉包にあるすべての式のセット (変換のセットが与えられた場合)。

現在、私は次のものを持っています：

import Data.List(nub)
import Data.Set

data Exp = IVal Int
    | Scalar String
    | Add Exp Exp
    deriving (Show, Eq, Ord)

commu (Add a b) = (Add b a)
commu x = x
assoc (Add (Add a b) c) = (Add a (Add b c))
assoc (Add a (Add b c)) = (Add (Add a b) c)
assoc x = x

neighbors x = [commu x, assoc x]

equiv :: [Exp] -> [Exp]
equiv closure
    | closure == closureUntilNow = closure
    | otherwise = equiv closureUntilNow
    where closureUntilNow = nub $ closure ++ concat [neighbors x|x<-closure]

しかし、おそらく必要以上に遅く (nub は O(n^2))、いくつかの用語が欠落しています。

たとえば、f = (x+y)+z の場合、(x+z)+y などは得られません。

4

1 に答える 1

3

以下、輸入品等。multisetパッケージを使用します。

import Control.Monad
import Data.MultiSet as M

data Exp = Var String | IVal Int | Add Exp Exp deriving (Eq, Ord, Show, Read)

ちょっとした紙と鉛筆の作業は、次の事実を示しています: 葉のマルチセットが等しい場合、式e1とe2は関係の合同閉包にあります。Var葉とは、値と値を意味しIValます。たとえば、次の関数の出力です。

leaves :: Exp -> MultiSet Exp
leaves (Add a b) = leaves a `union` leaves b
leaves e = singleton e

したがって、これは、特定の値の近傍にあるすべての要素を (最初から重複を生成しようとせずに) きれいに生成する方法を示唆しています。まず、葉のマルチセットを生成します。次に、非決定論的にマルチセットのパーティションを選択し、再帰します。パーティションを生成するコードは次のようになります。

partitions :: Ord k => MultiSet k -> [(MultiSet k, MultiSet k)]
partitions = go . toOccurList where
    go [] = [(empty, empty)]
    go ((k, n):bag) = do
        n' <- [0..n]
        (left, right) <- go bag
        return (insertMany k n' left, insertMany k (n-n') right)

実際には、左と右の両方の部分が空でないパーティションのみが必要です。しかし、それらをすべて生成した後で確認します。の呼び出しごとに 2 つしかないので、安価ですpartitions。これで、一挙に近隣全体を生成できます。

neighborhood :: Exp -> [Exp]
neighborhood = go . leaves where
    full = guard . not . M.null
    go m
        | size m == 1 = toList m
        | otherwise = do
            (leftBag, rightBag) <- partitions m
            full leftBag
            full rightBag
            left  <- go leftBag
            right <- go rightBag
            return (Add left right)

ところで、すべての用語を取得していない理由は、再帰的で推移的な閉包を生成しているが、合同閉包を生成していないためです。最上位だけでなく、用語の奥深くで書き換えルールを適用する必要があります。

于 2014-06-17T01:58:52.277 に答える