何时使用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的函数,并在递归函数中将它们链接在一起,以处理循环并将状态从一次迭代传递到下一次迭代,但我有一个模糊的想法,即monads适用.

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

Answer 1

在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

在这里,我们使用applicative notation来表示我们实际上只是在一个上下文中做(.) 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,所以随机性就出来了.不过你很容易做出这个monadic.)

但是,只是为了踢,让我们考虑一下Statemonad.这代表了某种环境的计算,因此它与某些东西State s a是同构的s -> (a,s),可以看到状态并可能更新它.在这里,Solution ->函数签名左侧的所有s都将消失,-> Solution右侧的s 也将消失.这会让你失望

1. moves :: State Solution [Move]
2. value :: Move -> State Solution Double
3. choose :: [Move] -> State Solution Move
4. apply :: Move -> State Solution ()

这意味着你会有一些monadic动作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",这是你的算法的定义.

来自这两者的带回家的消息是你想要避免显式的循环/递归,正如你正确地意识到的那样.如果你强行考虑这个算法,那么Statemonad似乎是一个自然的结构,因为它隐藏了你正在考虑的那些命令性功能.但是,它有缺点:例如,除了apply能够更改已保存的解决方案之外,一切都变成了monadic,而且最糟糕的是所有功能.如果你想象这个算法每次产生一个新的结果,你就会得到这个概念step :: Solution -> Solution,并且你可以用它iterate来获得一个表现良好的无限列表.

Answer 2

这是一个伪代码草图,说明如何使用Statemonad通过计算来线程化搜索状态:

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是非monadic,我曾经let向你展示如何将它们显式地集成到一个do块中.但是,一旦你对这种风格感到满意,你可能会想要使用<$>(又名fmap)和功能组合来获得更简洁:

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