Primero, tenga en cuenta que Objective Caml admite un estilo de programación que, a pesar de las diferencias sintácticas, es bastante similar a C++, mediante estructuras de datos mutables (referencias, matrices, tablas hash) y construcciones imperativas (ciclos for y while , asignación de variable). Asumo a continuación que en realidad estás tratando de escribir tu género topológico en un estilo idiomático funcional puro.
La programación funcional pura es principalmente declarativa: esta función aplicada a ese valor es este otro valor. Esta es la razón por la que el lado derecho de let x = es una expresión (se evalúa como un valor) en lugar de una secuencia de acciones que usa return. Por supuesto, los problemas aparecen cuando se adapta un algoritmo que comúnmente se describe como una serie de pasos.
Afortunadamente, hay un patrón (en realidad, una familia de patrones) que le permite representar algoritmos imperativos en estilo funcional al convertir "cambiar el valor de X" en "devolver un nuevo objeto que es idéntico al anterior" , excepto por el valor de X ".
Un algoritmo DFS tradicional implica recorrer el gráfico mientras recuerda qué elementos ya han sido visitados, en general (para que no los visite más de una vez) y para llegar a su posición actual (para que pueda detectar ciclos). Entonces, el estado imperativo de un algoritmo DFS está compuesto por el nodo actual, el conjunto de nodos visitados y el conjunto de nodos en la ruta actual. Todos estos datos deberán ser provistos a las llamadas recursivas, y cualquier cambio permanente tendrá que ser devuelto por esas mismas llamadas recursivas.
Usando su estructura gráfica de arriba, en combinación con una representación de la lista para los dos conjuntos (que es casi óptima - Set sería una mejor opción aquí), el algoritmo se vería algo como esto:
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
Tres detalles importantes arriba: primero, DFS dice que cuando haya terminado de explorar todos los elementos secundarios de un nodo determinado, debe eliminar ese nodo de la lista de "ruta actual" y colocarlo en la lista "visitado". Dado que estamos utilizando estructuras de datos inmutables, el primer paso es innecesario: su único propósito era deshacer la inserción del nodo cuando se inició la exploración, y en nuestra versión la lista new_path no es modificada por la llamada recursiva al explore. Este es un ejemplo de caso en que las estructuras de datos funcionales son más cómodas de trabajar que las estructuras imperativas.
Otro detalle importante es el uso de List.fold_left. Cuando comenzamos a hacer el estado explícito, reemplazamos funciones imperativas implícitas del tipo -> unit con funciones explícitas del tipo -> state -> .. -> state (aceptamos el estado como parámetro, devolvemos el estado nuevo).Por lo tanto, la exploración lista imperativo, que se veía así:
f edge_1 ; f edge_2 ; f edge_3
Ahora se ve así:
let state = f (f (f state edge_1) edge_2) edge_3)
que es exactamente lo que hace List.fold_left f state [edge_1 ; edge_2 ; edge_3]. Tocando mi propio cuerno, pero tengo a nice article about this here.
El tercer punto es que la operación "agregar elemento para establecer", al usar listas para representar conjuntos, se escribe simplemente como element :: set, porque esta es una operación que devuelve un nuevo conjunto (lista) que contiene todos los elementos de el conjunto original junto con el nuevo elemento. Esto deja el conjunto original intacto (lo cual es bueno por las razones descritas en el paso uno) mientras se usa una cantidad constante de memoria (crea una celda cons: un par simple cabeza-cola que contiene una referencia al elemento y una referencia al conjunto): no solo obtiene capacidades de deshacer, sino que lo hace sin costo adicional.
El algoritmo anterior "inserta" nodos en visited comenzando con las hojas de la exploración DFS, que en su caso representan los nodos que deberían hacerse al final. En resumen, la lista devuelta está clasificada topológicamente, pero podría no contener todos los elementos porque el punto de partida podría no ser el único elemento raíz (o incluso ser un elemento raíz). Entonces, aquí hay un paso de procesamiento adicional que consiste en tomar otro nodo del gráfico hasta que se haya explorado todo el gráfico.
O, en otras palabras, a partir de una exploración nueva DFS de cada nodo en el gráfico, pero ignorando cualquier nodos previamente explorado - lo que equivale a llevar la lista de elementos visitados de una exploración DFS a la siguiente .
Usando un pequeño pellizco en nuestro algoritmo anterior, esto tiene sólo dos líneas:
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
El truco consiste en permitir que la persona que llama de dfs para especificar la lista de nodos ya visitados. Llevar a cabo la lista de nodos visitados al iniciar un DFS desde cada nodo se hace usando List.fold_left exactamente como antes.
EDIT: aparte del tipo de la excepción, no hay nada aquí que restrinja el tipo de los elementos en el gráfico. Sin embargo, una excepción no puede ser polimórfica, por lo que tiene dos posibles soluciones. La primera consiste en renunciar a la realidad de devolver cualquier datos junto con la excepción:
exception CycleFound
... raise CycleFound ...
Esto revertirá el tipo de toposort de nuevo a una más genérica ('a * ('a list)) list -> 'a list.
La otra solución es bastante avanzada OCaml: lo necesario para hacer el móduloque contiene la excepción y la clasificación topológica polimórficos en ese tipo específico, de la siguiente manera:
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
Esto haría que el tipo de Topo(Node).sort ser (Node.t * (Node.t list)) list -> Node.t list, lo que significa que puede ordenar cualquier tipo que se desea mediante la definición de un módulo de nodo con ese tipo:
y 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
Si su pregunta había sido expresado de otra manera, me he recomendado O simplemente usa http://ocamlgraph.lri.fr/.Sin embargo, cuando esté más cómodo con OCaml y, en particular, con el sistema de módulos de OCaml, le recomiendo que vuelva a visitar este ejemplo. Una buena introducción a Ocamlgraph está en http://alexleighton.wordpress.com/2009/04/22/intro-to-ocamlgraph/. –