hammingDist1.hs

import           Control.Arrow       (second)
import           Data.List.Extra     (sort, groupSortOn)

-- Assuming we sort through counting sort 
-- Including the sort inside groupSortOn
-- Sorting of tuples is radix sort with base = max coordinate

-- type alias for readability
type Partition x = [[x]]
type EquivalenceClass x = [x]
type ID = Int      -- Unique id for each input string
-- simple functions
map2 = map . map
idx = zip [0 ..] -- index a list
hasDuplicate = any ((> 1) . length) . groupSortOn id
------------
hammingDistance1 :: [String] -> Bool
hammingDistance1 input = or $ zipWith condition p s
  where
    p = equivalences input
    s = tail $ reverse $ equivalences $ map reverse input

condition :: Partition ID -> Partition ID -> Bool
condition a b = hasDuplicate $ zip (h a) (h b)
  where
    h = map snd . sort . (uncurry (map . flip (,)) =<<) . idx

equivalences :: [String] -> [Partition ID]
equivalences = equivalences'. return . idx 

equivalences' :: Partition (ID, String) -> [Partition ID]
equivalences' xs
  | null t = [ys]
  | otherwise = ys : equivalences' (concatMap nextLayer xs)
  where
    t = snd $ head $ head xs
    ys = map2 fst xs

nextLayer :: EquivalenceClass (ID, String) -> [EquivalenceClass (ID, String)]
nextLayer = map2 (second tail) . groupSortOn (head . snd)