了解Monadic斐波纳契
我正在学习haskell和学习单子。我看过和阅读各种教程和编码状态单子一些简单的例子,但我无法理解下面的一段代码(从哈斯克尔维基取):了解Monadic斐波纳契
import Control.Monad.State
fib n = flip evalState (0,1) $ do
forM [0..(n-1)] $ \_ -> do
(a,b) <- get
put (b,a+b)
(a,b) <- get
return a
我的问题归结为以下:
- 什么是在内部的第一条语句,即
(a,b)<-get
产生什么结果。对于一些具体的例子,a
和b
的值如何。 - 你为什么要在这里使用状态monad?
在此示例中,状态是包含序列中生成的前两个数字的对。这最初是(0, 1)
提供给evalState
。
类型的get
是MonadState s m => m s
这样在内部do
块
(a, b) <- get
取出的状态对和分别结合a
和b
到所述第一和第二元件。状态将在以下put
中更新。
状态将因此是:
(0, 1), (1, 1), (1, 2), (3, 2), (3, 5), ...
外
(a, b) <- get
return a
解包的最终状态值,并返回第一个元素。
首先让我们明确正在使用的斐波那契算法。这个想法是从元组(0, 1)
开始,然后找到下一个为(1, 0 + 1)
,下一个为(1, 1 + 1)
,(2, 2 + 1)
,(3, 3 + 2)
,依此类推。通常,步骤是\(a, b) -> (b, a + b)
。你可以看到在这些元组中是斐波那契数。
什么是内做的第一个语句,即没有(A,B)< -get导致成什么 里面去?
Haskell没有语句,只有表达式。
y <- x
不是一个完整的表达式。它类似于x >>= \y ->
。
y <- x
m
是一个完整的表达,相当于x >>= \y -> m
。一行n
非y <- n
的形式相当于_ <- n
(不包括let
行,也许有些我忘了)。
使用这个我们可以desugar do-notation。
fib n =
flip evalState (0, 1)
(forM
[0..(n-1)]
(\_ -> get >>= (\(a, b) -> put (b, a + b)))
>>= (\_ -> get >>= (\(a, b) -> return a)))
)
现在它只是大概的了解>>=
,return
,get
,put
,等等。
状态实际上只是s -> (s, a)
类型的函数。他们采取初始状态并产生下一个状态加上一些其他值。
m >>= n
又名“绑定”的类型为Monad m => m a -> (a -> m b) -> m b
。然后,如果我们的单子是State s
,这是一样的:
的由m
返回a
将被传递到n
。我们还能猜到什么?我们预计国家也会传递,所以m
返回的状态也必须传递给n
。函数m >>= n
必须返回n
返回的状态和值。然后,我们知道如何实现绑定:
m >>= n = uncurry (flip n) . m
return :: Monad m => a -> m a
然后将其等同于return :: a -> s -> (s, a)
:
return = flip (,)
get :: State s s
相当于get :: s -> (s, s)
:
get = join (,)
put :: s -> State s()
或put :: s -> s -> (s,())
:
put s _ = (s,())
evalState :: s -> State s a -> a
或evalState :: s -> (s -> (s, a)) -> a
:
evalState s f = snd (f s)
可以展开的所有定义,看看究竟是什么在发生的例子。尽管直觉应该就足够了。
forM
[0..(n-1)]
(\_ -> get >>= (\(a, b) -> put (b, a + b)))
我们不关心具有数字0
到n - 1
所以第一个参数被丢弃。 get
检索当前状态,然后put
写入新状态。我们这样做n
次。
>>= (\_ -> get >>= (\(a, b) -> return a)))
我们不关心累计值(这是单位),所以第一个参数被丢弃。然后我们得到当前状态并且只是项目的第一个元素。这是我们正在寻找的最终答案。
flip evalState (0, 1) …
最后我们运行从初始状态开始(0, 1)
。
我们可以对此实现进行一些清理。首先,我们不关心范围[0..(n-1)]
,我们只关心重复动作n
次。更直接的方式来做到这一点是:
replicateM n (get >>= \(a, b) -> put (b, a + b))
结果单元的列表,它是未使用的,所以更高效的版本是:
replicateM_ n (get >>= \(a, b) -> put (b, a + b))
已经存在的功能get
后面跟put
的共同格局,命名为modify
,定义为\f -> get >>= put . f
。因此:
replicateM_ n (modify (\(a, b) -> (b, a + b)))
再有就是部分:
>>= (\_ -> get >>= (\(a, b) -> return a)))
任何时候,我们不关心以前的结果,我们可以使用>>
。
>> get >>= (\(a, b) -> return a))
这就是:
>> get >>= return . fst
m >>= return . f
简化为fmap f m
:
>> fmap fst get
现在我们有,总数:
fib n =
evalState
( replicateM_ n (modify (\(a, b) -> (b, a + b)))
>> fmap fst get
)
(0, 1)
我们也可以使用,比较:
fib n =
fst
(evalState
( replicateM_ n (modify (\(a, b) -> (b, a + b)))
>> get
)
(0, 1)
)
然后因为我傻了:
fib =
fst
. flip evalState (0, 1)
. (>> get)
. flip replicateM_ (modify (snd &&& uncurry (+)))
你为什么要使用状态单子在这里?
你不会。这很清楚,因为我们只使用状态值;另一个值总是单位和丢弃。换句话说,我们只需要n
(即找到哪个斐波纳契数)在开始和之后我们只需要累加的元组。
有时您认为有一串组合,如h . g . f
,但您希望发送两个参数而不是一个参数。那是State
可能适用。
如果某些函数读取并且某些函数写入状态(第二个参数),或者两者都执行,那么State
就符合要求。如果只有读者,则使用Reader
,如果只有作者,则使用Writer
。
我们可以改变这个例子来更好地使用State Monad。我会让这个元组消失!
fib =
flip evalState 0
. foldr (=<<) (return 1)
. flip replicate (\x -> get >>= \y -> put x $> x + y)
所以文档状态:get :: m s -- Return the state from the internals of the monad
(见here)。
但我记得很清楚,当我试图将我的头包裹在State Monad上时,这并没有多大帮助。
我只能推荐在ghci中使用:i
和:t
,并测试不同的子表达式。只是为了感受它。像这样的位:
import Control.Monad.State.Lazy
runState (get) 0
runState (get >>= \x -> put (x+1)) 0
:t return 1 :: State Int Int
runState (return 1) 0
runState (return 1 >>= \x -> (get >>= \y -> return (x+y))) 0
-- Keeping a pair of (predecessor/current) in the state:
let f = (get >>= (\(a,b) -> put (b,a+b))) :: State (Int, Int)()
runState (f >> f >> f >> f >> f >> f) (0,1)
-- only keeping the predecessor in the state:
let f x = (get >>= (\y -> put x >> return (x+y))) :: State Int Int
runState (return 1 >>= f >>= f >>= f >>= f >>= f >>= f) 0
而且玩弄modify
,runState
,evalState
,execState
。
至于2),你......不会在实际的代码中,它只是一个玩具的例子。 –