代码之家 › 专栏 › 技术社区 › coder_bro

如何从第一性原理导出状态单子?

state-monad monads haskell

coder_bro · 技术社区 · 7 年前

首先推导出单子的概念:

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=>

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需要定义为接受单个类型“ma”。

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) } m a -> (a -> m b) -> m b 绑定的

可作如下尝试:

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

上面没有定义bind,因为我不知道如何实现它。

我可以推导出为什么单子是有用的,并将其应用于第一个例子(也许),但似乎不能将其应用于状态。理解如何使用上面定义的概念导出状态Moand将是非常有用的。

请注意,我之前也问过类似的问题: Haskell - Unable to define a State monad like function using a Monad like definition

2 回复 | 直到 7 年前

melpomene 7 年前

你的合成函数 fex3 类型错误:

fex3 :: Int -> (Int, Int)

不像你的 sqrtInvLog' 例如 Maybe ', State 不会出现在 三氧化二铁

我们可以把它定义为

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

您的定义的主要区别在于 0 s .

如果(像你的 也许吧 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' 和类型。

这个 m 在定义中 单子的 m a , m b m = 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'
       }

cibercitizen1 7 年前

看一看 this

如果你有一个函数

ta -> tb

如果你想给它加上“state”,那么你应该传递这个state,然后

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

您可以将其转化为:

ta -> ts -> (tb, ts)

ta -> tb ,我们得到(加括号)

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

求和,如果函数返回 tb ta ta->结核 ),一个“有状态的” 它的版本将返回( ts -> (tb, ts) )从 助教 ta -> (ts -> (tb, ts)) )

因此,“有状态计算”(仅一个函数,或处理状态的函数链)必须返回/产生:

(ts -> (tb, ts))

这是int堆栈的典型情况。 [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]) . 所以我们想把这些基本操作结合起来

duplicateTop =
   v <- pop
   push v
   push v

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

让我们这样做(注意:这个定义与用于 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) )