Sum up distances of a permutation list (Haskell)

Question

I have a list of Towns and a function, which gives out the distance between two of them. For example:

dist!(Bielefeld,Muenchen) = 598

Now I want to make a function where I can calculate the full length of a random tour between all Towns. For example:

tourlength [a permutation of the 12 Towns] = whole way you have to travel (as Int)

I hope you know what I mean. I'm not sure how to integrate the dist! function into the new one.

My second problem is that I want to calculate which city has the shortest distance to a second one. To solve that, I wanted to use the greedy function below:

greedy a []     = [a]
greedy a X      = a : greedy (z X - [z])
              z = argmin x : dist a x 
tspgreedy X     = greedy (s x - [s])

But I don't know how to translate it to haskell...

Thanks for food for thought

Answer 1

In answer to your first question, one way of calculating the total distance of a journey that passes through a series of towns goes like this:

import Data.Complex (Complex, magnitude)

type Town = Complex Double

dist :: Town -> Town -> Int
dist x y = round $ magnitude (x-y)

journeyDistance :: [Town] -> Int
journeyDistance itinerary = sum . zipWith dist itinerary . drop 1 . cycle $ itinerary

(Don't be put off by the use of complex numbers; you can define your towns and the distances between them however you like, say, by a table lookup.) The idea behind this code is to zip the list representing the itinerary with itself -- but offset by one town (hence drop 1) -- calculating distances as we zip. That is, we pair every town with its successor in the itinerary, but the pairing operation is not the usual tuple construction but rather our own distance function (hence zipWith dist). cycle constructs an infinite repetition of the itinerary to ensure there are enough towns to "fully zip" with the original, finite list of towns.

In fact, because the second list in the zip "cycles around", the last town in the first list will be paired with the first town, forming a roundtrip. If you'd rather end your journey in the last town without returning to the first, then you could write the function like this:

journeyDistance itinerary = sum . init . zipWith dist itinerary . drop 1 . cycle $ itinerary

A quick way to solve your second problem might be like this:

import Data.List (minimumBy, tails)
import Data.Ord (comparing)

closestTowns :: [Town] -> (Town, Town)
closestTowns towns = minimumBy (comparing $ uncurry dist) [(x, y) | (x:xs) <- tails towns, y <- xs]