何时使用Haskell Monad

Question

何时使用Haskell Monad

20

我正在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中，如何最好地表达这种过程？

- zoo

2个回答

7

这是一个伪代码示例，展示了如何使用State单子将搜索状态传递到计算中：

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

请注意，即使您的主要计算在状态单子中，也不必每个组件都在单子中。在这里，evaluateMoves和chooseMove是非单子化的，我使用了let来向您展示如何将它们明确地集成到do块中。但是，一旦您熟悉了这种风格，您可能会想要使用<$>（又名fmap）和函数组合来获得更简洁的代码：

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

- acfoltzer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Antal Spector-Zabusky · Accepted Answer

在Haskell中表达这种迭代过程的最佳方法是将每个连续结果表示为一个“无限列表”。将四个步骤组合起来，得到从解决方案到不同（更好）解决方案的函数概念；你需要做的就是无限次地应用它。使用您的函数的用户可以使用任何列表函数来获取答案：solve s0 !! numIterations 或 find stoppingCondition $ solve s0，或者其他任何您想要的。

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

1. 给定可能的解决方案，找出可以进行的更改： moves :: Solution -> [Move]。 2. 给定一个解决方案和一个动作，对其进行评估，并将该值记录为某个实数： value :: Solution -> Move -> Double。 3. 给定一个解决方案和动作列表，选择最佳动作： choose :: Solution -> [Move] -> Move。 4. 给定一个动作和现有解决方案，将其应用于获得新解决方案： 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）。如果我们真的想简化事情，我们可以写成

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

任何一个片段都可以完全满足您的需求。（注意：在您的任何函数中没有效果/单子，所以随机性被排除了。不过，您很容易使其成为单子。）

开玩笑，我们来考虑一下State单子。它表示具有某种环境的计算，因此State s a等同于s->（a，s）——它可以看到状态并可能更新它。在这里，您函数签名左侧的所有Solution ->将消失，右侧的-> Solution也将消失。这将使您剩下以下内容：

1. moves :: State Solution [Move] 2. value :: Move -> State Solution Double 3. choose :: [Move] -> State Solution Move 4. 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

你可以将这个函数更加 point-free，或者像上面那样使它变成多态的，但我在这里不会这样做。重点是一旦你有了 `step`，你就可以使用 `runState . last $ replicateM_ numIterations step` 生成答案，或者给定一个 `whileM` 函数，使用 `runState $ whileM (stoppingCondition :: State Solution Bool) step`。同样，用户可以决定何时停止它。你的 `moves` 和 `value` 函数可能会使用 `get :: State s s` 查询状态；`apply` 可能会使用 `modify :: (s -> s) -> State s ()` 调整状态而无需将其取回。在这些类型中，您可以看到与上面的结构类似之处；实际上，在 `step` 的定义中也可以看到该结构。每个都是“将 `apply`、`choose`/`value` 和 `moves` 连接在一起”，这就是你的算法的定义。

这两个方法的主要信息是你需要避免显式循环/递归，正如你所意识到的那样。如果您将此算法作为命令式思考，则 `State` Monad 看起来像是自然的结构，因为它隐藏了恰好那些您想到的命令式特性。然而，它也有缺点：例如，所有内容都已变成单子，并且最糟糕的是，除了 `apply` 之外的函数都可以更改保存的解决方案。如果您将此算法想象为每次生成一个新结果，则会得到 `step :: Solution -> Solution` 的概念，然后您可以使用 `iterate` 获取良好行为的无限列表。