content: module Mapreduce_bare () where
  
  import Language.Haskell.Liquid.Prelude
  import Data.List (foldl')
  
  ----------------------------------------------------------------
  --- Step 1: Map each element into key-value list (concatMap) ---
  ----------------------------------------------------------------
  
  expand          :: (a -> [(k,v)]) -> [a] -> [(k, v)]
  expand f []     = []
  expand f (x:xs) = (f x) ++ (expand f xs)
  
  ----------------------------------------------------------------
  --- Step 2: Group By Key ---------------------------------------
  ----------------------------------------------------------------
  
  group ::[(Int, v)] -> [(Int, [v])]
  group = foldl' addKV [] 
    
  addKV m (k, v) = insert k vs' m
    where vs' = v : (findWithDefault [] k m)
  
  insert key value [] 
    = [(key, value)]
  insert key value ((k,_):kvs)
    | k == key
    = (key, value):kvs
  insert key value (kv:kvs)
    = kv : insert key value kvs  
  
  findWithDefault r _ ([]) 
    = r
  findWithDefault r k ((key,value):_) 
    | k `eq` key 
    = value
  findWithDefault r k (_:kvs) 
    = findWithDefault r k kvs 
  
  ----------------------------------------------------------------
  --- Step 3: Group By Key ---------------------------------------
  ----------------------------------------------------------------
  
  collapse f = foldrWithKey reduceKV []
    where reduceKV k (v:vs) acc = (k, foldl' f v vs) : acc
          reduceKV k []     _   = crash False -- error $ show (liquidAssertB False)
  
  foldrWithKey f = foldr (\(k, v) acc -> f k v acc) 
  
  ----------------------------------------------------------------
  --- Putting it All Together ------------------------------------
  ----------------------------------------------------------------
  
  mapReduce fmap fred xs = collapse fred $ group $ expand fmap xs
  
  ----------------------------------------------------------------
  --- "Word Count" -----------------------------------------------
  ----------------------------------------------------------------
  
  wordCount  = mapReduce fm plus 
    where fm = \doc -> [ (length w, 1) | w <- words doc]
  
  mytest = 
    let docs = [ "this is the end"
               , "go to the end"
               , "the end is the beginning"]
    in putStrLn $ isZero {- show -} $ wordCount docs
   
  isZero [_]  = "Positive" 
  isZero _    = "Negative"
  
  