何时使用Haskell monad [英] When to use Haskell monads

问题描述

 给出一个初始候选解决方案，重复直到满足停止条件为止：
 
 1.确定可能的移动
 2.评估可能的移动
 3.选择一个移动
 4.进行移动，记录新的候选解决方案，更新搜索状态
  

我可以为步骤1-4编写函数，并将它们链接在一个递归函数中，以处理循环和传递状态从一个迭代到下一个，但我有一个模糊的想法，单子应用。

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

解决方案

在Haskell中表达这种迭代过程的最好方式是每个连续结果的无限列表。把你的四个步骤组合在一起就产生了从解决方案到不同（更好）解决方案的功能的概念;你所需要做的就是无限次地应用这个。你的函数的用户可以使用任何列表函数来获得答案：解决s0！ numIterations ，或 find stoppingCondition $ solve s0 ，或者任何你想要的。

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

1. moves ::解决方案 - > ; [移动]
   
   给出一个可能的解决方案，找出可能的修改。


2. value： ：解决方案 - >移动 - > Double
   
   
   给出一个解决方案和一个举动，对它进行评估并将该值记录为某个实数。
   
3. 选择::解决方案 - > [移动] - >移动
   
   给出解决方案和移动列表，选择最好的移动列表。


4. apply :: Solution - >移动 - >解决方案
   
   
   给出一个步骤，将其应用于现有的解决方案以获取新的解决方案。

你想写一个类型如 solve :: Solution - >的函数。 （解决方案 - > Bool） - >解决方案需要一个初始解决方案和一个停止条件来执行你的算法。

相反，让我们把它作为一个无限列表。这意味着您只需删除谓词并使用 Solution - > [解决] 。

  import Data.Ord 
 import Data.List 
 
  - 移动，值和应用是特定于域的
 choose :: Solution  - > [移动]  - >移动
选择s ms = maximumBy（比较$ value s）ms 
 
解决::解决方案 - > [解决] 
 solve =迭代$ \s  - >申请。选择s $ move s 
  

这里的关键是 iterate ::（a - > a） - > a - > [a] ，它重复地将一个函数应用于一个值，并给出结果 - 完全是你的算法的描述。

然而，方式我真的写这将是以下内容：

$ p $ import Data.Ord
import Data.List

solve :: Ord o => （s - > [m]） - > （s→m→o）→> （s→m→s）→> s - > [s]
求解移动值apply =迭代步骤
其中步骤s =应用s。选择s $ move s
选择s = maximumBy（比较$ value s）


这是因为你可以对任何问题域重用相同的通用结构。您只需提供移动，值和 apply 函数！根据我的心情，我可能会将其重写为：

  import Control.Applicative 
 import Data.Ord 
 import Data.List 
 
 solve :: Ord o => （s  - > [m]） - > （s→m→o）→> （s→m→s）→> s  - > [s] 
求解移动值apply =迭代步骤
其中step =（。）< $>应用< *>选择< *>移动
 choose = maximumBy。比较。价值
  

在这里，我们使用应用符号来表示我们实际上只是在做（。）在一个上下文中应用choose moves （这只是 apply。choose $ moves ），其中每个函数都隐式传递参数 s （读者应用）。如果我们真的想要tersify的东西，我们可以写入

  import Control.Applicative 
 import Data.Ord 
 import Data.List 
 
 solve :: Ord o => （s  - > [m]） - > （s→m→o）→> （s→m→s）→> s  - > [s] 
解决移动值apply = 
迭代$（。）< $>应用< *> maximumBy。比较。值*移动
  

这些片段中的任何一个都可以完全满足您的需求。 （Proviso：在你的任何函数中没有任何效果/ monad，所以随机性已经出来，不过你可以很容易地做这个monadic。）

---

不过，我们来考虑一下 State monad。这代表了一种具有某种环境的计算，因此 State s a 同构于 s - > （a，s） - 可以看到状态并可能更新它的东西。在这里，函数签名左侧的所有 Solution - > s会消失， - >解决方案在右侧。那会让你失望：
$ b $ ol

moves :: State Solution [Move]

value :: Move - > State Solution Double

choose :: [Move] - > State Solution Move

apply :: Move - > State Solution（）

这意味着您将会有一些monadic操作 step ：

  import Control.Applicative 
 import Control.Monad.State 
导入Data.Ord 
导入Data.List 
 
选择:: [Move]  - >状态解决方案在fst中移动
 choose = let val m = do v < -  value m 
 return（m，v）
。 maximumBy（比较snd）< $> mapM val ms 
 
 step :: State Solution（）
 step = apply =<<选择=<<移动
  

