问Haskell中的平衡分区

EN

balancedPartition :: (Num a, Ord a) => [a] -> ([a], [a])
balancedPartition = snd . head . partitionsByBadness . sort
  where
    -- recursively builds a list of possible partitionings and their badness
    -- sorted by their (increasing) badness
    partitionsByBadness []     = [(0, ([], []))]
    partitionsByBadness (x:xs) = let res = partitionsByBadness xs
                                     withX = map (      (+x) *** first  (x:)) res
                                     sansX = map (subtract x *** second (x:)) res
                                 in merge withX $ normalize sansX

    -- When items are added to the second list, the difference between the sums
    -- decreases - and might become negative
    -- We take those cases and swap the lists, so that the first list has always
    -- a greater sum and the difference is always positive
    -- So that we can sort the list again (with linear complexity)
    normalize xs = let (neg, pos) = span ((<0) . fst) xs
                   in merge pos $ reverse $ map (negate *** swap) neg

-- merge two sorted lists (as known from mergesort, but
-- omits "duplicates" with same badness)
merge :: Ord k => [(k, v)] -> [(k, v)] -> [(k, v)]
merge []         zss        = zss
merge yss        []         = yss
merge yss@(y:ys) zss@(z:zs) = case comparing fst y z of
                                LT -> y : merge ys zss
                                EQ -> merge ys zss
                                GT -> z : merge yss zs