Dylan's Journal

Wow, functional style can result in much smaller code:

Original, Imperative version:

(* returns string list *)
let roots r = r.roots 


(* returns topologically sorted string list *)
let sort_roots r =
let mkhash l =
let h = Hashtbl.create (List.length l) in
List.iter (fun root -> Hashtbl.add h root ()) l;
h
in
let rv = ref [] in
let roots = ref r.roots in
while (List.length !roots) > 0 do
let pairs = List.rev_map (
fun root -> root, Graph.in_degree r.patterns root
) !roots in
let name, _ = List.fold_left (
fun (n, d) (n', d') ->
if d' > d then
(n', d')
else (n, d)
) ("", 0) pairs in
let sorted = Graph.toposort r.patterns name in
let hash = mkhash !roots in
List.iter (
fun key -> Hashtbl.remove hash key
) sorted;
let rest = Hashtbl.fold (
fun k _ accu ->
k :: accu
) hash [] in
roots := rest;
rv := !rv @ sorted
done; !rv

Now, for the functional version:

let roots r =
let each x l = x :: l in
StrSet.fold each r.roots []


let rec sortroots' g set roots accu =
match roots with
root :: rest ->
sortroots' g (StrSet.remove root set) rest ((Graph.toposort g root) @ accu)
| [] -> accu

let sortroots r =
sortroots' r.patterns r.roots (roots r) []

This entry was posted on Monday, December 5th, 2005 at 2:59 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.