4

ステート トランスフォーマーを使用して、2D 再帰ウォークのすべてのポイントでデータセットをランダムにサンプリングします。これにより、一緒に条件を満たしたサンプルの 2D グリッドのリストが出力されます。結果から遅延して取得したいのですが、私のアプローチでは、最初の結果を取得する前に、すべてのポイントでデータセット全体を使い果たします。

具体的には、次のプログラムを検討してください。

import Control.Monad ( sequence, liftM2 )
import Data.Functor.Identity
import Control.Monad.State.Lazy ( StateT(..), State(..), runState )

walk :: Int -> Int -> [State Int [Int]]
walk _ 0 = [return [0]]
walk 0 _ = [return [0]]
walk x y =
  let st :: [State Int Int]
      st = [StateT (\s -> Identity (s, s + 1)), undefined]
      unst :: [State Int Int] -- degenerate state tf
      unst = [return 1, undefined]
  in map (\m_z -> do
      z <- m_z
      fmap concat $ sequence [
          liftM2 (zipWith (\x y -> x + y + z)) a b -- for 1D: map (+z) <$> a
          | a <- walk x (y - 1) -- depth
          , b <- walk (x - 1) y -- breadth -- comment out for 1D
        ]
    ) st -- vs. unst

main :: IO ()
main = do
  std <- getStdGen
  putStrLn $ show $ head $ fst $ (`runState` 0) $ head $ walk 2 2

(x, y)プログラムは からまで長方形のグリッドをたどり、State モナドのリストの 1 つの値を含むすべての結果を合計します:状態を読み取って進める(0, 0)非自明なトランスフォーマー、または自明なトランスフォーマーのいずれかです。興味深いのは、アルゴリズムがとの先頭を超えて探索するかどうかです。stunststunst

提示されたコードでは、 がスローされundefinedます。これは、変換を連鎖させる順序の設計ミス、特に状態処理の問題であると考えましたunst。しかし、1D 再帰は、状態変換器を使用しても遅延を維持することがわかりました (幅ステップを削除し、ブロックを にb <- walk...交換します)。liftM2fmap

の場合、トリガーする前にグリッド全体をウォークするtrace (show (x, y))こともわかります。

$ cabal run
Build profile: -w ghc-8.6.5 -O1
...
(2,2)
(2,1)
(1,2)
(1,1)
(1,1)
sandbox: Prelude.undefined

ここでは私の使用に問題があると思いますが、モナドの選択とウォークの次元がその成功に影響するため、変換を行うことがそれ自体が厳密性の原因であるとはsequence広く言えません。sequence

ここで 1D 再帰と 2D 再帰の厳密さの違いの原因は何ですか? また、どうすれば必要な遅延を実現できますか?

4

2 に答える 2

1

KA Buhr によって受け入れられた答えは正しいです: 各方向に 1 つのステップの先頭を取得することは問題ありません (または のwalkいずれかで試してx < 2くださいy < 2) の暗黙の>>=inの組み合わせ、 の値の in 、および の値liftM2の状態依存関係は、に依存しますのすべての副作用。彼も指摘したように、実際に機能するソリューションは、実際に必要な依存関係によって異なります。sequenceabba

私の特定のケースの解決策を共有します。各walk呼び出しは、少なくとも呼び出し元の状態に依存し、おそらく他のいくつかの状態に依存します。これは、グリッドの事前注文トラバーサルと の代替に基づいていますst。さらに、質問が示唆するように、不要な代替手段をテストする前に、完全な結果を出したいと思いstます。これを視覚的に説明するのは少し難しいですが、これが私ができる最善の方法です: 左は変数の数を示していますst各座標での代替 (これは私の実際のユースケースで使用したものです) と右は、状態の望ましい依存関係順序の [かなり乱雑な] マップを示しています: 3D DFS で最初に xy を横断し、「x」深さ (最速の軸) として、「y」を幅 (中央の軸) として、最後に最も遅い軸 (白丸付きの破線で表示) として代替します。

ここに画像の説明を入力

元の実装での中心的な問題は、非再帰型の戻り値に対応するために、状態遷移のシーケンス リストから生じました。呼び出し元が依存関係の順序をより適切に制御できるように、リストの型をまとめて monad パラメーターで再帰的な型に置き換えましょう。

data ML m a = MCons a (MML m a) | MNil -- recursive monadic list
newtype MML m a = MML (m (ML m a)) -- base case wrapper

例[1, 2]:

MCons 1 (MML (return (MCons 2 (MML (return MNil)))))

Functor と Monoid の動作は頻繁に使用されるため、関連する実装を次に示します。

instance Functor m => Functor (ML m) where
  fmap f (MCons a m) = MCons (f a) (MML $ (fmap f) <$> coerce m)
  fmap _ MNil = MNil

instance Monad m => Semigroup (MML m a) where
  (MML l) <> (MML r) = MML $ l >>= mapper where
    mapper (MCons la lm) = return $ MCons la (lm <> (MML r))
    mapper MNil = r

instance Monad m => Monoid (MML m a) where
  mempty = MML (pure MNil)

2 つの重要な操作があります。2 つの異なる軸でステップを結合することと、同じ座標で異なる選択肢からのリストを結合することです。それぞれ：

  1. 図に基づいて、最初に x ステップから 1 つの完全な結果を取得し、次に y ステップから完全な結果を取得します。各ステップは、内部座標からの実行可能な選択肢のすべての組み合わせからの結果のリストを返すため、両方のリストでデカルト積を取得し、これも一方向にバイアスします (この場合は y 最速)。MML最初に、裸のリストの最後にベース ケース ラッパーを適用する「連結」を定義しますML。

    nest :: Functor m => MML m a -> ML m a -> ML m a
nest ma (MCons a mb) = MCons a (MML $ nest ma <$> coerce mb)

    次に、デカルト積:

    prodML :: Monad m => (a -> a -> a) -> ML m a -> ML m a -> ML m a
prodML f x (MCons ya ym) = (MML $ prodML f x <$> coerce ym) `nest` ((f ya) <$> x)
prodML _ MNil _ = MNil

  2. 異なる選択肢からのリストを 1 つのリストにまとめたいのですが、これが選択肢間の依存関係を導入することは気にしません。これはmconcat、Monoid インスタンスから使用する場所です。

全体として、次のようになります。

walk :: Int -> Int -> MML (State Int) Int
-- base cases
walk _ 0 = MML $ return $ MCons 1 (MML $ return MNil)
walk 0 _ = walk 0 0

walk x y =
  let st :: [State Int Int]
      st = [StateT (\s -> Identity (s, s + 1)), undefined]
      xstep = coerce $ walk (x-1) y
      ystep = coerce $ walk x (y-1)
     -- point 2: smash lists with mconcat
  in mconcat $ map (\mz -> MML $ do
      z <- mz
                              -- point 1: product over results
      liftM2 ((fmap (z+) .) . prodML (+)) xstep ystep
    ) st

headML (MCons a _) = a
headML _ = undefined

main :: IO ()
main = putStrLn $ show $ headML $ fst $ (`runState` 0) $ (\(MML m) -> m) $ walk 2 2

セマンティクスによって結果が変化したことに注意してください。私の目標は状態から乱数を引き出すことだけが必要であり、必要な依存関係の順序は、リスト要素を最終結果に正しくシェパディングすることで制御できるため、私には関係ありません。

(また、メモ化や厳密性への注意がなければ、この実装は大きな x と y に対して非常に非効率的であることも警告します。)

于 2020-03-12T06:04:45.070 に答える