Big Data/BI Zone is brought to you in partnership with:
DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Google MapReduce In A Week: Functional Programming Warm-up Exercises

03.13.2009
| 4844 views |
  • submit to reddit
        // Solutions to the Google MapReduce in a Week: Functional Programming Warm-up Exercises

-- Exercise 1
concat = foldr (flip (foldr (:))) []

-- Exercise 2
-- The hashtable (map) version
import qualified Data.Map as Map
groupMap xs = foldr f Map.empty xs
    where f (k, v) m = Map.insertWith (++) k [v] m

-- The hashtable- (map-)free version
group xs = foldr insert [] xs
insert (k, v) table = fst $ foldr f ([(k, [v])], []) table
    where f (k', vs) (ys, xs)
            = (if k == k' then (k, v:vs):xs else (k', vs):ys, (k', vs):xs)

-- Exercise 3
partition k xs = foldr f ([],[]) xs
    where f x (lts, gtes)
            | x < k     = (x:lts, gtes)
            | otherwise = (lts, x:gtes)

-- Exercise 4
(.) f g x = f (g x)