随机走在尖头的容器上 [英] Random walk on a pointed container

问题描述

让我们考虑一个在隧道中游荡的矮人.我将定义一个代表这种矮人的类型.这样的情况:

Let us consider a dwarf wandering in a tunnel. I will define a type that represents this situation thusly:

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

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

在这里，您会在隧道的一部分中看到一个矮人:

Here you see a dwarf in a section of a tunnel:

λ display x
-*---

已发现指向容器是 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))
-*---
--*--
---*-
----*
-----

引人注目的是，该操作适用于任何尖头容器中的任意数量的矮人，因此可以根据需要扩展到整个矮人堡垒.我可以类似地定义一个函数可以向左或以其他任何确定性方式移动小矮人.

Spectacularly, this same operation works with any number of dwarves, in any pointed container, and so can be extended to a whole dwarf fortress if desired. I can similarly define a function that moves a dwarf leftwards, or in any other deterministic fashion.

但是现在，如果我想让我的矮人漫无目的地游荡怎么办?现在，我的随机移动" 必须仅当未在左侧处放置相同的侏儒时，才在右侧放置侏儒(因为这会 ，并且绝对不能将两个小矮人放在同一个地方(会使其中的一个变小).换句话说，随机移动" 必须是 linear (如线性逻辑" )应用于共形堡垒时.

But now what if I want my dwarf to wander around aimlessly? Now my "shift randomly" must only place a dwarf to the right if the same dwarf is not being placed to the left (for that would make two dwarves out of one), and also it must never place two dwarves in the same place (which would make one dwarf out of two). In other words, "shift randomly" must be linear (as in "linear logic") when applied over a comonadic fortress.

我想到的一种方法是为矮人分配某种状态，以跟踪可用状态移动一个矮人，当我们确定该位置是由他们之一采取.这样，其余的矮人将无法采取这一行动.或者我们可能会跟踪位置的可用性.我在想某种"monadic" extendM (它将与通常的 extend 进行比较，因为 traverse 与 fmap 进行比较.)但是我不知道任何现有技术.

One approach I have in mind is to assign some sort of state to dwarves that tracks the available moves for a dwarf, removing moves from every relevant dwarf when we decide that the location is taken by one of them. This way, the remaining dwarves will not be able to take that move. Or we may track availability of locations. I am thinking that some sort of a "monadic" extendM might be useful. (It would compare to the usual extend as traverse compares to fmap.) But I am not aware of any prior art.

推荐答案

解决此问题的最简单方法是使用

The easiest way to solve this is by using the MonadRandom library, which introduces a new monad for random computations. So let’s set up a computation using random numbers:

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

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

现在，如何应用这个东西?扩展它很容易:

Now, how to apply this thing? It’s easy enough to extend it:

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

但这并不完全有效:它为我们提供了一个随机值的容器，而我们需要一个随机值的容器.换句话说，我们需要找到可以执行 w(Rand b)->的操作.兰德(w b).实际上，确实存在这样的功能: sequenceA ！如文档所述，如果将 sequenceA 应用于 w(Rand b)，它将运行每个 Rand 计算，然后将结果累加到得到 Rand(wb)-这正是我们想要的！所以:

But this doesn’t quite work: it gives us a container of randomised values, whereas we want a randomised container of values. In other words, we need to find something which can do w (Rand b) -> Rand (w b). And in fact there does exist such a function: sequenceA! As the documentation states, if we apply sequenceA to a w (Rand b), it will run each Rand computation, then accumulate the results to get a Rand (w b) — which is exactly what we want! So:

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 中的每个值).

As you can see from the type signature above, this actually works for any Applicative (because all we require is that each applicative computation can be run in turn), but requires w to be Traversible (so we can traverse over each value in w).

(有关此类问题的更多信息，我建议此博客文章及其第二部分.如果您想了解上述技术的实际应用，建议您我自己的类型类.)

(For more on this sort of thing, I recommend 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.)

这样可以回答您一半的问题；就是说，如何通过共性获得概率性行为.下半部分是:

So that answers one half of your question; that is, how to get probabilistic behaviour using comonads. The second half is:

…而且它绝不能在同一位置放置两个矮人……

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

我不太确定，但是一种解决方案可能是将您的声波计算分为三个阶段:

This I’m not too sure about, but one solution could be to split your comonadic computation into three stages:

1. 将每个矮人概率性地转换为一个差异，说明该矮人是向左移动，向右移动还是停留.此操作的类型: mkDiffs :: X Dwarf->兰德(X DwarfDiff)
2. 执行每个差异，但保持原始的矮级位置.此操作的类型: execDiffs :: X DwarfDiff->X(DwarfDiff，[DwarfDiffed]).
3. 解决矮人相撞的情况.此操作的类型: resolve :: X(Dwarf，[DwarfDiffed])->兰德(X矮人).

上面使用的类型:

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非常好，但是同时更新多个值时很糟糕.问题是诸如 X 之类的符号是拉链，它们存储一个数据结构作为单个聚焦"值加上周围的上下文".就像我说的那样，这对于根据上下文更新关注的值非常有用，但是如果您需要更新多个值，则必须将计算拖入这个值+上下文的模型中……如上所述，这可能非常棘手.因此，comonads可能不是此应用程序的最佳选择.

---

As you can see, the above solution is pretty complicated. I have an alternate recommendation: don’t use comonads for this problem! Comonads are great for when you need to update one value based on its context, but are awful at updating multiple values simultaneously. The issue is that comonads such as your X are zippers, which store a data structure as a single ‘focused’ value plus a surrounding ‘context’. As I said, this is great for updating a focused value based on its context, but if you need to update multiple values, you have to shoehorn your computation into this value+context mould… which, as we saw above, can be pretty tricky. So possibly comonads aren’t the best choice for this application.

这篇关于随机走在尖头的容器上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！