What are Monads?

Had some fun with with my monad protocol, I benchmarked it’s flat_map versus Enum.flat_map (via the awesome Benchee), and I did it with enum in two ways, both the ‘correct’ return, and the way that it would traditionally be done in Elixir (which is marked as the *_wrong one as it is not following the flat_map laws properly, meaning it also returns a list instead of the actual object). I benched with a list, a map, and a map of a single element (named ValueMap). The results:

Operating System: Linux
CPU Information: Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz
Number of Available Cores: 2
Available memory: 8.011072 GB
Elixir 1.6.0-dev
Erlang 20.0
Benchmark suite executing with the following configuration:
warmup: 5.00 s
time: 5.00 s
parallel: 1
inputs: List, Map, ValueMap
Estimated total run time: 1.50 min



Benchmarking with input List:
Benchmarking Elixir.Enum.flat_map...
Benchmarking Elixir.Enum.flat_map_wrong...
Benchmarking ExCore.Monad.flat_map...

Benchmarking with input Map:
Benchmarking Elixir.Enum.flat_map...
Benchmarking Elixir.Enum.flat_map_wrong...
Benchmarking ExCore.Monad.flat_map...

Benchmarking with input ValueMap:
Benchmarking Elixir.Enum.flat_map...
Benchmarking Elixir.Enum.flat_map_wrong...
Benchmarking ExCore.Monad.flat_map...

##### With input List #####
Name                                 ips        average  deviation         median
ExCore.Monad.flat_map             3.71 M        0.27 μs  ±1318.59%        0.20 μs
Elixir.Enum.flat_map              3.67 M        0.27 μs  ±1058.86%        0.20 μs
Elixir.Enum.flat_map_wrong        3.64 M        0.27 μs  ±1075.87%        0.20 μs

Comparison: 
ExCore.Monad.flat_map             3.71 M
Elixir.Enum.flat_map              3.67 M - 1.01x slower
Elixir.Enum.flat_map_wrong        3.64 M - 1.02x slower

##### With input Map #####
Name                                 ips        average  deviation         median
ExCore.Monad.flat_map             4.15 M        0.24 μs ±11150.89%         0.0 μs
Elixir.Enum.flat_map_wrong        1.33 M        0.75 μs   ±310.86%        0.70 μs
Elixir.Enum.flat_map              0.67 M        1.49 μs  ±1624.04%        1.00 μs

Comparison: 
ExCore.Monad.flat_map             4.15 M
Elixir.Enum.flat_map_wrong        1.33 M - 3.12x slower
Elixir.Enum.flat_map              0.67 M - 6.19x slower

##### With input ValueMap #####
Name                                 ips        average  deviation         median
ExCore.Monad.flat_map             7.35 M       0.136 μs   ±518.59%       0.120 μs
Elixir.Enum.flat_map              3.42 M        0.29 μs ±10604.27%         0.0 μs
Elixir.Enum.flat_map_wrong        1.84 M        0.54 μs  ±2503.76%        0.30 μs

Comparison: 
ExCore.Monad.flat_map             7.35 M
Elixir.Enum.flat_map              3.42 M - 2.15x slower
Elixir.Enum.flat_map_wrong        1.84 M - 3.99x slower

In addition, mine works with any type the user wants to write an implementation for, like for the Erlang :array module, you could do that (where you cannot with Enum). ^.^

But as you can see, mine is faster in every case, ‘barely’ so with lists (basically the same implementation that Enum already uses I don’t doubt) to surprisingly and significantly faster with maps (even the ‘fast’ version that skips much of Enum’s work is still much slower). In addition, mine returns a list when a list is input and a map when a map is input, as flat_map/2 is supposed to be doing. ^.^

/me is tempted to implement more category theory functions at this point other than just monad, could probably run circles around a lot of the existing Elixir code (though the elixir code could be made faster if anyone tried)

/me is still unsure why on earth Enum.flat_map/2 does not return the same type that it took in, like whaaa…

EDIT: Oh, and the benchmarking code:



defmodule Helpers do
  def do_flat_map({k, v}), do: %{k => v, v => k}
  def do_flat_map(v), do: [v, v]

  def do_flat_map_wrong({k, v}), do: [{k, v}, {v, k}]
  def do_flat_map_wrong(v), do: [v, v]
end

inputs = %{
  "List"     => [:a, :b, :c, :d],
  "Map"      => %{a: 1, b: 2, c: 3, d: 4},
  "ValueMap" => ExCore.Monad.wrap(42, %{}),
}


actions = %{
  "Elixir.Enum.flat_map" => fn input -> Enum.flat_map(input, &Helpers.do_flat_map/1) end,
  "Elixir.Enum.flat_map_wrong" => fn input -> Enum.flat_map(input, &Helpers.do_flat_map_wrong/1) end,
  "ExCore.Monad.flat_map" => fn input -> ExCore.Monad.flat_map(input, &Helpers.do_flat_map/1) end,
}


Benchee.run actions, inputs: inputs, time: 5, warmup: 5, print: %{fast_warning: false}
5 Likes