CSE230 Fa16 - MapReduce

Map-Reduce

> module MapReduce (mapReduce) where
> 
> import qualified Data.Map as M
> import List
> import Prelude hiding (map, reduce, concat, foldr, foldr1)
> expand   :: (a -> List (k, v)) -> List a -> List (k, v)
> group    :: (Ord k) => List (k, v) -> M.Map k (List v)
> collapse :: (v -> v -> v) -> M.Map k (List v) -> M.Map k v

The following is a super simplified implementation of Map-Reduce using the Lists and Data.Map.

> mapReduce :: (Ord k) => (a -> List (k, v))
>                      -> (v -> v -> v)
>                      -> List a
>                      -> M.Map k v
> 
> mapReduce fm fr xs = kvm
>   where
>     kvs   = expand      fm xs     -- step 1
>     kvsm  = group       kvs       -- step 2
>     kvm   = collapse fr kvsm      -- step 3

The Problem If you solved foldr1 then you should get a single type error below, in the call to foldr1 in collapse. Fix the error by modifying the refinement type specifications only (do not modify any code).

Note: This problem requires you to have solved the foldr1 problem from List.lhs; otherwise no points.

Next, we briefly describe and show each step of the mapReduce function.

Step 1: Map Elements into Key-Value Lists

> {-@ expand  :: (a -> List (k, v)) -> List a -> List (k, v) @-}
> expand f xs = concat (map f xs)

Step 2: Group By Key

> {-@ group :: (Ord k) => List (k, v) -> M.Map k (List v) @-}
> group     = foldr addKV  M.empty
> 
> addKV (k,v) m = M.insert k vs' m
>   where
>     vs'       = add v (M.findWithDefault empty k m)

Step 3: Reduce Each Key to Single Value

> {-@ collapse  :: (v -> v -> v) -> M.Map k (List v) -> M.Map k v @-}
> collapse f = M.map (foldr1 f)
> 
> toList :: M.Map k v -> List (k, v)
> toList = M.foldrWithKey (\k v acc -> add (k, v) acc) empty