在 Haskell 中包含随机数和列表的 State Monad。

Question

我正在学习我的函数式编程考试，仍在努力真正理解单子。有什么比自己定义一个更好的方法呢？我定义了这个：

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

基本上是把列表单子和随机单子结合在一起。 这个单子应该使您能够处理随机函数和列表。 现在出现了困难，因为我能够定义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页。

有什么需要解释的吗？

- Rich_Rich

---

你期望单子做什么？我认为你不能将这种类型转换为单子。 - Reid Barton

实际上，这种方法是相反的。你应该从你想要的行为开始，然后写下你需要实现它的类型。我的短语“将此类型转换为单子”是不好的。 - Reid Barton

我想要的行为是将这些函数链接在一起（从语义上看）：exmpl :: Int -> StdGen -> ([Int], StdGen) exmpl x gen = [y | y <- [x - 3 .. x + randomR (1, 10) gen] - Rich_Rich

f :: a -> ST a b，但是 x :: [a]。你不能将 f 应用于 x，所以你必须选择一个元素（哪一个？）或将其应用于一些或所有元素，并找出如何处理所有结果为 ST a b 的值。 - chepner

但是“像链条一样将函数 [...] 链接在一起”是什么意思呢？如果你理解了这句话的含义，那么写 (>>=) 就不会有问题了。 - Reid Barton

Answer 1

让我们小心地跟踪所有类型（当我编写复杂代码时，我会这样做）。首先，让我们为您的ST类型添加一个访问器，这将使事情变得更容易。

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

现在我们有runST :: ST a -> State -> ([a], State)。 在定义单子代码时，我喜欢立即将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)。我们可以通过使用f来获得b。我们现在有一个a列表，让我们尝试映射。

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

嗯，这并不是很有用，让我们尝试应用我们收到的状态：

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

也许我们可以用这个。我们有一个列表的列表，还有其他东西。我们把它命名为rs（代表“结果”）：

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

现在我们可以通过将所有结果的b连接起来来获取标签的列表：

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

因此，我们希望返回的是这个。现在我们要选择哪一个“State”呢？我们有一个问题，因为我们有很多不同的“State”可以选择。我们选择列表中的最后一个还是第一个？如果列表为空，也许我们只需返回输入的“State”。这些都是随意的选择——就像我的一位物理教授曾经说过的：“现在我们必须做出选择，这是一个问题，因为我们即将做出错误的选择。”这在函数式编程中非常真实；每当你不得不做出这样的任意选择时，你可能正在搞砸。

如果我们退后一步，直观地思考一下含义，“ST a”计算需要一个状态，并返回一个包含新状态的选择列表，每个选择都会产生一个选择列表和一个新状态。我们可以使用“concat”将所有列表组合在一起，但我们没有办法将所有状态组合成一个状态。对于随机API，我们没有这种方法（也许我们可以想象通过“bitxor”将所有状态结合在一起...）。

没有办法将状态组合起来，我们的单子绑定将不得不忘记大部分它所拥有的数据，这是它不遵守法律的相当迹象（虽然在这样复杂的单子中证明法律的复杂性令人担忧）。据我所知，也没有这种类型的单子。

有一个带有这个类型的单子：

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

这段话涉及到IT技术，它等同于“StateT State []”。现在，每个计算分支都有自己的随机状态，因此我们不再需要将许多状态合并为一个。你可以更好地定义这个Monad——像我一样写下你所知道的所有类型，并尝试以类型为导向的方式得到你需要的结果。尽量不要“忘记”任何信息，并努力在构建输出时仅使用每个输入一次。

抱歉，这篇文章有点含糊和冗长——我意识到我在定义monad时使用了很多直觉原则，所以我想尝试分享它们。记住，仅仅得到类型检查通过的定义是不够的（尽管这会让你走得更远）：还要检查法律，否则当你使用“do”符号等时可能会出现奇怪的问题。

- luqui

---

新类型 ST' a = ST' { runST' :: State -> [(a, State)] } - Daniel Wagner

使用 g (f:fs) s = let {(bs,s2) = f s ; (rs,sn) = g fs s2} in (bs++rs,sn) ; g [] s = ([],s) 处理 fs :: [State -> ([b], State)] 难道不是很自然吗？ - Will Ness

@WillNess, 啊，这很像“concatM”，非常有趣。我想知道这是否导致ST成为单子。 - luqui

更像是将 map f as 应用于 msum，如果我们定义 ST f <|> ST g = ST $ \s -> let (a, r) = f s; (b, q) = g r in (a ++ b, q)。 - Will Ness

@WillNess，又称 (<|>) = liftM2 (++) 在 State 中（取模新类型）。 - luqui

Answer 2

跟随luqui的方法，我们得到如下结果：

st >>= f = ST (g . runST st)
    -- runST st  :: State -> ([a], State)
    -- f         :: a -> ST b
    -- runST . f :: a -> State -> ([b], State)

    where
        g (a:as,s) = let  (bs, s2) = (runST . f) a s 
                          (rs, sn) = g (as, s2)
                     in   (bs ++ rs, sn) 
        g ([], s)  = ([], s) 

（未经测试）。

- Will Ness