13

問題

これを効率的に行うにはどうすればよいか、しばらく考えていましたが、何らかの理由で実行できませんでした。各フィールドにデータが含まれる長方形のグリッドをモデル化する必要があります。

ジッパーを介してアクセスする必要があります。ここで、フォーカスはフィールド (いわば値) です。ジッパーは、アクションgoDown、goUp、goLeftおよびをサポートする必要がありgoRightます。各アクションは、指定された方向にフォーカスをフィールドに変更するだけでなく、here現在フォーカスされているフィールドの値を返す必要があります。

これは で実行できますが、 のルックアップ時間は対数であるため、フォーカスの変更には の要素数である時間Mapがかかるという意味で非効率的です。log nnMapMap

指定されたアクションがO(1)時間内に機能する必要があります。

例

説明のために、以下のマトリックスを見てください。括弧内の数字は現在のフォーカスです。

1 (2) 3
4  5  6
7  8  9

私が申請した場合goRight、私は取得する必要があります:

1  2 (3)
4  5  6
7  8  9

今申し込んだ場合here、返される値は になります3。

質問

上記で説明したフォームのデータ型は、haskell ではどのように見えるでしょうか? 代数データ型として実現可能ですか?

4 つの方向すべてでのフォーカスの変更は、O(1)現在フォーカスされている値を読み取るだけでなく、時間内に実行できる必要があることに注意してください。

4

2 に答える 2

12

わかりました、この問題に対する「正しい」答えをまだ誰も与えていないことに失望しています。なぜなら、それが存在することは知っていますが、うまく説明することはできないからです。私の答えはhttp://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.htmlに基づいています

まず、標準の 1d ジッパーは次のようになります。

Data U x = U [x] x [x]

最初の要素は、フォーカスの「左」にあるすべての要素の逆リストであり、次にフォーカス要素、次にフォーカスの「右」にあるすべての要素のリストです。例えば：

U [-1,-2,-3] 0 [1,2,3]

次に、ジッパーを左右に動かします。私たちがグリッドの端から離れたときに何をすべきかを決めなければなりません。元の投稿では、コーナー ケースは読者の演習として残されるように、単純に無限グリッドを想定していました。

left  (U (a:as) x zs) = U as a (x:zs)
right (U as x (z:zs)) = U (x:as) z zs

コンテナのように見えるものはすべて Functor にする必要があります。

instance Functor U where
  fmap f (U a x z) = U (map f a) (f x) (map f z)

この時点で、私がやろうとしていることとその理由を誰かに説明してもらいたいと思います。Uのインスタンスを作成しますControl.Comonad。私が説明できる最善のことは、コモナドは裏返しのモナドのようなものだということです。1 つの要素を与えて、新しい値を持つコンテナーを作成するように求める代わりに(>>= :: Monad m => m a -> (a -> m b) -> m b)、Comonads は構造全体を与えて、フォーカスに属する値のみを要求します。(=>>) :: Comonad w=>w a -> (w a -> b) -> w

したがって、comonad-3.0.2 パッケージの Control.Comonad の条件を使用すると、次のようになります。

Instance Comonad U where
  -- extract :: U a -> a   -- called coreturn in the post
  extract (U _ x _) = x

  -- duplicate :: U a -> U (U a)  -- called cojoin in the post
  duplicate x = U (tail $ iterate left x) x (tail $ iterate right x)

duplicate は、Zippers の Zipper を提供し、それぞれが最後の要素よりも 1 つ多く左または右にシフトされます。膨大な量のメモリのように見えますが、Haskell はレイジーであり、実際のメモリ フットプリントは非常に小さく、完全なセットの場合は O(n)、まったく見回さない場合は O(1) のオーダーです。

しかし、これはすべて 1 つの次元にすぎません。繰り返しになりますが、これを 2 次元に拡張することを簡単に説明できるほど賢くありません。

data U2 x = U2 (U(U x))

instance Functor U2 where
  fmap f (U2 y) = U2 $ fmap (fmap f) y

instance Comonad U2 where
  extract (U2 y) = extract (extract y)
  duplicate (U2 y) = fmap U2 $ U2 $ roll $ role y where
    iterate' f = tail . iterate f
    role x = U (iterate' (fmap left) x) x (iterate' (fmap right) x)

複製関数は、適切にシフトされたグリッドのグリッドを作成するようになりました。そう

goLeft  u = let (U _ (U x _ _) _) = duplicate u in x
goRight u = let (U _ (U _ _ x) _) = duplicate u in x
goUp      = left  . duplicate
goDown    = right . duplicate
here      = extract

Haskell はレイジーなので、これらはすべて O(1) 関数です。さらに興味深いことにhere、時間とメモリの両方で O(1) コストを変更し、計算で近傍セルを使用できます。これにより、game of lifeセルオートマトンのようなものを実装するのと同じくらい簡単になります

rule  (U2 (U
      (U (u0:_) u1 (u2:_):_)
      (U (u3:_) u4 (u5:_))
      (U (u6:_) u7 (u8:_):_))) =
         let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in
           u4 && (n==2 || n==3) || (not u4) && n==3

-- assume u is the original graph each step is
step u = u =>> rule

上記のブログ投稿に加えて、Google で Comonad を検索して詳細を確認することをお勧めします。

于 2013-04-09T04:39:54.187 に答える
1

これはあなたが求めているものではないかもしれませんが、より良い答えを提案する理由を最初に聞きたいです。

data GridWithZipper a = GridWithZipper { grid :: [[a]]
                                       , gwzx :: Int
                                       , gwzy :: Int
                                       }

goLeft  gwz = gwz { gwzx = gwzx gwz - 1 }
goRight gwz = gwz { gwzx = gwzx gwz + 1 }
goUp    gwz = gwz { gwzy = gwzy gwz - 1 }
goDown  gwz = gwz { gwzy = gwzx gwz + 1 }

get gwz = grid gwz !! gwzx gwz !! gwzy gwz

すべての操作は明らかにO(1).

goただし、操作はすべてO(1)、取得と設定はO(sqrt(n))です。

于 2013-04-08T09:26:34.327 に答える