Функциональное программирование и алгоритмы с состоянием

Я изучаю функциональное программирование на Haskell . В то же время я изучаю теорию автоматов и, поскольку они, кажется, хорошо сочетаются друг с другом, я пишу небольшую библиотеку для игры с автоматами.

Вот проблема, которая заставила меня задать вопрос. Изучая способ оценки достижимости состояний, я пришел к выводу, что простой рекурсивный алгоритм будет весьма неэффективным, поскольку некоторые пути могут совместно использовать некоторые состояния, и я мог бы в конечном итоге оценить их несколько раз.

Например, здесь, оценка достижимости из г от , я должен был бы исключить е и при проверке пути через D и C :

Таким образом, моя идея состоит в том, что алгоритм, работающий параллельно по многим путям и обновляющий общую запись исключенных состояний, может быть хорошим, но это слишком много для меня.

Я видел, что в некоторых простых случаях рекурсии можно передать состояние в качестве аргумента, и это то, что я должен сделать здесь, потому что я передаю список состояний, через которые я прошел, чтобы избежать циклов. Но есть ли способ передать этот список и в обратном направлении, например, вернуть его в кортеже вместе с логическим результатом моей canReachфункции? (хотя это кажется немного вынужденным)

Помимо обоснованности моего примера , какие еще методы доступны для решения такого рода проблем? Я чувствую, что они должны быть достаточно распространенными, чтобы были такие решения, как то, что происходит с fold*или map.

До сих пор, читая learnyouahaskell.com, я не нашел ни одного, но учтите , что еще не трогал монады.

( если интересно, я разместил свой код на codereview )

Функциональное программирование не избавляет от состояния. Это только делает это явным! Хотя это правда, что такие функции, как map, часто «распутывают» «разделяемую» структуру данных, если все, что вы хотите сделать, это написать алгоритм достижимости, то это просто вопрос отслеживания того, какие узлы вы уже посетили:

import qualified Data.Set as S
data Node = Node Int [Node] deriving (Show)

-- Receives a root node, returns a list of the node keyss visited in a depth-first search
dfs :: Node -> [Int]
dfs x = fst (dfs' (x, S.empty))

-- This worker function keeps track of a set of already-visited nodes to ignore.
dfs' :: (Node, S.Set Int) -> ([Int], S.Set Int)
dfs' (node@(Node k ns), s )
  | k  `S.member` s = ([], s)
  | otherwise =
    let (childtrees, s') = loopChildren ns (S.insert k s) in
    (k:(concat childtrees), s')

--This function could probably be implemented as just a fold but Im lazy today...
loopChildren :: [Node] -> S.Set Int -> ([[Int]], S.Set Int)
loopChildren []  s = ([], s)
loopChildren (n:ns) s =
  let (xs, s') = dfs' (n, s) in
  let (xss, s'') = loopChildren ns s' in
  (xs:xss, s'')

na = Node 1 [nb, nc, nd]
nb = Node 2 [ne]
nc = Node 3 [ne, nf]
nd = Node 4 [nf]
ne = Node 5 [ng]
nf = Node 6 []
ng = Node 7 []

main = print $ dfs na -- [1,2,5,7,3,6,4]

Теперь я должен признаться, что отслеживание всего этого состояния вручную довольно раздражает и подвержено ошибкам (легко использовать s 'вместо s' ', легко передать один и тот же s более чем в одно вычисление ...) , Вот где приходят монады: они не добавляют ничего, что вы не могли сделать раньше, но позволяют неявно передавать переменную состояния, а интерфейс гарантирует, что это происходит однопоточным способом.

Редактировать: я попытаюсь дать более подробное обоснование того, что я сделал сейчас: во-первых, вместо того, чтобы просто проверять достижимость, я кодировал поиск в глубину. Реализация будет выглядеть примерно так же, но отладка выглядит немного лучше.

На языке с сохранением состояния DFS будет выглядеть примерно так:

visited = set()  #mutable state
visitlist = []   #mutable state
def dfs(node):
   if isMember(node, visited):
       //do nothing
   else:
       visited[node.key] = true           
       visitlist.append(node.key)
       for child in node.children:
         dfs(child)

Теперь нам нужно найти способ избавиться от изменчивого состояния. Прежде всего мы избавляемся от переменной "listlist", заставляя dfs возвращать это вместо void:

visited = set()  #mutable state
def dfs(node):
   if isMember(node, visited):
       return []
   else:
       visited[node.key] = true
       return [node.key] + concat(map(dfs, node.children))

А теперь самое сложное: избавиться от «посещаемой» переменной. Основная хитрость заключается в использовании соглашения, в котором мы передаем состояние в качестве дополнительного параметра функциям, которые в нем нуждаются, и эти функции возвращают новую версию состояния в качестве дополнительного возвращаемого значения, если они хотят его изменить.

let increment_state s = s+1 in
let extract_state s = (s, 0) in

let s0 = 0 in
let s1 = increment_state s0 in
let s2 = increment_state s1 in
let (x, s3) = extract_state s2 in
-- and so on...

Чтобы применить этот шаблон к dfs, нам нужно изменить его, чтобы получать набор «посещенных» в качестве дополнительного параметра и возвращать обновленную версию «посещенных» в качестве дополнительного возвращаемого значения. Кроме того, нам нужно переписать код, чтобы мы всегда передавали «самую последнюю» версию «посещенного» массива:

def dfs(node, visited1):
   if isMember(node, visited1):
       return ([], visited1) #return the old state because we dont want to  change it
   else:
       curr_visited = insert(node.key, visited1) #immutable update, with a new variable for the new value
       childtrees = []
       for child in node.children:
          (ct, curr_visited) = dfs(child, curr_visited)
          child_trees.append(ct)
       return ([node.key] + concat(childTrees), curr_visited)

Версия на Haskell в значительной степени делает то, что я сделал здесь, за исключением того, что она идет до конца и использует внутреннюю рекурсивную функцию вместо изменяемых переменных curr_visited и childtrees.

Что касается монад, то, что они в основном выполняют, - это неявная передача «curr_visited» вместо того, чтобы заставлять вас делать это вручную. Это не только удаляет помехи из кода, но также предотвращает ошибки, такие как разветвление состояния (передача одного и того же «посещенного» набора в два последующих вызова вместо цепочки состояния).

Вот простой ответ, на который можно положиться mapConcat.

 mapConcat :: (a -> [b]) -> [a] -> [b]
 -- mapConcat is in the std libs, mapConcat = concat . map
 type Path = []

 isReachable :: a -> Auto a -> a -> [Path a]
 isReachable to auto from | to == from = [[]]
 isReachable to auto from | otherwise = 
    map (from:) . mapConcat (isReachable to auto) $ neighbors auto from

Куда neighborsвозвращает состояния, непосредственно связанные с государством. Это возвращает серию путей.