你可以让这个更加无点，或者像上面那样变得多态，但是我赢了在这里做这件事。问题是，一旦你有 step ，你可以用 runState产生答案。最后$ replicateM_ numIterations步骤，或给出 whileM 函数， runState $ whileM（stopsCondition :: State Solution Bool）步骤。同样，用户可以决定如何停止它。您的移动和值函数可能会通过 get :: State ss ; apply 可能会使用修改::（s - > s） - >状态s（）可以调整状态，而无需将其拉回。在这些类型中可以看到与上面的结构的相似性;实际上，您也可以在 step 的定义中看到该结构。每个人都说串在一起应用，选择 / 值 ， moves ，这就是你的算法的定义。

---

从这两个方面获得的信息就是，你希望避免显式的循环/递归，正如你正确地认识到的那样。如果你必须考虑这个算法，那么 State monad看起来就像是一个自然的结构，因为它隐藏了你正在考虑的命令性功能。然而，它有缺点：例如，一切都变成了一元，除了 apply 之外的其他函数都可以更改保存的解决方案。如果你想象这个算法每次都产生一个新的结果，你可以看到 step :: Solution - >的概念。解决方案，并从那里你可以使用 iterate 来得到一个行为良好的无限列表。

I'm implementing a combinatorial optimization algorithm in 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

I could write functions for steps 1-4 and chain them together inside a recursive function to handle looping and passing state from one iteration to the next, but I have a vague idea that monads apply.

What's the best way to express this kind of procedure in Haskell?

解决方案

The best way to express this sort of iterative procedure in Haskell is as an infinite list of each successive result. Piecing together your four steps yields a notion of a function from a solution to a different (better) solution; all you need to do is apply this infinitely many times. The user of your function can then use any list function to get the answer: solve s0 !! numIterations, or find stoppingCondition $ solve s0, or whatever you want.

In order to get here, let's write out the types for each of these functions.

1. moves :: Solution -> [Move]
   Given a possible solution, figure out the possible changes you can make.
2. value :: Solution -> Move -> Double
   Given a solution and a move, evaluate it and record that value as some real number.
3. choose :: Solution -> [Move] -> Move
   Given a solution and a list of moves, pick the best one.
4. apply :: Solution -> Move -> Solution
   Given a move, apply it to an existing solution to get a new one.

You want to write a function with a type something like solve :: Solution -> (Solution -> Bool) -> Solution which takes an initial solution and a stopping condition to execute your algorithm.

Instead, let's make this an infinite list; this means that you'll just remove the predicate and have 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

Here, the key is iterate :: (a -> a) -> a -> [a], which repeatedly applies a function to a value and gives you the results—exactly the description of your algorithm.

However, the way I'd really write this would be the following:

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)

The advantage of this is that you can reuse this same generic structure for any problem domain. All you need to do is to provide the moves, value, and apply functions! And depending on my mood, I might rewrite that as this:

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

Here, we use applicative notation to say that we're effectively just doing (.) apply choose moves (which is just apply . choose $ moves) in a context where each of those functions is implicitly passed a parameter s (the reader applicative). If we really wanted to tersify things, we could write

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

Any of these snippets will do exactly what you need. (Proviso: there are no effects/monads in any of your functions, so randomness is out. You make this monadic easily, though.)

---

Just for kicks, though, let's think about the State monad. This represents a computation with some sort of environment, so that State s a is isomorphic to s -> (a,s)—something which can see the state and potentially update it. Here, all the Solution ->s on the left of your function signatures would disappear, as would the -> Solutions on the right. That would leave you with

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

This means that you would have some monadic 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

You could make this more point-free, or make it polymorphic just as above, but I won't do that here. The point is that once you have step, you can generate answers with runState . last $ replicateM_ numIterations step, or given a whileM function, runState $ whileM (stoppingCondition :: State Solution Bool) step. Again, the user can decide how to stop it. Your moves and value functions would probably query the state with get :: State s s; apply would probably use modify :: (s -> s) -> State s () to tweak the state without needing to pull it back out. You can see the similarity with the structure from above in these types; and in fact, you can see that structure in the definition of step, as well. Each one says "string together apply, choose/value, and moves", which is the definition of your algorithm.

---

The take-home message from both of these is that you want to avoid explicit loops/recursion, as you so rightly realized. If you think about this algorithm imperatively, then the State monad seems like a natural structure, as it hides exactly those imperative features you were thinking of. However, it has downsides: for instance, everything has become monadic, and—worst of all—functions other than apply are able to change the saved solution. If you instead imagine this algorithm as producing a new result each time, you get the notion of step :: Solution -> Solution, and from there you can use iterate to get a well-behaved infinite list.

这篇关于何时使用Haskell monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！