D.B.Cooper - 1 year ago 92

Python Question

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 Source

^{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
```