How to improve calculation on shortest distance more idiomatically in Haskell? -
i've tried write calculation on shortest distance between 2 graph nodes according dijkstra's algorithm below, 2 things in code rather imperative , tedious:
- explicitly passing parameters mutated states in order reuse them later;
- heavily using conditional branch.
so i'd learn how improve in more idiomatic way of haskell you. lot in advance.
import qualified data.set set (size, insert) import data.set (set, empty, notmember) import qualified data.map map (size, insert, lookup) import data.map (map, fromlist) import data.maybe (fromjust) {- g: graph map, every edge weighs 1 simplicity. s: source vertex t: target vertex c: current vertex a: adjacent vertex as: adjacent vertex list v: visited vertex set d: shortest distance map -} -- purposely skipped explicit type signature make short below, caltotarget g t c v d | set.size v < map.size g - 1 && c /= t && notmember c v = calfromadj (lookup' c g) g t c v d | otherwise = d calfromadj [] _ _ _ _ d = d calfromadj (a : as) g t c v d = calfromadj g t c v $ caltotarget g t (set.insert c v) (calfromcurrent (a : as) c v d) calfromcurrent [] _ _ d = d calfromcurrent (a : as) c v d | notmember v = calfromcurrent c v $ map.insert (min (lookup' d) (lookup' c d + 1)) d | otherwise = calfromcurrent c v d lookup' k m = fromjust $ map.lookup k m -- test below, {- a-s---b-c \ |\ \ | \ \| \ d-e-t-f -} g = fromlist [ ("a", ["s"]), ("s", ["a", "b", "d"]), ("b", ["s", "c", "d", "t"]), ("c", ["b"]), ("d", ["s", "b", "e"]), ("e", ["d", "t"]), ("t", ["b", "e", "f"]), ("f", ["t"]) ] infinity = 99 d = fromlist [ ("a", infinity), ("s", infinity), ("b", infinity), ("c", infinity), ("d", infinity), ("e", infinity), ("t", infinity), ("f", infinity) ] v = empty s = "s" t = "t" -- shortest distance equal 2 "s" "t" below, main = print . lookup' t . caltotarget g t s v $ map.insert s 0 d
Comments
Post a Comment