在尖头容器上随机游走

Question

让我们考虑一个在隧道中徘徊的矮人。我将定义一个类型来表示这个这样的情况：

data X a = X { xs :: [a], i :: Int }

display :: X Bool -> IO ()
display X{..} = putStrLn (concatMap f xs) where { f True = "*" ; f False = "-" }

这里你看到隧道的一部分有一个矮人：

λ display x
-*---

发现a pointed container is an instance of Comonad。我可以用这个在这里定义一个模拟我的矮人向右移动的函数：

shiftRight :: X Bool -> Bool
shiftRight x@X{..} | let i' = i - 1 in i' `isInRange` x && xs !! i' = True
                   | otherwise = False

参见：

λ traverse_ display $ scanl (&) x (replicate 4 (extend shiftRight))
-*---
--*--
---*-
----*
-----

惊人的是，同样的操作适用于任何数量的矮人，在任何尖头容器中，如果需要，可以扩展到整个矮人堡垒。 我可以类似地定义一个函数将矮人向左移动，或以任何其他确定性方式移动。

但是现在如果我想让我的小矮人漫无目的地游荡怎么办？现在我的"shift randomly"必须如果同一个矮人没有被放在左边 （因为那样会从一个中生成两个矮人)，而且它绝不能将两个矮人放在同一个地方( 会使二分之一成为侏儒）。换句话说，"shift randomly" 必须是线性（如 "linear logic") 当应用于一个共同堡垒时。

我想到的一种方法是将某种状态分配给跟踪可用的矮人为矮人移动，当我们决定位置是被其中一个人带走。这样一来，剩下的矮人就无法接下那招了。或者我们可以跟踪位置的可用性。 我在想某种 "monadic" extendM 可能有用。 （它与通常的 extend 相比，就像 traverse 与 fmap 相比。） 但我不知道有任何现有技术。

Answer 1

解决此问题的最简单方法是使用 MonadRandom library, which introduces a new monad 进行随机计算。因此，让我们使用随机数进行计算：

-- normal comonadic computation
type CoKleisli w a b = w a -> b

-- randomised comonadic computation
type RCoKleisli w a b = w a -> Rand b

现在，如何应用这个东西？ extend 很容易：

halfApply :: Comonad w => (w a -> Rand b) -> (w a -> w (Rand b))
halfApply = extend

但这并不完全有效：它给了我们一个随机值的容器，而我们想要一个随机值的容器。换句话说，我们需要找到可以做w (Rand b) -> Rand (w b)的东西。而事实上确实存在这样一个函数：sequenceA！正如文档所述，如果我们将 sequenceA 应用于 w (Rand b)，它会运行每次 Rand 计算，然后累积结果以获得 Rand (w b) - 这正是我们想要的！所以：

fullApply :: (Comonad w, Traversible w, Applicative f)
          => (w a -> f b) -> (w a -> f (w b))
fullApply c = sequenceA . extend c

从上面的类型签名可以看出，这实际上适用于任何 Applicative（因为我们只需要每个应用计算可以依次运行），但需要 w 为 Traversible（因此我们可以遍历 w 中的每个值）。

（有关此类内容的更多信息，我推荐 this blog post, plus its second part. If you want to see the above technique in action, I recommend my own probabilistic cellular automata library, back when it still used comonads instead of my own typeclass。）

这样就回答了你问题的一半；也就是说，如何使用 comonads 获得概率行为。下半场是：

… and also it must never place two dwarves in the same place …

这个我不太确定，但一种解决方案可能是将您的共子计算分为三个阶段：

将每个矮人概率转换为一个差异，说明该矮人是向左移动、向右移动还是停留。此操作的类型：mkDiffs :: X Dwarf -> Rand (X DwarfDiff)
执行每个差异，但保持原始矮人位置。此操作的类型：execDiffs :: X DwarfDiff -> X (DwarfDiff, [DwarfDiffed]).
解决小矮人发生碰撞的情况。此操作的类型：resolve :: X (Dwarf, [DwarfDiffed]) -> Rand (X Dwarf).

上面使用的类型：

data Dwarf = Dwarf | NoDwarf
data DwarfDiff = MoveLeft | MoveRight | DontMove | NoDiff
data DwarfDiffed = MovedFromLeft | MovedFromRight | NothingMoved

我所说的示例：

myDwarfs = X [NoDwarf                ,Dwarf                     ,NoDwarf                                ,Dwarf                    ,Dwarf                     ,Dwarf      ] 0
mkDiffs myDwarfs
         = X [NoDiff                 ,MoveRight                 ,NoDiff                                 ,MoveLeft                 ,MoveRight                 ,DontMove   ] 0
execDiffs (mkDiffs myDwarfs)
         = X [(NoDiff,[NothingMoved]),(MoveRight,[NothingMoved]),(NoDiff,[MovedFromRight,MovedFromLeft]),(MoveLeft,[NothingMoved]),(MoveRight,[NothingMoved]),(DontMove,[MovedFromLeft])] 0
resolve (execDiffs (mkDiffs myDwarfs))
         = X [NoDwarf                ,NoDwarf                   ,Dwarf                                  ,Dwarf                    ,Dwarf                     , Dwarf     ] 0

如您所见，上述解决方案非常复杂。我有一个替代建议：不要使用 comonads 来解决这个问题！当您需要根据其上下文更新 one 值时，Comonads 很棒，但在 awful同时更新多个值。问题在于，诸如 X 之类的组合是 zippers，它将数据结构存储为单个“聚焦”值加上周围的“上下文”。正如我所说，这对于根据其上下文更新聚焦值非常有用，但是如果您需要更新多个值，则必须将您的计算硬塞进这个值+上下文模型中……正如我们在上面看到的那样，这可能非常棘手.所以可能 comonads 不是这个应用程序的最佳选择。

在尖头容器上随机游走

Random walk on a pointed container

haskell

comonad