Учу 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)
- Форум язычок вот написал (2020)
- Форум Решено | Конвертировать file.txt в формат file.json через Bash (2022)
- Форум DFS (2018)
- Галерея DFS (2004)
- Форум [ocaml] ocaml <--> c (2008)
- Форум Выбор DFS (2012)
- Форум Не работает блюр на верхней панели js (2025)
- Форум Ocaml (2008)