何时使用Haskell monad
我在Haskell中实现了一个组合优化算法：
Given an initial candidate solution, repeat until stopping criteria are met:
1. Determine possible moves
2. Evaluate possible moves
3. Choose a move
4. Make move, record new candidate solution, update search state
我可以编写第1-4步的函数，并将它们链接在一个递归函数中，以处理循环和从一个迭代到下一个迭代的状态，但我有一个模糊的想法，monads适用。
在Haskell中表达这种程序的最好方法是什么？
在Haskell中表达这种迭代过程的最好方式是将每个连续结果的无限列表作为一个无限列表。 把你的四个步骤组合在一起就产生了从解决方案到不同（更好）解决方案的功能的概念; 你所需要做的就是无限次地应用这个。 你的函数的用户可以使用任何列表函数来得到答案： solve s0 !! numIterations solve s0 !! numIterations ，或find stoppingCondition $ solve s0 solve s0 !! numIterations find stoppingCondition $ solve s0 ，或任何你想要的。
为了得到这里，让我们写出每个函数的类型。
moves :: Solution -> [Move] 给出一个可能的解决方案，找出你可能做出的改变。
value :: Solution -> Move -> Double 给出一个解决方案和一个举措，评估它并将该值记录为一些实数。
choose :: Solution -> [Move] -> Move 给出一个解决方案和一系列的动作，选择最好的一个。
apply :: Solution -> Move -> Solution 鉴于此举，将其应用于现有解决方案以获得新解决方案。
你想用类型如solve :: Solution -> (Solution -> Bool) -> Solution来写一个函数，它需要一个初始解决方案和一个停止条件来执行你的算法。
相反，让我们将其作为一个无限的列表; 这意味着您只需删除谓词并具有Solution -> [Solution] 。
import Data.Ord
import Data.List
-- moves, value, and apply are domain-specific
choose :: Solution -> [Move] -> Move
choose s ms = maximumBy (comparing $ value s) ms
solve :: Solution -> [Solution]
solve = iterate $ s -> apply s . choose s $ moves s
在这里，关键是iterate :: (a -> a) -> a -> [a] ，它重复地将一个函数应用于一个值，并给出结果 - 完全是你的算法的描述。
但是，我真的写这个的方式如下：
import Data.Ord
import Data.List
solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply = iterate step
where step s = apply s . choose s $ moves s
choose s = maximumBy (comparing $ value s)
这样做的好处是，您可以对任何问题域重复使用相同的通用结构。 你所需要做的就是提供moves ， value和apply功能！ 根据我的心情，我可能会将其重写为：
import Control.Applicative
import Data.Ord
import Data.List
solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply = iterate step
where step = (.) <$> apply <*> choose <*> moves
choose = maximumBy . comparing . value
在这里，我们使用应用符号来说明我们实际上只是在一个上下文中(.) apply choose moves （这只是apply . choose $ moves ），其中每个函数都隐含地传递了一个参数s （读者应用） 。 如果我们真的想把事情弄清楚，我们可以写
import Control.Applicative
import Data.Ord
import Data.List
solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
solve moves value apply =
iterate $ (.) <$> apply <*> maximumBy . comparing . value <*> moves
这些片段中的任何一个都可以完全满足您的需求。 （Proviso：在你的任何函数中没有任何效果/ monad，所以随机性就出来了，尽管你很容易做到这一点。）
尽管如此，让我们考虑一下State单体。 这代表了一种具有某种环境的计算，因此State sa与s -> (a,s)同构s -> (a,s)可以看到状态并可能更新状态的东西。 在这里，函数签名左侧的所有Solution -> s将消失，右侧的-> Solution s将消失。 那会让你失望
moves :: State Solution [Move] value :: Move -> State Solution Double choose :: [Move] -> State Solution Move apply :: Move -> State Solution () 这意味着你会有一些单调的行动step ：
import Control.Applicative
import Control.Monad.State
import Data.Ord
import Data.List
choose :: [Move] -> State Solution Move
choose = let val m = do v <- value m
return (m,v)
in fst . maximumBy (comparing snd) <$> mapM val ms
step :: State Solution ()
step = apply =<< choose =<< moves
你可以让这个更加无点，或者像上面那样使它变得多态，但是我不会在这里做到这一点。 重点是，一旦你有了step ，你就可以用runState . last $ replicateM_ numIterations step生成答案runState . last $ replicateM_ numIterations step runState . last $ replicateM_ numIterations step ，或者给定一个whileM函数， runState $ whileM (stoppingCondition :: State Solution Bool) step 。 同样，用户可以决定如何停止它。 你的moves和value函数可能会用get :: State ss查询状态; apply可能会使用modify :: (s -> s) -> State s ()来调整状态而不需要将其拉回。 在这些类型中可以看到与上面的结构的相似性; 实际上，您也可以在step的定义中看到该结构。 每个人都说“串联apply ， choose / value ，并moves ”，这是您的算法的定义。
从这两个方面获得的信息是，您希望避免显式循环/递归，正如您正确实现的一样。 如果你认真考虑这个算法，那么State monad看起来就像是一个自然的结构，因为它隐藏了你正在考虑的那些命令性特征。 但是，它有缺点：例如，一切都变成了一元，而最糟糕的是，除apply之外的其他功能都能够更改保存的解决方案。 如果你想象这个算法每次都产生一个新的结果，你可以得到step :: Solution -> Solution的概念，并且从那里你可以使用iterate得到一个行为良好的无限列表。
下面是一个伪代码草图，说明如何使用State monad来通过计算对搜索状态进行线程化：
import Control.Monad.State
type SearchState = ...
type Move = ...
type Fitness = ...
determineMoves :: State SearchState [Move]
determineMoves = do
-- since determineMoves is in the State monad, we can grab the state here
st <- get
...
evaluateMoves :: [Move] -> [(Move, Fitness)]
evaluateMoves = ...
chooseMove :: [(Move, Fitness)] -> Move
chooseMove = ...
-- makeMove is not itself monadic, but operates on the SearchState
-- type we're threading through with the State monad
makeMove :: Move -> SearchState -> SearchState
makeMove m st = ...
loop :: State SearchState ()
loop = do
moves <- determineMoves
let candidates = evaluateMoves moves
move = chooseMove candidates
-- we pass a function (SearchState -> SearchState) to modify in
-- order to update the threaded SearchState
modify (makeMove move)
loop
请注意，即使您的主计算处于monad状态，并非每个组件都必须位于monad中。 在这里， evaluateMoves和chooseMove是非一元，和我用let你如何明确地将它们集成到一个do块。 然而，一旦你对这种风格感到满意，你可能会希望使用<$> （aka fmap ）和函数组合来更加简洁：
loop :: State SearchState ()
loop = do
move <- (chooseMove . evaluateMoves) <$> determineMoves
modify (makeMove move)
loop