如何从第一原则推导出状态单子？

Question

我正试图从函数组合的例子中得出一个 State Monad 的实现。这是我想出的：

首先推导出Monad的概念：

data Maybe' a = Nothing' | Just' a deriving Show

sqrt' :: (Floating a, Ord a) => a -> Maybe' a
sqrt' x = if x < 0 then Nothing' else Just' (sqrt x)

inv' :: (Floating a, Ord a) => a -> Maybe' a
inv' x = if x == 0 then Nothing' else Just' (1/x)

log' :: (Floating a, Ord a) => a -> Maybe' a
log' x = if x == 0 then Nothing' else Just' (log x)

我们可以有如下函数组合这些函数：

sqrtInvLog' :: (Floating a, Ord a) => a -> Maybe' a
sqrtInvLog' x = case (sqrt' x) of
                  Nothing' -> Nothing'
                  (Just' y) -> case (inv' y) of
                                Nothing' -> Nothing'
                                (Just' z) -> log' z

这可以通过分解 case 语句和函数应用程序来简化：

fMaybe' :: (Maybe' a) -> (a -> Maybe' b) -> Maybe' b
fMaybe' Nothing' _ = Nothing'
fMaybe' (Just' x) f = f x

-- Applying fMaybe' =>
sqrtInvLog'' :: (Floating a, Ord a) => a -> Maybe' a
sqrtInvLog'' x = (sqrt' x) `fMaybe'` (inv') `fMaybe'` (log')`

现在我们可以通过定义 Monad =>

将概念推广到任何类型，而不仅仅是 Maybe'

class Monad' m where
  bind' :: m a -> (a -> m b) -> m b
  return' :: a -> m a

instance Monad' Maybe' where
  bind' Nothing' _ = Nothing'
  bind' (Just' x) f = f x
  return' x = Just' x

使用Monad'实现，sqrtInvLog''可以写成：

sqrtInvLog''' :: (Floating a, Ord a) => a -> Maybe' a
sqrtInvLog''' x = (sqrt' x) \bind'` (inv') `bind'` (log')`

尝试应用概念来维护状态，我定义了如下所示的内容：

data St a s = St (a,s) deriving Show

sqrtLogInvSt' :: (Floating a, Ord a) => St a a -> St (Maybe' a) a
sqrtLogInvSt' (St (x,s)) = case (sqrt' x) of
                             Nothing' -> St (Nothing', s)
                             (Just' y) -> case (log' y) of
                                            Nothing' -> St (Nothing', s+y)
                                            (Just' z) -> St (inv' z, s+y+z)

无法使用上述定义来定义 monad，因为需要将 bind 定义为采用单一类型 "m a"。

第二次尝试基于 Haskell 的 State Monad 定义：

newtype State s a = State { runState :: s -> (a, s) }

首次尝试定义使用组合函数构建并保持状态的函数：

