SUPAFREAK!

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import Data.AminoAcid                 -- http://lpaste.net/107071
import Data.Map (Map)
import qualified Data.Map as Map

-- SUPAFREAK!
-- A solution to the haskell exercise posted at http://lpaste.net/107286

pool :: [[AcidName]]
pool = [[A, C, D], [E, F], [G, H, I], [E, F], [K, L, M, N], [P, Q], [R]]

{--

Okay, so the very first thing we do is to remap the pool to a multi-map
structure:

 --}

mlist :: [[a]] -> Map Int [[a]]
mlist = foldr (\elts -> Map.insertWith (++) (length elts) [elts]) Map.empty

{--

*Main> mlist pool
fromList [(1,[[R]]),
          (2,[[E,F],[E,F],[P,Q]]),
          (3,[[A,C,D],[G,H,I]]),
          (4,[[K,L,M,N]])]

 --}

-- a) is just a co-return (extraction) down from mlist's values

lenSort :: [[a]] -> [[a]]
lenSort = concat . Map.elems . mlist 

{--

*Main> lenSort pool
[[R],[E,F],[E,F],[P,Q],[A,C,D],[G,H,I],[K,L,M,N]]

a) Q.E.D.

 --}

-- b. freqSort

{--

Now that we have elements grouped by length already in mlist, we
remap them to a frequency distribution

 --}

mlist' :: [[[a]]] -> Map Int [[a]]
mlist' = foldr (\elts -> Map.insertWith (++) (length elts) elts) Map.empty

freqSort :: [[a]] -> [[a]]
freqSort = concat . Map.elems . mlist' . Map.elems . mlist

{--

*Main> freqSort pool
[[R],[K,L,M,N],[A,C,D],[G,H,I],[E,F],[E,F],[P,Q]]

b) Q.E.D.

 --}