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.