What is a pure functional approach to indexing functions?

Question

For example, a function that receives a list of trades and returns a list of value sums, indexed by time:

trades = [{time:1,value:8}, {time:1.1,value:8},... {time:1.2,value:7}, time:2.1,value:8} ...]
total_value_by_time = {}

for trade in trades
    if not exists(total_value_by_time[trade.time])
        total_value_by_time[trade.time] = 0
    total_value_by_time[trade.time] += trade.value 

I couldn't figure out how to replicate this algorithm with none of the common FP approaches such as map and reduce. What is a pure functional way to do it?

Answer 1

I'd say the most natural solution is to first group the list by equal times, then sum up each group's values. In Haskell,

tradesAccum = sortBy (compare`on`time)
          >>> groupBy ((==)`on`time)
          >>> map (map value >>> sum)

In case you try this and don't know where to find the necessary standard functions:

import Data.List (sortBy, groupBy)
import Data.Function (on)
import Control.Arrow ((>>>))

---

We can also make this nicely parallelisable and as efficient as with Map, but still use only lists. This is basically a variation of the above, but completely implemented as a prune-enabled, parallel merge sort:

import Control.Parallel.Strategies

uniqueFstFoldSnd :: (Ord a, Semigroup b) => [(a, b)] -> [(a, b)]
uniqueFstFoldSnd [] = []
uniqueFstFoldSnd [x] = [x]
uniqueFstFoldSnd l = uncurry merge .
    (withStrategy $
        if len>100 then parTuple2 (evalList r0) (evalList r0)
                   else r0
    ) $ uniqueFstFoldSnd *** uniqueFstFoldSnd $ splitAt (len `quot` 2) l
  where merge [] ys = ys
        merge xs [] = xs
        merge ((k, u):xs) ((l, v):ys)
         | k < l      = (k, u   ) : merge        xs  ((l,v):ys)
         | k > l      = (l, v   ) : merge ((k,u):xs)        ys
         | otherwise  = (k, u<>v) : merge        xs         ys
        len = length l

Note that the parallelism doesn't yet give a significant performance improvement; I'm still experimenting with Strategies...

Answer 2

There is a function for this exposed as part of the Data.Map API. Your example boils down to fromListWith (+).

Answer 3

Well here's how I'd write your code in Haskell

import Data.Map as M
import Data.List(foldl')

total :: [(Double Integer)] -> Map (Double, Integer)
total = foldl' step M.empty
  where step m (key, val) | member key m = M.update key (+val) m
                          | otherwise    = M.insert key val m

In general folds are the functional approach to iteration and you use them to replace loops that accumulate things. In this specific case, you could also use group

Answer 4

You can think of this function as "breaking down" a list and then building back up a mapping or dictionary from the results. It makes for a relatively uninteresting map-reduce problem since everything is in the reduce.

import qualified Data.Map as Map
import           Data.Map (Map)

type Time = Double
type Value = Double
data Trade = Trade { time :: Time, value :: Value }

-- given some `mapReduce` function...
accum = mapReduce mapper reducer where
  mapper :: Trade -> Map Time Value
  mapper tr = Map.singleton (time tr) (value tr)

  -- This inherits the associativity of (+) so you can 
  -- reduce your mapper-generated `Map`s in any order. It's 
  -- not idempotent, though, so you must ensure that each datum
  -- is added to the reduction exactly once. This is typical
  -- for map reduce
  reducer :: [Map Time Value] -> Map Time Value 
  reducer maps = Map.unionsWith (+)

-- without parallelization this looks like you'd expect
--     reducer . map mapper :: [Trade] -> Map Time Value

Where the interesting Map functions come from the Haskell containers package: Map.singleton and Map.unionsWith.

Generally, "breaking down" and "reducing" are all algorithms called "catamorphisms" (cata- is a Greek prefix for breaking "downward", just like "catabolism"). Pure functional programs are absolutely amazing at doing catamorphisms as they are usually "fold"s of some kind.

That said, we can write this same algorithm as a fold in just one pithy line. We'll use Data.Map.Strict and foldl' to make sure that this Haskell code doesn't generate any spare, useless thunks.

import qualified Data.Map.Strict as Map

accum :: [Trade] -> Map Time Value
accum = foldl' (\oldMap tr -> Map.insertWith (+) (time tr) (value tr) oldMap) Map.empty

Answer 5

MapCollectReduce approach.

insert (a,b) [] = [(a,[b])]
insert (a,b) ((k, vs):rest) | a == k    = (k, b:vs):rest
                            | otherwise = (k, vs):(insert (a,b) rest)

collect ((k,v):kvs) = insert (k,v) (collect kvs)
collect [] = []

trades l = map (\(k, vs) -> (k, sum vs)) $ collect l

I coded a very primitive collect function, that performs pretty horribly. Once you have that, you take your data and do a map (not here in this case, consider it a map id). Then you collect the pairs, meaning, you group the pairs by it's key. And finally you calculate on the collected data: you sum all the values for a given key.

@leftaroundabout and @jozefg's answers probably outperform this one by a mile, but with a good library for mapCollectReduce I believe this will be faster. (This also parallelizes great, but I don't think that's of importance to you)