40

私は大きな結び目を結ぶことを含むHaskellプロジェクトに取り組んでいます：グラフのシリアル化された表現を解析しています。各ノードはファイルにオフセットされており、そのオフセットによって別のノードを参照する場合があります。したがって、解析中にオフセットからノードへのマップを作成する必要があります。これは、do recブロック内で自分自身にフィードバックできます。

私はこれを機能させており、ちょっと-ちょっと-合理的に抽象化されて-風のStateTモナド変換子になっています：

{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}

import qualified Control.Monad.State as S

data Knot s = Knot { past :: s, future :: s }

newtype RecStateT s m a = RecStateT (S.StateT (Knot s) m a) deriving
  ( Alternative
  , Applicative
  , Functor
  , Monad
  , MonadCont
  , MonadError e
  , MonadFix
  , MonadIO
  , MonadPlus
  , MonadReader r
  , MonadTrans
  , MonadWriter w )

runRecStateT :: RecStateT s m a -> Knot s -> m (a, Knot s)
runRecStateT (RecStateT st) = S.runStateT st

tie :: MonadFix m => RecStateT s m a -> s -> m (a, s)
tie m s = do
  rec (a, Knot s' _) <- runRecStateT m (Knot s s')
  return (a, s')

get :: Monad m => RecStateT s m (Knot s)
get = RecStateT S.get

put :: Monad m => s -> RecStateT s m ()
put s = RecStateT $ S.modify $ \ ~(Knot _ s') -> Knot s s'

このtie関数は魔法が起こる場所です。呼び出しによってrunRecStateT値と状態が生成され、それを独自の未来としてフィードします。get過去と未来の両方の状態から読み取ることがputできますが、「現在」を変更することしかできないことに注意してください。

質問1：これは一般的にこの結び目を結ぶパターンを実装するための適切な方法のように見えますか？またはさらに良いことに、誰かがこれに対する一般的な解決策を実装しましたが、ハッキングを覗き見したときに見落としていましたか？モナドはおそらくもっとエレガントに見えたので（Dan Burtonからの同様の投稿Contを参照）、しばらくの間モナドに頭を打ちましたが、うまくいきませんでした。

完全に主観的な質問2：私の呼び出しコードが最終的にどのように見えるかについて私は完全にわくわくしていません：

do
  Knot past future <- get
  let {- ... -} = past
      {- ... -} = future
      node = {- ... -}
  put $ {- ... -}
  return node

ここでの実装の詳細は省略されています。明らかに重要な点は、pastand状態を取得し、letバインディング内futureでそれらをパターンマッチングして（または前のパターンを明示的に遅延させて）、気になるものを抽出してから、ノードを構築して更新する必要があることです。私の状態と最後にノードを返します。不必要に冗長に思えますが、特に、と状態を抽出するパターンを誤って厳密にすることがいかに簡単であるかが嫌いです。それで、誰かがより良いインターフェースを考えることができますか？pastfuture

4

5 に答える 5

8

私はいろいろと遊んでいます、そして私は何かを思いついたと思います...面白い。私はそれを「Seer」モナドと呼んでおり、（モナド操作とは別に）2つの基本的な操作を提供します。

see  :: Monoid s => Seer s s
send :: Monoid s => s -> Seer s ()

および実行操作：

runSeer :: Monoid s => Seer s a -> a

このモナドが機能する方法は、予見者がすべてをsee見ることができるようにし、予見者が他のすべての予見者に情報を「送信」して見ることができるようにすることです。いずれかの予見者が操作を実行するときはいつでも、送信されたすべての情報と送信されるすべての情報を見ることができます。つまり、特定の実行内で、どこでいつ呼び出しても、常に同じ結果が生成されます。別の言い方をすれば、それは「結ばれた」結び目への実用的な参照を取得する方法です。sendseeseesee

これは実際には、を使用するのと非常によく似てfixいますが、すべてのサブパーツが明示的にではなく、段階的かつ暗黙的に追加される点が異なります。明らかに、パラドックスが存在する場合、予見者は正しく機能せず、十分な怠惰が必要です。たとえば、see >>= send情報が爆発的に増加し、タイムループに陥る可能性があります。

ばかげた例：

import Control.Seer
import qualified Data.Map as M
import Data.Map (Map, (!))

bar :: Seer (Map Int Char) String
bar = do
  m <- see
  send (M.singleton 1 $ succ (m ! 2))
  send (M.singleton 2 'c')
  return [m ! 1, m ! 2]

私が言ったように、私はちょうどいじくり回しているので、これがあなたが持っているものよりも優れているかどうか、またはそれがまったく良いかどうかはわかりません！しかし、それは気の利いた、そして関連性があり、あなたの「結び目」状態がであるならば、Monoidそれはあなたにとってちょうど役に立つかもしれません。公正な警告：私はSeerを使用して構築しましたTardis。

https://github.com/DanBurton/tardis/blob/master/Control/Seer.hs

于 2012-06-19T01:39:23.343 に答える
8

実装に関しては、リーダーモナド（未来用）とステートモナド（過去/現在用）のコンポジションにします。その理由は、未来を一度だけ（でtie）設定し、それを変更しないためです。

{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}

import Control.Monad.State
import Control.Monad.Reader
import Control.Applicative

newtype RecStateT s m a = RecStateT (StateT s (ReaderT s m) a) deriving
  ( Alternative
  , Applicative
  , Functor
  , Monad
  , MonadPlus
  )

tie :: MonadFix m => RecStateT s m a -> s -> m (a, s)
tie (RecStateT m) s = do
  rec (a, s') <- flip runReaderT s' $ flip runStateT s m
  return (a, s')

getPast :: Monad m => RecStateT s m s
getPast = RecStateT get

getFuture :: Monad m => RecStateT s m s
getFuture = RecStateT ask

putPresent :: Monad m => s -> RecStateT s m ()
putPresent = RecStateT . put

2番目の質問に関しては、データフローを知ることが役立ちます（つまり、コードの最小限の例を用意する）。厳密なパターンが常にループにつながるというのは真実ではありません。確かに、非生成ループを作成しないように注意する必要がありますが、正確な制限は、構築する内容と方法によって異なります。

于 2012-06-18T20:21:21.890 に答える
8

このトピックに関する記事を「 Assembly: Circular Programming with Recursive do」というタイトルで書きました。そこでは、ノット タイイングを使用してアセンブラーを構築する 2 つの方法について説明しています。あなたの問題と同様に、アセンブラは、ファイル内で後で発生する可能性のあるラベルのアドレスを解決できる必要があります。

于 2012-06-18T20:12:41.263 に答える
1

最近、同様の問題がありましたが、別のアプローチを選択しました。再帰的なデータ構造は、データ型ファンクターの型固定小数点として表すことができます。データのロードは、次の 2 つの部分に分割できます。

  • ある種の識別子によってのみ他のノードを参照する構造にデータをロードします。この例でLoader Int (NodeF Int)は、 type の値のマップを構築する ですNodeF Int Int。
  • 識別子を実際のデータに置き換えて再帰的なデータ構造を作成し、結び目を結びます。この例では、結果のデータ構造は typeを持ち、後で便宜上Fix (NodeF Int)に変換されます。Node Int

適切なエラー処理などが欠けていますが、その考えは明らかなはずです。

-- Public Domain

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe (fromJust)

-- Fixed point operator on types and catamohism/anamorphism methods
-- for constructing/deconstructing them:

newtype Fix f = Fix { unfix :: f (Fix f) }

catam :: Functor f => (f a -> a) -> (Fix f -> a)
catam f = f . fmap (catam f) . unfix

anam :: Functor f => (a -> f a) -> (a -> Fix f)
anam f = Fix . fmap (anam f) . f

anam' :: Functor f => (a -> f a) -> (f a -> Fix f)
anam' f = Fix . fmap (anam f)

-- The loader itself

-- A representation of a loader. Type parameter 'k' represents the keys by
-- which the nodes are represented. Type parameter 'v' represents a functor
-- data type representing the values.
data Loader k v = Loader (Map k (v k))

-- | Creates an empty loader.
empty :: Loader k v
empty = Loader $ Map.empty

-- | Adds a new node into a loader.
update :: (Ord k) => k -> v k -> Loader k v -> Loader k v
update k v = update' k (const v)

-- | Modifies a node in a loader.
update' :: (Ord k) => k -> (Maybe (v k) -> (v k)) -> Loader k v -> Loader k v
update' k f (Loader m) = Loader $ Map.insertWith (const (f . Just)) k (f Nothing) $ m

-- | Does the actual knot-tying. Creates a new data structure
-- where the references to nodes are replaced by the actual data.
tie :: (Ord k, Functor v) => Loader k v -> Map k (Fix v)
tie (Loader m) = Map.map (anam' $ \k -> fromJust (Map.lookup k m)) m


-- -----------------------------------------------------------------
-- Usage example:

data NodeF n t = NodeF n [t]
instance Functor (NodeF n) where
    fmap f (NodeF n xs) = NodeF n (map f xs)

-- A data structure isomorphic to Fix (NodeF n), but easier to work with.
data Node n = Node n [Node n]
  deriving Show
-- The isomorphism that does the conversion.
nodeunfix :: Fix (NodeF n) -> Node n
nodeunfix = catam (\(NodeF n ts) -> Node n ts)

main :: IO ()
main = do
    -- Each node description consist of an integer ID and a list of other nodes
    -- it references.
    let lss = 
            [ (1, [4])
            , (2, [1])
            , (3, [2, 1])
            , (4, [3, 2, 1])
            , (5, [5])
            ]
    print lss
    -- Fill a new loader with the data:
    let
        loader = foldr f empty lss
        f (label, dependsOn) = update label (NodeF label dependsOn)
    -- Tie the knot:
    let tied' = tie loader
    -- And convert Fix (NodeF n) into Node n:
    let tied = Map.map nodeunfix tied'

    -- For each node print the label of the first node it references
    -- and the count of all referenced nodes.
    print $ Map.map (\(Node n ls@((Node n1 _) : _)) -> (n1, length ls)) tied
于 2012-07-26T10:01:34.513 に答える
0

Monad の使用量の多さに圧倒されます。私は過去/未来のことを理解していないかもしれませんが、レイジー + フィックスポイント バインディングを表現しようとしているだけだと思います。(間違っていたら訂正してください。) R=W でのモナドの使用法はちょっとおかしいですが、 で同じことができる場合、とRWSは必要ありません。物事を簡単にしないなら、モナドを使う意味はありません。(とにかく、時系列を表すモナドはごくわずかです。)Stateloopfmap

結び目を結ぶための私の一般的な解決策：

  1. すべてをノードのリストに解析し、
  2. そのリストを、Data.Vectorボックス化された (=lazy) 値への O(1) アクセス用に変換します。
  3. letまたは関数をfix使用してその結果を名前にバインドします。mfix
  4. パーサー内のその名前付きベクターにアクセスします。( 1を参照してください。)

sth を書いているブログのそのexampleソリューション。このような：

data Node = Node {
  value :: Int,
  next  :: Node
} deriving Show
…
tie = …
parse = …
data ParserState = …
…
example :: Node
example =
  let (_, _, m) = tie parse $ ParserState 0 [(0, 1), (1, 2), (2, 0)]
  in (m Map.! 0)

私はこのように書いたでしょう：

{-# LANGUAGE ViewPatterns, NamedFieldPuns #-}
import Data.Vector as Vector

example :: Node
example =
   let node :: Int -> Node
       node = (Vector.!) $ Vector.fromList $
                   [ Node{value,next}
                   | (value,node->next) <- [(0, 1), (1, 2), (2, 0)]
                   ]
   in (node 0)

またはそれより短い:

{-# LANGUAGE ViewPatterns, NamedFieldPuns #-}
import Data.Vector as Vector

example :: Node
example = (\node->(Vector.fromList[ Node{value,next}
                                  | (value,node->next) <- [(0, 1), (1, 2), (2, 0)]
                                  ] Vector.!)) `fix` 0
于 2012-07-15T23:34:37.093 に答える