Во-первых, имейте в виду, что Objective Caml поддерживает стиль программирования, который, несмотря на синтаксические различия, довольно похож на C ++ посредством изменяемых структур данных (ссылки, массивы, хеш-таблицы) и императивных конструкций (для циклов for и while, присвоение переменной). Ниже я предполагаю, что вы на самом деле пытаетесь написать свой топологический вид в идиоматическом чисто функциональном стиле.
Чистое функциональное программирование в основном декларативное: эта функция применяется к этому значению , это это другое значение. Вот почему правая часть let x = является выражением (оценивается как значение), а не последовательностью действий, которая использует return. Конечно, возникают проблемы при адаптации алгоритма, который обычно описывается как последовательность шагов.
К счастью, есть шаблон (на самом деле, семейство шаблонов), который позволяет вам представлять алгоритмы императивного вывода в функциональном стиле, поворачивая «изменить значение X» на «возвращая новый объект, который идентичен старому, за исключением значения Х ".
Традиционный алгоритм DFS включает в себя пошаговое прохождение по графику с запоминанием того, какие элементы уже были посещены - в целом (чтобы вы не посещали их более одного раза) и для перехода к вашей текущей позиции (чтобы вы могли обнаружить циклы ). Итак, императивное состояние алгоритма DFS состоит из текущего узла, набора посещенных узлов и набора узлов в текущем пути. Все эти данные должны быть предоставлены для рекурсивных вызовов, и любые постоянные изменения должны быть возвращены теми же рекурсивными вызовами.
Используя вышеописанную структуру графа в сочетании с представлением списка для двух наборов (вряд ли это оптимально - Set будет лучшим выбором здесь), алгоритм будет выглядеть примерно так:
let dfs graph start_node =
let rec explore path visited node =
if List.mem node path then raise (CycleFound path) else
if List.mem node visited then visited else
let new_path = node :: path in
let edges = List.assoc node graph in
let visited = List.fold_left (explore new_path) visited edges in
node :: visited
in explore [] [] start_node
Три важные детали выше: во-первых, DFS говорит, что, закончив изучение всех дочерних узлов данного узла, вы должны удалить этот узел из списка «текущий путь» и поместить его в список «посещенных». Поскольку мы используем неизменные структуры данных, первый шаг не требуется: его единственная цель состояла в том, чтобы отменить вставку узла, когда началось исследование, и в нашей версии список new_path не изменяется рекурсивным вызовом explore. Это пример случая, когда с функциональными структурами данных работать удобнее, чем с императивными структурами.
Еще одной важной деталью является использование List.fold_left. Когда мы начали делать состояние явным, мы заменили неявные императивные функции типа -> unit на явные функции типа -> state -> .. -> state (примите состояние в качестве параметра, верните новое состояние). Итак, императивный список исследований, который выглядел так:
f edge_1 ; f edge_2 ; f edge_3
Теперь выглядит так:
let state = f (f (f state edge_1) edge_2) edge_3)
Именно это и делает List.fold_left f state [edge_1 ; edge_2 ; edge_3]. У моего собственного рога, но у меня есть хорошая статья об этом здесь .
Третий момент заключается в том, что операция «добавить элемент в набор» при использовании списков для представления наборов записывается просто как element :: set, поскольку это операция, которая возвращает новый набор (список), который содержит все элементы оригинального набора вместе с новым элементом. Это оставляет исходный набор нетронутым (что хорошо по причинам, описанным в первом шаге) при использовании постоянного объема памяти (он создает ячейку cons - простую пару голова-хвост, содержащую ссылку на элемент и ссылку на набор ): вы не только получаете возможность отмены, но и делаете это без дополнительных затрат.
Приведенный выше алгоритм «вставляет» узлы в visited, начиная с листьев исследования DFS, которые в вашем случае представляют те узлы, которые должны быть выполнены последними. Короче говоря, возвращаемый список отсортирован топологически, но может содержать не все элементы, поскольку отправная точка может быть не единственным корневым элементом (или вообще не быть корневым элементом). Таким образом, здесь есть дополнительный этап обработки, заключающийся в том, чтобы убрать еще один узел из графа, пока весь граф не будет исследован.
Или, другими словами, запуск нового исследования DFS с каждого узла в графике , но игнорирование любых ранее исследованных узлов - что эквивалентно сохранению списка посещенных элементов от одного исследования DFS до следующего.
Используя небольшую настройку нашего предыдущего алгоритма, это займет всего две строки:
let dfs graph visited start_node =
let rec explore path visited node =
if List.mem node path then raise (CycleFound path) else
if List.mem node visited then visited else
let new_path = node :: path in
let edges = List.assoc node graph in
let visited = List.fold_left (explore new_path) visited edges in
node :: visited
in explore [] visited start_node
let toposort graph =
List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph
Подстройка состоит в том, чтобы позволить вызывающему dfs указать список уже посещенных узлов. Перенос списка посещенных узлов при запуске DFS с каждого узла выполняется с использованием List.fold_left точно так же, как и раньше.
EDIT : кроме типа исключения, здесь нет ничего, что ограничивало бы тип элементов в графе. Однако исключение не может быть полиморфным, поэтому у вас есть два возможных решения. Во-первых, нужно отказаться от фактического возврата любых данных, за исключением:
exception CycleFound
... raise CycleFound ...
Это вернет тип toposort обратно к более общему ('a * ('a list)) list -> 'a list.
Другое решение - довольно продвинутый OCaml: вам нужно сделать модуль , который содержит исключение и топологическую сортировку полиморфной в этом конкретном типе, следующим образом:
module type NODE = sig
type t
end
module type Topo = functor (Node:NODE) -> struct
exception CycleFound of Node.t list
let dfs ...
let sort ...
end
При этом тип Topo(Node).sort будет (Node.t * (Node.t list)) list -> Node.t list, что означает, что вы можете отсортировать любой тип по вашему желанию, определив модуль узла с этим типом:
type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve
module Node = struct
type t = recipe
end
let graph = [ Wheat, [Eggs,Milk,Mix] ;
Milk, [Mix] ;
Eggs, [Mix] ;
Mix, [Cook] ;
Cook, [Serve] ;
Serve, [] ]
module RecipeTopo = Topo(Node)
let sorted = RecipeTopo.sort graph