D.B.Cooper D.B.Cooper - 13 days ago 6
Python Question

Can't convert simple python code to haskell

I'm trying to convert this to Haskell,

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


This is as far as I got,

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)]


I can't figure out how to do the for loop with recursion. Anyone have an idea?

Answer

Note: This answer is written in literate Haskell. Save it as *.lhs and load it in GHCi.

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

Let us have a look at your Python code and think of how the Haskell function should look like:

def longest_path(edge, edges):

Allright. We start with a single edge and a list of edges. Therefore, we should write a function with that type:

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

Now, what do we do in our Python code? Apparently, we remove our current edge from the list of edges:

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

Luckily, there is a function to remove the first occurence of an element in a list, namely delete:

>     let remaining = delete edge edges

So far so good. Now, possibles is just the list of edges with have the correct end-point:

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

That's easy too:

>         possibles = filter (edge `connectedTo`) edges

And then we look for the longest chain for all the possible edges.

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

Since we cannot modify maxchain in Haskell, let's create all those intermediate paths instead:

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

This is where the recursion happens. For every Edge in our possible edges, we create the longestPath of that edge and the remaining ones.

Most of for loops can be expressed as map and a following fold. The fold we will use is maximumBy, where we compare the lists by their length with comparing length:

>     in edge : maximumBy (comparing length) paths

We've used a small helper though, connectedTo. But that's easy:

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

All code at once:

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
Comments