Ответ 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, чтобы получить нужный бесконечный список.