5

私は現在、Haskell で実装したい 2 つのオートマトン学習アルゴリズムのニーズに適合するデータ構造を考え出そうとしています: RPNIとEDSM。

直観的には、ツリーに対するジッパーに近いものが理想的です。これらのアルゴリズムは、状態に対するある種の焦点 (ブルー フリンジ) を維持する状態マージ アルゴリズムであるため、興味深いポイントにすばやく到達するためにある種のジッパーが役立ちます。しかし、DFA (Determinist Finite Automaton) はツリーのような構造よりもグラフのような構造であるため、私はちょっと迷っています。遷移によって構造に戻ることができますが、ジッパーが正常に動作しない可能性があります。

私の質問は次のとおりです。高速な方法で操作できるように、DFA (または少なくともその遷移) をどのように表現しますか?

4

4 に答える 4

9

Haskell でのオートマトンの通常の不透明な表現から始めましょう。

newtype Auto a b = Auto (a -> (b, Auto a b))

これは、何らかの入力を受け取り、それ自体の新しいバージョンとともに何らかの出力を生成する関数を表します。便宜上、それはカテゴリと矢印です。また、アプリカティブ ファンクターのファミリでもあります。残念ながら、このタイプは不透明です。このオートマトンの内部を分析する方法はありません。ただし、不透明な関数を透過的な式の型に置き換えると、分析および操作できるオートマトンが得られるはずです。

data Expr :: * -> * -> * where
    -- Stateless
    Id      :: Expr a a

    -- Combinators
    Connect :: Expr a b -> Expr b c -> Expr a c

    -- Stateful
    Counter :: (Enum b) => b -> Expr a b

これにより、計算の構造にアクセスできます。これもカテゴリですが、矢印ではありません。矢印になると、どこかに不透明な機能があります。

于 2012-05-09T15:00:25.230 に答える
5

グラフを使用して開始できますか? fglパッケージは Haskell Platform の一部だと思います。

それ以外の場合は、'deriving (Data)' を使用して独自の構造を定義し、"Scrap Your Zipper"ライブラリを使用して Zipper を取得できます。

于 2012-05-09T14:57:46.337 に答える
0

手の込んだグラフ アルゴリズムが必要ない場合は、DFA をMap State State. これにより、アクセスと操作が高速になります。また、現在の状態を追跡することでフォーカスを得ることができます。

于 2012-05-18T22:11:23.847 に答える
0

regex-tdfaパッケージを見てみましょう: http://hackage.haskell.org/package/regex-tdfa

ソースはかなり複雑ですが、パフォーマンスを調整するためにタグ付けされた DFA を使用した正規表現の実装であるため、DFA を効率的に表現するためのいくつかの優れたプラクティスを示しているはずです。

于 2012-05-18T23:48:36.163 に答える