Recently I began to learn Haskell, and got to algorithms on graphs. Go very hard. Found Dijkstra's algorithm, but I can not figure out what happens in the code. Namely, it is not clear, it is transferred to the relax method:

retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)

And also what happens in the retMinNode method. Algorithm source code:

 inf = 100000 dijkstra ::Int->Int->[(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)] dijkstra sd adjList visited | (p,q) == (inf, inf) = visited | otherwise = dijkstra pd adjList ((p,q):visited) where (p,q) = exploreNeighbours s visited adjList exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int) exploreNeighbours source visited adjList = retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited) belongsTo::Int->[(Int,Int)]->Bool belongsTo _ [] = False belongsTo s ((x,_):xs) | (x==s) = True | otherwise = belongsTo s xs relax :: [(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)] relax [] visited = [] relax ((x,y,z):ns) visited = (y, (currDist x) + z):relax ns visited where currDist n = foldl(\acc t -> if (fst t == n) then (snd t) else acc) inf visited retMinNode ::[(Int,Int)]->(Int,Int) retMinNode [] = (inf,inf) retMinNode arr = foldl (\acc t -> if ((snd t) < (snd acc)) then t else acc) (inf,inf) arr

    1 answer 1

    retMinNode takes a list of pairs and returns a pair with the minimum second element.

    Teakr deal with

     exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int) exploreNeighbours source visited adjList = retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)

    To begin, rewrite by dividing a complex expression into parts.

     exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int) exploreNeighbours source visited adjList = retMinNode c where a = [(x,y,z) | (x,y,z) <- b, not (belongsTo y visited)] b = [(s,d,e) | (s,d,e) <- adjList, (belongsTo source visited)] c = relax a visited

    Expressions of the form [a | b <- c, d] [a | b <- c, d] are called list comprehension.

    • c source sheet.
    • b variable taking values ​​from the source list
    • d filter
    • a expression result.

    Thus, b is just a strange way to return an adjList if true belongsTo source visited and an empty list otherwise.

    Now let's deal with a . This is a list that is the result of filtering the previous one.

    Then everything seems to be simple.