map Implementation fun map f[] 三 [] map f (x:xs)=(f x):(map f xs) This implementation moves left-to-right across the list,mapping elements one at a time ..But does it need to? 17
17 map Implementation ◼ This implementation moves left-to-right across the list, mapping elements one at a time ◼ … But does it need to? fun map f [] = [] | map f (x::xs) = (f x) :: (map f xs)
Implicit Parallelism In map In a purely functional setting,elements of a list being computed by map cannot see the effects of the computations on other elements If order of application of fto elements in list is commutative,we can reorder or parallelize execution This is the“secret”that MapReduce exploits 18
18 Implicit Parallelism In map ◼ In a purely functional setting, elements of a list being computed by map cannot see the effects of the computations on other elements ◼ If order of application of f to elements in list is commutative, we can reorder or parallelize execution ◼ This is the “secret” that MapReduce exploits
References http://net.pku.edu.cn/~course/cs501/2008/resou rce/haskell/functional.ppt http://net.pku.edu.cn/~course/cs501/2008/resou rce/haskell/ 19
19 References ◼ http://net.pku.edu.cn/~course/cs501/2008/resou rce/haskell/functional.ppt ◼ http://net.pku.edu.cn/~course/cs501/2008/resou rce/haskell/
NC&IS MapReduce Basic
MapReduce Basic
Typical Large-Data Problem Iterate over a large number of records Map ■ Extract something of interest from each Shuffle and sort intermediate results Aggregate intermediate ■ Generate final output Key idea:provide a functional abstraction for these two operations 21
21 Typical Large-Data Problem ◼ Iterate over a large number of records ◼ Extract something of interest from each ◼ Shuffle and sort intermediate results ◼ Aggregate intermediate results ◼ Generate final output Key idea: provide a functional abstraction for these two operations (Dean and Ghemawat, OSDI 2004)