Schulze letter voting2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import Data.List as L
import Data.Map as M
import Data.Ord

abc="ABCDEFGHIJKLMNOPQRSTUVWXYZ"

-- generate all letter pairs from word (duplicates filtered), missing letters put at the end of the list with equal weight
votes word = L.map (\[a,b]->(a,b)) [x | x<-L.subsequences w, L.length x == 2] ++ [(a,b)|a <- w, b <- abc L.\\ w]
            where w = L.nub word

-- make map of letterpair frequencies
pairMap dict = M.fromListWith (+) [(p, 1) | p <- concatMap votes $ lines dict]
 
 -- Floyd–Warshall for widest path
schulzeDist pmap = L.foldl' schulzeUpdate pmap abc
                where schulzeUpdate m k = M.mapWithKey (\(a,b) n -> max n (min (get (a,k)) (get (k,b)))) m
              get k = M.findWithDefault 0 k pmap
         
-- custom compare using the map
comp pmap a b = compare (get (b,a)) (get (a,b))
        where get k = M.findWithDefault 0 k pmap

-- sorting
sortByDict dict = sortBy (comp $ schulzeDist $ pairMap dict) abc
            
main = do
             dict <- readFile "words.txt"
             putStrLn $ sortByDict dict