fex1 :: Int->State Int Int
fex1 x = State { runState = \s->(r,(s+r)) } where r = x `mod` 2`

fex2 :: Int->State Int Int
fex2 x = State { runState = \s-> (r,s+r)} where r = x * 5

组合函数：

fex3 x = (runState (fex2 y)) st where (st, y) = (runState (fex1 x)) 0

但是定义newtype State s a = State { runState :: s -> (a, s) }不符合bind

的m a -> (a -> m b) -> m b模式

尝试如下：

instance Monad' (State s) where
   bind' st f = undefined
   return' x = State { runState = \s -> (x,s) }

bind' 在上面未定义，因为我不知道如何实现它。

我可以得出为什么 monad 有用并将其应用于第一个示例（可能'），但似乎无法将其应用于 State。了解我如何使用上面定义的概念推导状态 Moand 将很有用。

请注意，我之前曾问过类似的问题：但我已在此处展开并添加了更多详细信息。

Answer 1

您的组合函数 fex3 类型错误：

fex3 :: Int -> (Int, Int)

与 Maybe' 的 sqrtInvLog' 示例不同，State 不会出现在 fex3 的类型中。

我们可以定义为

fex3 :: Int -> State Int Int
fex3 x = State { runState = \s ->
    let (y, st) = runState (fex1 x) s in
        runState (fex2 y) st }

与您的定义的主要区别在于，我们传递自己的状态 s.

，而不是将 0 硬编码为初始状态

如果（就像在您的 Maybe 示例中一样）我们想要组合三个函数怎么办？这里我只是复用 fex2 而不是引入另一个中间函数：

fex4 :: Int -> State Int Int
fex4 x = State { runState = \s ->
        let (y, st) = runState (fex1 x) s in
            let (z, st') = runState (fex2 y) st in
                runState (fex2 z) st' }

剧透：

通用版bindState可以提取如下：

bindState m f = State { runState = \s ->
    let (x, st) = runState m s in
    runState (f x) st }

fex3' x = fex1 x `bindState` fex2
fex4' x = fex1 x `bindState` fex2 `bindState` fex2

我们也可以从 Monad' 和类型开始。

Monad'定义中的m应用于一种类型参数（m a、m b）。我们不能设置 m = State 因为 State 需要两个参数。另一方面，部分应用对于类型是完全有效的：State s a 实际上意味着 (State s) a，所以我们可以设置 m = State s:

instance Monad' (State s) where
   -- return' :: a -> m a (where m = State s)
   -- return' :: a -> State s a
   return' x = State { runState = \s -> (x,s) }

   -- bind' :: m a -> (a -> m b) -> m b (where m = State s)
   -- bind' :: State s a -> (a -> State s b) -> State s b
   bind' st f =
   -- Good so far: we have two arguments
   --   st :: State s a
   --   f :: a -> State s b
   -- We also need a result
   --   ... :: State s b
   -- It must be a State, so we can start with:
       State { runState = \s ->
   -- Now we also have
   --   s :: s
   -- That means we can run st:
           let (x, s') = runState st s in
   --   runState :: State s a -> s -> (a, s)
   --   st :: State s a
   --   s :: s
   --   x :: a
   --   s' :: s
   -- Now we have a value of type 'a' that we can pass to f:
   --   f x :: State s b
   -- We are already in a State { ... } context, so we need
   -- to return a (value, state) tuple. We can get that from
   -- 'State s b' by using runState again:
           runState (f x) s'
       }

Answer 2

看看this。总结和扩展一下。

如果你有函数

ta -> tb

并想给它加上"state"，那么你应该传递那个状态，并且有

(ta, ts) -> (tb, ts)

你可以通过柯里化来改变它：

ta -> ts -> (tb, ts)

如果你将它与原来的ta -> tb进行比较，我们得到（添加括号）

ta -> (ts -> (tb, ts))

总结一下，如果一个函数returns tb来自ta（即ta -> tb），一个"stateful" 它的版本将从 ta（即 ta -> (ts -> (tb, ts))）

return（ts -> (tb, ts)）

因此，一个"stateful computation"（只有一个函数，或者是处理状态的函数链）必须return/produce这样：

(ts -> (tb, ts))

这是一个典型的整数栈。 [Int] 是州

pop :: [Int] -> (Int, [Int]) -- remove top
pop (v:s) -> (v, s)

push :: Int -> [Int] -> (int, [Int]) -- add to the top
push v s -> (v, v:s)

对于push，push 5的类型与pop :: [Int] -> (Int, [Int])的类型相同。所以我们想combine/join这个基本操作得到的东西为

duplicateTop =
   v <- pop
   push v
   push v

请注意，根据需要，duplicateTop :: [Int] -> (Int, [Int])

现在：如何将两个有状态计算结合起来得到一个新的？ 让我们开始吧（注意：这个定义与用于 monad (>>=) 的 bind 但它是等效的。

合并：

f :: ta -> (ts -> (tb, ts))

和

g :: tb -> (ts -> (tc, ts))

得到

h :: ta -> (ts -> (tc, ts))

这是h的构造（伪haskell）

h = \a -> ( \s -> (c, s') )

我们必须计算 (c, s') 的地方（表达式中的其余部分只是参数 a 和 s）。方法如下：

                   -- 1. run f using a and s
  l1 = f a         -- use the parameter a to get the function (ts -> (tb, ts)) returned by f 
  (b, s1) = l1 s   -- use the parameter s to get the pair that l1 returns ( :: (tb, ts) )
                   -- 2. run g using f output, b and s1
  l2  = g b        -- use b to get the function (ts -> (tb, ts)) returned by g
  (c, s') = l2 s1  -- use s1 to get the pair that l2 returns ( :: (tc, ts) )

如何从第一原则推导出状态单子？

How to derive a state monad from first principles?

haskell

monads

state-monad