Реализация алгоритма длинного пути в Haskell

Question

Я бы хотел, чтобы некоторые из них помогли реализовать алгоритм длинного пути для Haskell. Я использовал Haskell только две недели и раньше ничего не делал на функциональном языке. Я действительно теряюсь при попытке реализовать алгоритмы на функциональном языке, когда вы ограничены неизменяемыми данными и рекурсией.

Я пытался реализовать этот алгоритм: http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Мой график строится так:

data = Graph w = Graph {vertices :: [(Char, w)], 
         edges :: [(Char, Char, w)]} deriving Show 

Так что я весов на обеих вершин и ребер, а также веса может быть любой тип данных , Поэтому при вычислении самого длинного пути мне также нужно взять две функции: f и g. Самый длинный путь от вершины a до b будет представлять собой сумму f(w) и g(w) для всех весов пути.

Я попытался реализации этого, но я всегда нахожу себя пытается закодировать «императивный» путь, который получает действительно некрасиво очень быстро ...

Пожалуйста, мне точку в правильном направлении.

weight_of_longest_path :: (Ord w) => Graph w -> Char -> Char 
              -> (w -> w) -> (w -> w) -> w 
weight_of_longest_path (Graph v w) startVert endVert f g = 
    let 
    topSort = dropWhile (/= startVert) $ topological_ordering (Graph v w) 
    distList = zip topSort $ 
       (snd $ head $ filter (\(a,b) -> a == startVert) v) 
       : (repeat (-999999999)) 
    finalList = getFinalList (Graph v w) topSort distList f g 
    in 
    snd $ head $ filter (\(a,b) -> b == endVert) finalList 

getFinalList :: (Ord w) => Graph w -> [Char] -> [(Char, w)] 
            -> (w -> w) -> (w -> w) -> [(Char, w)] 
getFinalList _ [] finalList _ _ = finalList 
getFinalList (Graph v w) (firstVert:rest) distList f g = 
    let 
    neighbours = secondNodes $ filter (\(a,b,w) -> a == firstVert) w 
    finalList = updateList firstVert neighbours distList (Graph v w) f g 
    in 
    getFinalList (Graph v w) rest finalList f g 

updateList :: (Ord w) => Char -> [Char] -> [(Char, w)] -> Graph w 
           -> (w -> w) -> (w -> w) -> [(Char, w)] 
updateList _ [] updatedList _ _ _ = updatedList 
updateList firstVert (neighbour:rest) distList (Graph vertices weights) f g = 
    let 
    edgeWeight = selectThird $ head 
      $ filter (\(a,b,w) -> a == firstVert && b == neighbour) weights 
    verticeWeight = snd $ head 
      $ filter (\(a,b) -> a == neighbour) vertices 
    newDist = calcDist firstVert neighbour verticeWeight edgeWeight 
         distList f g 
    updatedList = replace distList neighbour newDist 
    in 
    updateList firstVert rest updatedList (Graph vertices weights) f g 


calcDist :: (Ord w) => Char -> Char -> w -> w -> [(Char, w)] 
          -> (w -> w) -> (w -> w) -> w 
calcDist firstVert neighbour verticeWeight edgeWeight distList f g = 
    if (compareTo f g 
     (snd $ head $ filter (\(a,b) -> a == neighbour) distList) 
     (snd $ head $ filter (\(a,b) -> a == firstVert) distList) 
     edgeWeight verticeWeight) == True 
    then 
    (f (snd $ head $ filter (\(a,b) -> a == firstVert) distList)) 
    + (g edgeWeight) + (f verticeWeight) 
    else 
    (f (snd $ head $ filter (\(a,b) -> a == neighbour) distList)) 

replace :: [(Char, w)] -> Char -> w -> [(Char, w)] 
replace distList vertice value = 
    map (\p@(f, _) -> if f == vertice then (vertice, value) else p) 
     distList 

Как вы можете видеть, что это много грязного код для такого простого алгоритма, и я уверен, что его выполнимым в более чистом способе.

Answer 1

Вот подход, который использует более «функциональный» способ мышления. Она вращается вокруг двух функций:

longestPath :: Graph -> Node -> Node -> [Edge] 
pathCost :: Graph -> [Edges] -> Int 

longestPath возвращает путь в виде списка ребер самого длинного пути. pathCost возвращает стоимость пути.

Определение longestPath идет что-то вроде этого:

longestPath g start end 
    | start == end = [] 
    | otherwise = 
    maximumBy (comparing (pathCost g)) 
       [ e : path | e <- edges of the node start 
          let start' = the other vertex of e, 
          let g' = graph g with node start deleted, 
          let path = longestPath g' start' end ] 

(maximumBy исходит от Data.List и comparing от Data.Ord)

нотабене Ребра будут сгенерированы в обратном порядке.

Существует множество деталей реализации, которые нужно выяснить, и, в частности, вам придется немного изменить это, чтобы обрабатывать случай, когда нет пути от start до node (что может произойти после того, как вы начнете удаление узлы), но это подход, с которого я начну.