Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
47 lines (44 sloc) 2.25 KB
% Copyright (c) 2011-2012, Tom Van Cutsem, Vrije Universiteit Brussel
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions are met:
% * Redistributions of source code must retain the above copyright
% notice, this list of conditions and the following disclaimer.
% * Redistributions in binary form must reproduce the above copyright
% notice, this list of conditions and the following disclaimer in the
% documentation and/or other materials provided with the distribution.
% * Neither the name of the Vrije Universiteit Brussel nor the
% names of its contributors may be used to endorse or promote products
% derived from this software without specific prior written permission.
%
%THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
%ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
%WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
%DISCLAIMED. IN NO EVENT SHALL VRIJE UNIVERSITEIT BRUSSEL BE LIABLE FOR ANY
%DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
%(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES
%LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
%ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
%(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
%SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
% A sequential implementation of the Google MapReduce pattern
-module(mapreduce_sequential).
-export([mapreduce/3]).
-import(lists, [foreach/2]).
%% Input = List[{K1, V1}]
%% Map(K1, V1) -> returns a List[{K2,V2}]
%% Reduce(K2, List[V2]) -> returns a List[V2]
%% Returns a Map[K2,List[V2]]
mapreduce(Input, Map, Reduce) ->
%% Map Phase
IntermediateLists = lists:map(fun ({K1,V1}) -> Map(K1,V1) end, Input),
IntermediatePairs = lists:flatten(IntermediateLists),
IntermediateMap = lists:foldl(
fun({K2,V2}, Dict) ->
dict:append(K2,V2,Dict)
end, dict:new(), IntermediatePairs),
%% Reduce Phase
dict:map(fun(K2, ListOfV2) ->
Reduce(K2, ListOfV2)
end, IntermediateMap).