無法轉換簡單的Python代碼哈斯克爾

Question

我試圖將其轉換爲哈斯克爾，

def longest_path(edge, edges): 
    remaining = list(edges) 
    del remaining[remaining.index(edge)] 
    possibles = [x for x in remaining if x[0] == edge[1]] 
    maxchain = [] 
    for c in possibles: 
     l = longest_path(c, remaining) 
     if len(l) > len(maxchain): 
      maxchain = l 
    return [edge] + maxchain 

這是據我得到的，

deleteN :: Int -> [a] -> [a] 
deleteN _ []  = [] 
deleteN i (x:xs) 
    | i == 0 = xs 
    | otherwise = x : deleteN (i-1) xs 

longestPath edge edges = let 
    remaining = deleteN (fromMaybe $ elemIndex edge edges) edges 
    possibiles = [opt | opt <- remaining, (fst opt) == (snd edge)] 

我想不出如何用遞歸做for循環。任何人有想法？

Answer 1

^{注意：這個答案寫在文學Haskell。將其保存爲​​3210並將其加載到GHCi中。}

> import Data.Ord (comparing) 
> import Data.List (delete, maximumBy) 
> type Edge = (Int, Int) 

讓我們來看看你的Python代碼，並認爲Haskell的功能應該如何看起來像：

def longest_path(edge, edges): 

還好吧。我們從一個邊和一個邊的列表開始。因此，我們應該編寫一個這樣的函數：

> longestPath :: Edge -> [Edge] -> [Edge] 
> longestPath edge edges = 

現在，我們在我們的Python代碼中做什麼？

remaining = list(edges) 
    del remaining[remaining.index(edge)] 

幸運的是，刪除元素第一次出現在列表中，即delete功能：

>  let remaining = delete edge edges 

所以很顯然，我們從邊緣的列表中刪除我們目前edge非常好。現在，possibles只是用正確的終點邊緣的名單：

possibles = [x for x in remaining if x[0] == edge[1]] 

那是太容易了：

>   possibles = filter (edge `connectedTo`) edges 

然後我們尋找所有可能的邊緣鏈最長。

maxchain = [] 
    for c in possibles: 
     l = longest_path(c, remaining) 
     if len(l) > len(maxchain): 
      maxchain = l 

既然我們不能在Haskell修改maxchain，讓我們創建所有的中間路徑來代替：

>   paths = [] : map (\e -> longestPath e remaining) possibles 

這就是遞歸發生。對於我們可能的邊緣中的每個Edge，我們創建該邊緣的longestPath和其餘邊緣。

for環的大部分可以表示爲map和以下的摺疊。我們將使用摺疊是maximumBy，在這裏我們通過它們的長度與comparing length比較列表：雖然

>  in edge : maximumBy (comparing length) paths 

我們已經使用了一個小幫手，connectedTo。但是，這很簡單：

> connectedTo :: Edge -> Edge -> Bool 
> connectedTo (_,b) (x,_) = b == x 

所有代碼一次：

import Data.List (delete, maximumBy) 
import Data.Ord (comparing) 

type Edge = (Int, Int) 

longestPath :: Edge -> [Edge] -> [Edge] 
longestPath edge edges = 
    let remaining = delete edge edges 
     possibles = filter (edge `connectedTo`) edges 
     paths = [] : map (\e -> longestPath e remaining) possibles 
    in edge : maximumBy (comparing length) paths 

connectedTo :: Edge -> Edge -> Bool 
connectedTo (_,b) (x,_) = b == x 

Answer 2

這個python代碼並不是最好的......我沒有看到找到edge的索引，然後del這個點......只是使用edges.remove(edge)。

在Haskell中以同樣的方式你可以filter邊緣：

remaining = filter (/= edge) edges 

現在，您for循環是迄今爲止跟蹤最好的結果。這在Haskell中可以通過使用累加器參數的遞歸函數完成。然而這裏的模式是一個fold：

foldr f [] possibilities 

其中：

f c maxchain = let l = longestPath c remaining 
       in 
        if length l > length maxchain then l else maxchain 

您可以修改longestPath也返回路徑的長度，避免length來電...

---

完整的代碼如下所示：

longestPath edge edges = foldr f [] possibilities 
    where 
    remaining = filter (/= edge) edges 
    possibilities = [opt | opt <- remaining, (fst opt) == (snd edge)] 
    f c maxchain = if length l > length maxchain then l else maxchain 
     where 
     l = longestPath c remaining 

---

正如評論，而不是filter指出，你可以使用delete edge edges只刪除一個發生edge。但是，如果你正在處理標準圖表，這應該不重要。