Elixir: Map Reduce Monad

map_reduce_monad.exs

# MapReduce.lift
# This lifts a function from A -> B to [A] -> B:
# It first maps [A] to [B] 
# Then reduces [B] to B
defmodule MapReduce do

    # map is the A -> B
    # {reduce, id, direction} is a list monoid, which is dependent on the internal type of the list
    # reduce is the associative binary operator
    # id is the identity element
    # direction is the direction of the evaluation for the reduction/fold
    # :left direction means reducing from a, b where a is first value and b is the second value, a can be the id
    # :right direction means reducing from a, b where a is the penultimate value and b is the last value, b can be the id
    # note that Elixir is strict (except in its macros), so :left direction will not blow the stack unlike Haskell's lazy evaluation

    def lift(map, {reduce, id, :left}) do
        &(map_reducing_left(&1, map, reduce, id))
    end

    def lift(map, {reduce, id, :right}) do
        &(map_reducing_right(&1, map, reduce, id))
    end

    defp map_reducing_left([head|tail], map, reduce, id) do
        map_reducing_left(tail, map, reduce, reduce.(id, map.(head)))
    end

    defp map_reducing_left([], _, _, id) do
        id
    end

    # fold right is not tail-recursive, might blow the stack!
    # http://stackoverflow.com/a/3429693/582917
    defp map_reducing_right([head|tail], map, reduce, id) do
        reduce.(map.(head), map_reducing_right(tail, map, reduce, id))
    end

    defp map_reducing_right([], _, _, id) do
        id
    end

end

sum = MapReduce.lift(
    fn x -> x end,
    {
        fn x, y -> x + y end,
        0,
        :left
    }
)

IO.puts sum.([1, 2, 3]) # 6

diffl = MapReduce.lift(
    fn x -> x end,
    {
        fn x, y -> x - y end,
        0,
        :left
    }
)

IO.puts diffl.([1, 2, 3]) # -6 <-> (((0 - 1) - 2) - 3)

diffr = MapReduce.lift(
    fn x -> x end,
    {
        fn x, y -> x - y end,
        0,
        :right
    }
)

IO.puts diffr.([1, 2, 3]) # 2 <-> (1 - (2 - (3 - 0)))

member = fn x ->
    MapReduce.lift(
        fn y -> y == x end,
        {
            fn a, b -> a or b end,
            false,
            :left
        }
    )
end

IO.puts member.(3).([1, 2, 3]) # true

mapl = fn f -> 
    MapReduce.lift(
        fn x -> f.(x) end,
        {
            fn a, b -> a ++ [b] end,
            [],
            :left
        }
    )
end

IO.puts inspect mapl.(fn x -> x + 1 end).([1, 2, 3]) # [2, 3, 4] <-> ++(++(++([], 2), 3), 4)

mapr = fn f -> 
    MapReduce.lift(
        fn x -> f.(x) end,
        {
            fn a, b -> [a|b] end,
            [],
            :right
        }
    )
end

IO.puts inspect mapr.(fn x -> x + 1 end).([1, 2, 3]) # [2, 3, 4] <-> [2|[3|[4|[]]]]