Когда использовать монады Хаскелла

Ответ 1

Лучший способ выразить эту итеративную процедуру в Haskell - это бесконечный список каждого последующего результата. Объединение четырех шагов дает представление о функции от решения к другому (лучшему) решению; все, что вам нужно сделать, это применять это бесконечно много раз. Затем пользователь вашей функции может использовать любую функцию списка, чтобы получить ответ: solve s0 !! numIterations или find stoppingCondition $ solve s0 или что угодно.

Чтобы получить здесь, напишите типы для каждой из этих функций.

• moves :: Solution -> [Move]
  Учитывая возможное решение, выясните возможные изменения, которые вы можете сделать.
• value :: Solution -> Move -> Double
  Учитывая решение и ход, оцените его и запишите это значение как некоторое действительное число.
• 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

Любой из этих фрагментов будет делать именно то, что вам нужно. (Proviso: никаких эффектов/монад в любой из ваших функций нет, поэтому случайность отсутствует. Однако вы делаете это монадично легко.)

Просто для ударов, пусть, подумайте о монаде State. Это представляет собой вычисление с какой-то средой, так что 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 ()

Это означает, что у вас будет некоторое монадическое действие 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 кажется естественной структурой, поскольку она скрывает именно те императивные функции, о которых вы думали. Однако у него есть минусы: например, все стало монадическим, а худшая из всех функций, отличных от apply, может изменить сохраненное решение. Если вы вместо этого представляете этот алгоритм как новый результат каждый раз, вы получаете понятие step :: Solution -> Solution, и оттуда вы можете использовать iterate, чтобы получить нужный бесконечный список.

Ответ 2

Здесь представлен псевдокодный эскиз того, как вы можете использовать монаду 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. Как только вам станет комфортно в этом стиле, вы, вероятно, захотите получить удобство, используя <$> (aka fmap) и составную часть композиции, чтобы получить более краткий:

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