haskell - 何时使用Haskell monads

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

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

Answer 1

在Haskell中表达这种迭代过程的最佳方法是将每个连续结果作为一个无限列表。将您的四个步骤组合在一起，可以得出从解决方案到另一个(更好)解决方案的功能概念。您需要做的是无限次应用此方法。函数的用户然后可以使用任何列表函数来获取答案:solve s0 !! numIterations或find stoppingCondition $ solve s0或任何您想要的东西。

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

moves :: Solution -> [Move]给定一个可能的解决方案，找出可以进行的更改。

value :: Solution -> Move -> Double给定一个解决方案和一个 Action ，对其进行评估并将该值记录为一些实数。

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

这些片段中的任何一个都能满足您的需求。 (条件:您的任何函数中都没有效果/单子(monad)，因此随机性就消失了。不过，您可以轻松地使此单子(monad)成单。)

不过，只为踢球，让我们考虑State monad。这表示具有某种环境的计算，因此State s a与s -> (a,s)是同构的，可以看到状态并可能对其进行更新。在这里，函数签名左侧的所有Solution ->都会消失，右侧的-> Solution也会消失。那会让你

moves :: State Solution [Move]

value :: Move -> State Solution Double

choose :: [Move] -> State Solution Move

apply :: Move -> State Solution ()

这意味着您将有一些单子(monad) Action 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生成答案，或者使用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似乎是自然结构，因为它完全隐藏了您正在考虑的那些命令性功能。但是，它有缺点:例如，所有内容都变成了单子(monad)，最糟糕的是，除apply之外的功能都可以更改保存的解决方案。如果您反而每次都将此算法想象为产生新结果，则会得到step :: Solution -> Solution的概念，然后可以使用iterate获得行为良好的无限列表。