如何从第一性原理推导一个状态单子? [英] How to derive a state monad from first principles?
问题描述
我试图提出一个从功能组合示例派生的State Monad的实现.在这里，我想出了什么:
I am trying to come up with an implementation of State Monad derived from examples of function composition. Here I what I came up with:
首先衍生出Monad的概念:
First deriving the concept of 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)
我们可以具有如下组成这些功能的功能:
We can have function that composes these functions as follows:
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语句和函数应用程序来简化此操作:
This could be simplified by factoring out the case statement and function application:
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 =>
Now we can generalize the concept to any type, instead of just Maybe' by defining a 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可以写为:
Using Monad' implementation, sqrtInvLog'' can be written as:
sqrtInvLog''' :: (Floating a, Ord a) => a -> Maybe' a
sqrtInvLog''' x = (sqrt' x) \bind'` (inv') `bind'` (log')`
尝试应用概念维护状态，我定义了如下所示的内容:
Trying to apply the concept to maintain state, I defined something as shown below:
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".
It is not possible to define a monad using the above definition as bind needs to be defined as taking in a single type "m a".
基于Haskell对State Monad的定义的第二次尝试:
Second attempt based on Haskell's definition of State Monad:
newtype State s a = State { runState :: s -> (a, s) }
首次尝试定义使用组合函数构建并保持状态的函数:
First attempt to define function that is built using composed functions and maintains state:
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的模式
But the definition newtype State s a = State { runState :: s -> (a, s) } does not fit the pattern of m a -> (a -> m b) -> m b of bind
可以尝试如下:
instance Monad' (State s) where
bind' st f = undefined
return' x = State { runState = \s -> (x,s) }
上面没有定义
bind'，因为我不知道如何实现.
bind' is undefined above becuase I did not know how I would implement it.
我可以得出单子为什么有用的原因，并将其应用于第一个示例(也许是)，但似乎无法将其应用于State.理解我如何使用上面定义的概念来推导州定律将很有用.
I could derive why monads are useful and apply it the first example (Maybe') but cannot seem to apply it to State. It will be useful to understand how I could derive the State Moand using concepts defined above.
Note that I have asked a similar question earlier: Haskell - Unable to define a State monad like function using a Monad like definition but I have expanded here and added more details.
推荐答案
您组成的函数fex3具有错误的类型:
Your composed function fex3 has the wrong type:
fex3 :: Int -> (Int, Int)
与您的Maybe的sqrtInvLog'示例不同，State不会以fex3的类型出现.
Unlike with your sqrtInvLog' example for Maybe', State does not appear in the type of 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硬编码为初始状态.
The main difference to your definition is that instead of hardcoding 0 as the initial state, we pass on our own state s.
如果(如您的Maybe示例中)我们想组成三个函数怎么办?在这里，我将重用fex2而不是引入另一个中间函数:
What if (like in your Maybe example) we wanted to compose three functions? Here I'll just reuse fex2 instead of introducing another intermediate function:
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' }
SPOILERS:
SPOILERS:
广义版本bindState可以按以下方式提取:
The generalized version bindState can be extracted as follows:
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'和类型开始.
We can also start with Monad' and types.
Monad'定义中的m应用于一种类型参数(m a，m b).我们无法设置m = State，因为State需要两个参数.另一方面，部分应用程序完全适用于类型:State s a的确表示(State s) a，因此我们可以设置m = State s:
The m in the definition of Monad' is applied to one type argument (m a, m b). We can't set m = State because State requires two arguments. On the other hand, partial application is perfectly valid for types: State s a really means (State s) a, so we can set 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'
}
这篇关于如何从第一性原理推导一个状态单子?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
