In a list of pairs, replace snds with median of all snds with the same fst

Question

Given is a list of pairs. I want to replace the second element of all pairs with the median of the second elements of all pairs with the same first element.

For example:

[("a",1.0),("b",3.0),("a",2.0),("a",4.0)]
->
[("a",2.0),("b",3.0),("a",2.0),("a",2.0)]

The order of the elements in the resulting list is not important. So the following result would be equally valid:

[("a",2.0),("a",2.0),("a",2.0),("b",3.0)]

My current solution looks as follows:

import Control.Arrow
import qualified Data.Map as M

median :: Fractional a => [a] -> a
median xs | null xs  = error "empty list"
          | odd  len = xs !! mid
          | even len = meanMedian
                where  len = length xs
                       mid = len `div` 2
                       meanMedian = (xs !! mid + xs !! (mid+1)) / 2

solve :: [(String, Float)] -> [(String, Float)]
solve pairs = map replaceWithMedian pairs
    where
        medianMap = map (mapSnd (:[])) >>> M.fromListWith (++) >>> M.toList
                        >>> map (mapSnd median) >>> M.fromList
        mapSnd f (x, y) = (x, f y)
        replaceWithMedian (x, y) = (x, M.findWithDefault 0 x (medianMap pairs))

main :: IO ()
main = print $ solve [("a",1.0),("b",3.0),("a",2.0),("a",4.0)]

solve feels unnecessary long to me. I'm looking for more elegant/terse solution, not character-count-wise but with a simpler algorithm.

Answer 1

Fixing things first

First of all, median is wrong:

median [1,2,3,4,5] /= median [3,1,4,5,2]

Both should return 3, but on the first list median returns 3 and on the latter 4. Make sure to sort your list, or state in the (currently missing) documentation that your list has to be sorted. Also, using !! twice is rather slow. Instead, drop the first elements up to mid and then take the mean:

median :: (Fractional a, Ord a) => [a] -> a
median [] = error "median: empty list"
median xs
 | odd len  = xs' !! mid
 | otherwise = mean $ take 2 $ drop mid $ xs'
 where 
     len = length xs
     mid = len `div` 2
     xs' = sort xs

mean :: (Fractional a) => [a] -> Maybe a
mean xs = -- exercise; it's not trivial to get this right

-- Alternatively, just use meanDuo in median:
meanDuo :: Fractional a => [a] -> a
meanDuo [x,y] = -- ...

Also, if you use error, make sure to include the function's name in the error message; best practice include the completely qualified name, i.e.

error "Data.TupleMagic.median: empty list"

After all, there are (usually) no stack traces, and it's really nice to know where things went wrong. Note that you should add this behaviour in a documentation, since the type doesn't really tell what would happen on an empty list. Since Fractional a is also an instance of Num, any fixed number could be feasible. Alternatively use Maybe a as return type or NonEmpty as input.

Use the tools you have at hand

mapSnd is second from Control.Arrow. Also, Data.Map is an instance of Functor, which means you can replace

M.toList >>> map (second f) >>> M.fromList

with

fmap f 

Furthermore, be honest. Although medianMap is called *Map, it's actually a function. While GHC might call it only once, it's not guaranteed, so remember the map. And last, since you know that every key x will be contained in toMap pairs, you can use Data.Map.! instead of Data.Map.findWithDefault:

solve :: [(String, Float)] -> [(String, Float)]
solve pairs = map replaceWithMedian pairs
  where
    toMap     = map (second pure) >>> M.fromListWith (++) >>> fmap median
    medianMap = toMap pairs
    replaceWithMedian (x, _) = (x, medianMap M.! x)

Furthermore, there's usually no reason to use Float nowadays, unless you've checked

• that it's faster,
• that it's reduced accuracy fulfils your needs, and
• you're having memory constraints (which usually also contradicts String and lists).

Instead, Double is used most of the time.

Answer 2

Here are few notes about current implementation of solve:

• As you are using Control.Arrow, mapSnd is already here, see second.
• Using M.findWithDefault can lead to hiding implementation errors because it replaces "key not found" error (which could not occur if code is correct) with random value. I would suggest using Map.! as it explicitly states that "not found" is not expected.
• medianMap is a pure function and it is applied only to pairs but GHC is not smart enough to calculate medianMap pairs only once. That means you are building new map of medians for each element of pairs. You can let mapOfMedians = medianMap pairs to be sure that it is calculated only once.

It is also possible to solve little bit more concisely:

solve
  = concatMap (\(k,xs) -> replicate (length xs) (k, median xs))
  . M.toList
  . foldl' (\m (k,v) -> M.insertWith' (++) k [v] m) M.empty

This could also be a bit faster as it does not traverse map of medians on each pair.

Answer 3

Helper function

Your code feels complicated because you did not write a helper function, I suggest the function:

allLookUps :: Eq b1 => b1 -> [(b1, b)] -> [b]

Example usage:

*Main> allLookUps 4 [(4, 314), (0,5), (4, 7)]
[314,7]

To find all the second items that match to the first.

Using it, solve is very easy, we just apply it to all the first items and create the result tuples:

solve xs = map (\x -> (x, median $ allLookUps x xs)) $ map fst xs

Explicit pattern matching

null xs requires some thinking and confuses imperative programmers about another null.

I suggest explicit pattern matching to be immediately obvious:

median []  = error "empty list"
-- etc...

Be general with your types

solve can have a way more general type than you wrote, look:

solve :: (Eq b, Fractional b1) => [(b, b1)] -> [(b, b1)]

I see no reason to restrict it to String and Float.