无法转换简单的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。但是，如果你正在处理标准图表，这应该不重要。