Working with OCaml is still really hard for me. The whole project would’ve been a hundred lines in a language I’m familiar with, but it ended up near 900 (though admittedly, this is much more rigorous). But if I want to be knowledgable enough about it to even be able to dismiss it, I must continue to try.
My primary observation so far is that the common claim I see about ML-- “Once your program compiles, it does the right thing”-- is very true in practice. That's really awesome and useful. On the other hand, the compiler errors you get can be really hard to track down. (Those two aren’t necessarily related: the first (good) one is a product of a strong static type system, while the second (bad) one comes from the type inference.)
Feel free to criticize; I’m still trying to learn. I also didn’t use any (for example) hash tables or arrays so I doubt I get the same runtime as a real implementation would.
let dijkstra edges src =
(* given full edge list and source,
return list of outgoing edges from source. *)
let rec outgoing edges src =
match edges with
[] -> []
| Edge(n1, c, n2, _)::rest ->
let outs = outgoing rest src in
if n1 = src then (n2, c)::outs else
if n2 = src then (n1, c)::outs else
outs
in
(* tentative list, new tentative item -> updated tentative list
(update the cost if the item’s already there, otherwise prepend it.) *)
let rec update_tentative tentative ((nn, nc, np) as newt) =
match tentative with
[] -> [newt]
| ((n,c,p) as orig)::rest ->
if nn = n then
(if nc < c then newt::rest else orig::rest)
else
orig::(update_tentative rest newt)
in
(* one iteration of dijkstra’s algorithm.
process all neighbors of the latest confirmed node. *)
let dijkstra_iter confirmed tentative =
let (cur,cost,_) = List.hd confirmed in
(* update_tentative on all neighbors of current node. *)
let rec update_neighbors t outs =
let update_neighbor t (n,ec) =
if (List.exists (fun (conf,_,_) -> conf=n) confirmed) then t
else update_tentative t (n,cost+ec,cur)
in
match outs with
[] -> t
| out::rest ->
let t’ = update_neighbor t out in
update_neighbors t’ rest
in
(* remove and return lowest-cost entry on tentative list. *)
let pop_lowest t =
let rec find_lowest t ((_,lowcost,_) as lowest) =
match t with
[] -> lowest
| ((_,cost,_) as cur)::rest ->
if cost < lowcost then find_lowest rest cur
else find_lowest rest lowest
in
let rec remove target l =
match l with
[] -> []
| cur::rest ->
if cur = target then rest
else cur::(remove target rest)
in
let lowest = find_lowest t (List.hd t) in
(lowest, remove lowest t)
in
(* the heart of the algorithm: *)
(* (1) update tentative with all of cur’s outgoing connections; *)
let out = (outgoing edges cur) in
let t’ = update_neighbors tentative out in
(* (2) and pop the lowest-cost tentative onto confirmed. *)
let (lowest, t’‘) = pop_lowest t’ in
(lowest::confirmed, t’‘)
in
let rec run c t =
match t with
[] -> c (* done *)
| _ ->
let (c’, t’) = dijkstra_iter c t in
run c’ t’
in
(* need to iterate once so something is on the tentative list to start with.
i need a do..while loop, not a while loop. :P *)
let (c, t) = dijkstra_iter [ (src, 0, src) ] [] in
run c t
Update: stupid LogJam ate some of my double-primes. Sorry about that.
