状态Monad在Haskell中包含Random和List

Question

当我正在学习我的考试功能编程时,我仍然在努力真正理解 Monads.还有什么比自己定义一个更好的方法？我定义了这个:

newtype ST a = ST (State -> ([a], State))
type State = StdGen

基本上是List Monad和Random Monad合二为一.这个monad应该可以让你使用随机函数和列表.现在遇到了麻烦,因为我能够定义return函数,但是>>=并没有完全解决问题.

instance Monad ST where
    return a = ST $ \g -> ([a], g)
    -- M a -> (a -> M b) -> M b
    st >>= f  = ST $ \s -> 
                let (x,s') = st s 
                in (f x) s'

代码的灵感来源于本文第218页

有什么解释吗？

Answer 1

让我们注意所有类型（在编写棘手的代码时自己做）。首先，让我们为您的ST类型添加一个访问器，这将使事情变得更容易。

newtype ST a = ST { runST :: State -> ([a], State) }

现在我们有了runST :: ST a -> State -> ([a], State)。在定义monad代码时，我希望立即将其应用于runST所有ST值，因此我知道我真正使用的类型。

st >>= f = ST $ \s ->
    -- runST st  :: State -> ([a], State)
    -- f         :: a -> ST b
    -- runST . f :: a -> State -> ([b], State)
    -- s         :: State
    let (as, s') = runST st s in  -- I renamed x to as for readability
    -- as        :: [a]
    -- s'        :: State

现在我们需要一个([b], State)。我们可以b通过使用得到f。我们有一个的列表，a所以让我们尝试映射

    -- map (runST . f) as :: [State -> ([b], State)]

嗯，那不是那么有用，我们也尝试应用进入的状态：

    -- map (\a -> runST (f a) s) as :: [([b], State)]

也许我们可以解决这个问题。我们有的列表b，以及其他一些东西。让我们将其命名rs为“结果”：

    let rs = map (\a -> runST (f a) s) as in

现在，我们可以b通过将所有结果bs串联来获得s 的列表：

    let bs = concat (map fst rs) in  -- bs :: [b]

所以大概就是我们要返回的东西。现在State我们要搭配哪个？我们有一个问题，因为我们有很多不同State的选择。我们是选择列表中的最后一个还是第一个？如果列表为空，也许我们只是返回输入的State结果。这些都是任意选择-正如我的物理学教授曾经说过的：“现在我们必须做出选择，这是一个问题，因为我们要做出选择错误的一个”。在函数编程中，这是非常正确的。每当您必须做出这样的任意选择时，您可能都会陷入困境。

如果我们退后一步并直观地考虑其含义，则ST a计算将获取一个状态，并返回带有新状态的选项列表以用于将来的计算，每个选项都会产生一个选项列表和一个新状态。我们可以使用将所有列表组合在一起concat，但是我们没有办法将所有状态组合在一起。有了随机API，我们就没有这个了（我们可以想象也许bitxor将所有状态汇总在一起……）。

没有合并状态的方法，我们的monad绑定将不得不忘记它拥有的大多数数据，这是一个很好的信号，表明它不会遵守法律（尽管monad这么复杂，我担心证明法律的复杂性）。据我所知，没有这种类型的单子。

还有就是有单子此类型：

newtype ST' a = ST' { runST' :: State -> [(a, State)] }

它等效于StateT State []。现在，计算的每个分支都具有其自己的随机状态，因此我们不再需要将许多状态组合在一起。您可能会更好地定义此monad-像我一样做，写下您所知道的所有内容的类型，并尝试以类型定向的方式获得所需的内容。尽量不要“忘记”任何信息，并在构造输出时努力只使用一次每个输入。

抱歉，这篇文章有点含糊不清-我意识到在定义monad时我使用了很多直观的原理，所以我想尝试共享它们。记住，仅仅获得类型检查的定义是不够的（尽管这样做确实有很多帮助）：还检查法律，否则，当您使用do符号等时，您会发生奇怪的事情。