I really enjoy Haskell but feel I still have a total beginner's style, and would like to move beyond that. The code below - for Dijkstra's shortest path algorithm - is a case in point. I feel as though I have ended up with a copy of the imperative pseudo code I began with, having done some small transformations, but not the sort of big ones an expert would come up with. (Perhaps it was the very fact that I had pseudo code to start with that got me into this mess - without it would I have pursued a generate and prune strategy?)
But the big decision I needed was how to store the 3 elements of state
- The results
- The Dijkstra scores of the points not yet turned into results; and
- The set of points already found (i.e. the keys of the results)
In the end I used a Vector to Dijkstra scores, and have been passing around my state variables, whereas they could probably have been put into the background with a Monad. I know that having Vector manipulations in two places is not smart (I could probably have reduced that 1 by passing the deletion request into
I'd welcome any constructive comments, on how an expert would approach the state challenge.
import qualified Data.ByteString.Char8 as BS import qualified Data.Vector as V import qualified Data.List as L type NodeName = Int type Dist = Int type Edge = (NodeName, Dist) type Edges = [Edge] type Graph = V.Vector Edges -- STATE type Explored = [NodeName] -- IntSet? type Results = [(NodeName, Dist)] -- need to add to randomly type DijkstraScores = V.Vector (Maybe Dist) -- take top from DijkList -- add to results -- get update DijkList mainLoop :: Graph -> Explored -> DijkstraScores -> Results -> Results mainLoop gr exs ds res = let minIdx = V.minIndexBy maybeOrder ds Just minVal = ds V.! minIdx res' = (minIdx,minVal) : res exs' = minIdx : exs newDists = filter (not . (`elem` exs') . fst) $ gr V.! minIdx newDs = recalcDijkDist newDists minVal $ ds V.// [(minIdx,Nothing)] -- remove this value in case V.all (==Nothing) newDs of True -> res False -> mainLoop gr exs' newDs res' -- run over new Dists -- change if lower -- leave if higher -- add if no existing data -- recombine with all other data recalcDijkDist :: Edges -> Dist -> DijkstraScores -> DijkstraScores recalcDijkDist newDists distOfNewPoint ds = let comps = map process newDists process :: Edge -> (Int, Maybe Int) process (x,y) = case ds V.! x of Just z -> (x, Just $ min (y + distOfNewPoint) z) Nothing -> (x, Just $ y + distOfNewPoint) in ds V.// comps getEdges :: String -> IO Graph getEdges path = do -- init removes a trailing '\r' lines <- (map (init . (BS.split '\t')) . BS.lines) `fmap` BS.readFile path let gr = V.fromList $ ( :) $ map processLine lines return gr processLine :: [BS.ByteString] -> Edges processLine (n:connections) = map splitter connections where myread = maybe (error "can't read Int") fst . BS.readInt splitter c = let (x,y) = (\(xx,yy) -> (xx, BS.tail yy)) $ BS.break (==',') c in (myread x, myread y) main = do gr <- getEdges "dijkstra.txt" let --mloop = mainLoop gr  (initDijkstra $ gr V.! 1)  mloop = mainLoop gr  (recalcDijkDist (gr V.! 1) 0 $ V.replicate 201 Nothing)  anstoFind = [7,37,59,82,99,115,133,165,188,197] -- maybe :: b -> (a -> b) -> Maybe a -> b answers = map (\x -> snd $ maybe (error "not found") id $ L.find ((==x).fst) mloop) anstoFind return answers --return gr -- Nothing is interpreted as 0 otherwise maybeOrder :: Maybe Int -> Maybe Int -> Ordering maybeOrder Nothing x = GT maybeOrder x Nothing = LT maybeOrder (Just x) (Just y) = compare x y