D.B.Cooper - 1 year ago 122
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?

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download