Учу Ocaml. Есть некоторые проблемы в том, что часто хочется написать какой-то алгоритм в привычном императивном стиле. Долго с непривычки мучаюсь, чтобы написать в функциональном стиле, а то что получается не всегда нравится. Может кто поможет, никак не могу придумать нормальную реализацию DFS (depth first search) в функциональном стиле. Пока лучшее, что придумал весьма громоздко и использует модуль Set для хранения состояния: module IntSet = Set.Make ( struct type t = int let compare x y = if x < y then (-1) else if x > y then 1 else 0 end) ;; let dfs gm v = let n = Array.length gm in let rec dfs_aux v l results = let rec iter i (l, results) = if i = n then (l, results) else if gm.(v).(i) && not (IntSet.mem i l) then iter (i + 1) (dfs_aux i (IntSet.add i l) (i :: results)) else iter (i + 1) (l, results) in iter 0 (l, results) in List.rev (snd (dfs_aux v (IntSet.singleton v) [v])) ;; let dfs gm v = let n = Array.length gm in let l = Array.make n false in let verticies = ref [] in let rec dfs_aux v = l.(v) <- true ; verticies := v :: !verticies ; for i = 0 to n - 1 do if gm.(v).(i) && not l.(i) then dfs_aux i done in dfs_aux v ; List.rev !verticies ;; let gm = Array.make_matrix 8 8 false ;; gm.(0).(1) <- true ;; gm.(0).(2) <- true ;; gm.(0).(4) <- true ;; gm.(1).(0) <- true ;; gm.(1).(3) <- true ;; gm.(2).(0) <- true ;; gm.(2).(3) <- true ;; gm.(2).(5) <- true ;; gm.(3).(1) <- true ;; gm.(3).(2) <- true ;; gm.(4).(0) <- true ;; gm.(4).(6) <- true ;; gm.(4).(7) <- true ;; gm.(5).(2) <- true ;; gm.(6).(4) <- true ;; gm.(7).(4) <- true ;; Printf.printf "[" ;; List.iter (function v -> Printf.printf "%d; " v) (dfs gm 0) ;; Printf.printf "]\n" ;; Расскажите пожалуйста, как это сделать красиво? Спасибо. P. S. Может кто знает какую-нить свободную книгу или сайт какой, где можно почерпнуть знания о реализации стандартных алгоритмов/структур данных в функциональном стиле ?
Ответ на:
комментарий
от Zulu
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Похожие темы
- Форум ocaml Syntax error (2010)
- Форум OCaml. Непонятки с модулями. (2006)
- Форум DFS (2018)
- Галерея DFS (2004)
- Форум [ocaml] ocaml <--> c (2008)
- Форум Выбор DFS (2012)
- Форум Ocaml (2008)
- Форум OCaml (2006)
- Форум Prolog implementation. (2008)
- Форум scheme implementation (2005)