何时使用 Haskell monad

Question

我正在 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 编写函数，并将它们链接在一个递归函数中，以处理循环并将状态从一个迭代传递到下一个迭代，但我有一个模糊的想法，即单子适用。

在 Haskell 中表达这种过程的最佳方式是什么？

Answer 1

在 Haskell 中表达这种迭代过程的最佳方式是作为每个连续结果的无限列表。将四个步骤拼凑在一起会产生从一个解决方案到另一个（更好）解决方案的函数概念；您所需要做的就是无限多次应用此方法。然后，函数的用户可以使用任何列表函数来获取答案：solve s0 !! numIterations，或 findstoppingCondition $solve s0，或任何你想要的。

为了到达这里，让我们写出每个函数的类型。

1. 移动::解决方案-> [移动]
   给定一个可能的解决方案，找出你可以做出的可能的改变。
2. 值::解决方案->移动->双
   给定一个解决方案和一个步骤，对其进行评估并将该值记录为某个实数。
3. 选择::解决方案-> [移动]->移动
   给定一个解决方案和一系列动作，选择最好的一个。
4. 应用::解决方案->移动->解决方案
   给定一个移动，将其应用到现有的解决方案中以获得新的解决方案。

您想要编写一个具有类似 solve :: 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]，它重复将函数应用于某个值并给出结果 - 正是算法的描述。

然而，我真正编写的方式如下：

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   = (.) <
gt; apply <*> choose <*> moves
        choose = maximumBy . comparing . value

在这里，我们使用应用符号来表示我们实际上只是在执行 (.) apply selectmoves （这只是 apply .选择 $ 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 $ (.) <
gt; apply <*> maximumBy . comparing . value <*> moves

任何这些片段都可以完全满足您的需要。 （附带条件：您的任何函数中都没有效果/单子，因此随机性已经消失。不过，您可以轻松地创建这个单子。）

---

不过，为了好玩，让我们考虑一下 State 单子。这表示某种环境下的计算，因此 State s a 与 s -> 是同构的。 (a,s)——可以查看状态并可能更新它的东西。在这里，函数签名左侧的所有 Solution -> 都会消失，-> 也会消失。解决方案位于右侧。这将为您留下

1. moves :: State Solution [Move]
2. value :: Move ->状态解双
3. choose::[Move] ->状态解决方案移动
4. apply::Move -> State Solution ()

这意味着您将有一些单子操作步骤：

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) <
gt; mapM val ms

step :: State Solution ()
step = apply =<< choose =<< moves

您可以使其更加无点，或者如上所述使其具有多态性，但我不会这样做这里。重点是，一旦您有了 step，您就可以使用 runState 生成答案。最后 $replicateM_ numIterations 步骤，或给定一个 whileM 函数，runState $whileM (stoppingCondition :: State Solution Bool) 步骤。同样，用户可以决定如何停止它。您的 moves 和 value 函数可能会使用 get :: State s s 查询状态； apply 可能会使用 modify :: (s -> s) -> State s () 调整状态而不需要将其拉回。您可以看到这些类型与上面结构的相似之处；事实上，您也可以在 step 的定义中看到该结构。每个都说“串在一起 apply、choose/value 和 moves”，这是您的定义算法。

---

从这两个方面得出的结论是，您希望避免显式循环/递归，正如您正确认识到的那样。如果您以命令式的方式思考此算法，那么 State 单子似乎是一种自然的结构，因为它恰好隐藏了您所想到的那些命令式功能。然而，它也有缺点：例如，一切都变成了单子，而且最糟糕的是，除 apply 之外的函数都能够更改保存的解决方案。如果您将这个算法想象为每次都会产生一个新结果，您就会得到step :: Solution -> 的概念。解决方案，然后您可以使用iterate 来获取行为良好的无限列表。

Answer 2

这是如何使用 的伪代码草图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 块。不过，一旦您习惯了这种风格，您可能会想要习惯使用 <$> （又名 fmap）和函数组合来变得更加简洁：

loop :: State SearchState ()
loop = do
  move <- (chooseMove . evaluateMoves) <
gt; determineMoves
  modify (makeMove move)
  loop