<div dir="ltr">Dear Haskell Cafe,<div><br></div><div>Given a set of sets, and a particular target set, I want to find the sets that are nearest (in terms of Hamming distance) to the target set. </div><div><br></div><div>I am using the following code:</div><div><br></div><div><div>import Data.List    </div><div>import qualified Data.Set as Set</div><div><br></div><div>nearest_k :: Ord a => Int -> [(Set.Set a, v)] -> Set.Set a -> [(Set.Set a, v)]</div><div>nearest_k k bs b = take k bs' where</div><div>    bs' = sortOn (hamming b) bs</div><div><br></div><div>hamming :: Ord a => Set.Set a -> (Set.Set a, v) -> Int</div><div>hamming x (y, _) = hamming_distance x y</div><div><br></div><div>hamming_distance :: Ord a => Set.Set a -> Set.Set a -> Int</div><div>hamming_distance xs ys = Set.size (Set.difference xs ys) + Set.size (Set.difference ys xs)</div><div><br></div><div><br></div><div><br></div><div>subsets :: [a] -> [[a]]</div><div>subsets []  = [[]]</div><div>subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)    </div><div><br></div><div>int_lists :: [[Int]]</div><div>int_lists = subsets [1..20]</div><div><br></div><div>values :: [(Set.Set Int, Int)]</div><div>values = map f (zip [1..] int_lists) where</div><div>    f (i, x) = (Set.fromList x, i)</div><div><br></div><div>test = nearest_k 8 values (Set.fromList [1,2,3])</div></div><div><br></div><div>----</div><div><br></div><div>This works ok for the test above (with sets of ints), but is rather slow in my actual application (in which the sets are large sets of ground atoms of first-order logic). Is there some major optimization I should be doing here? </div><div><br></div><div>thanks,</div><div>Richard</div></div>