What are Monads?

Is it actually true, that Monads are basically simply flatMaps and thats it?

2 Likes

In essence a monad is anything that just has two functions (though some languages break them up into more, but this is the basics) and follows a few laws:

  1. First you need to have the type, it can be anything that can contain anything else, 0 or more times, so an optional (0 or 1 times), a list (0 or more times), a tuple (N times), a map (0 or more times), or anything you can think of or create that can hold ‘something’ (like a future in java/c++/rust/javascript/etc… is a monad type for example).
  2. First function is the unit function, it just takes a value and wraps it in the type you specify, it is often named unit/return/wrap/etc… The Elixir Enum.wrap/2 is such a unit function if you pass it only a single value (it technically does more than just what unit should do, a real unit in elixir is something like the list constructor like [42] or {42} or %{a: 42} or so forth).
  3. Second function is the bind function, often called flat_map (as it is in Elixir), it is just a function that takes an instance of a type (like an elixir list) and a function, and it calls that function on each element inside the monad and returns that same monadic type back (this is where Elixir’s flat_map breaks down, making it not monadic either, it just accepts returning a list), that list of monadic type instances returned are then flattened back down one level, so something like (in Elixir parlance) flat_map([1, 2, 3, 4], fn x when even?(x) -> [x, x]; _ -> [] end) returns [2, 2, 4, 4] and flat_map(%{a: 1, b: 2}, fn {key, value} -> %{key => value; value => key} end) would return %{a: 1, b: 2, 1 => :a, 2 => :b} and so forth.
  4. The first law being that (I’ll use elixir’s terminology for these of wrap/flat_map) wrap when passed to flat_map is the same as the original instance, I.E. something === flat_map(something, &wrap(&1, theType) and flat_map(wrap(v), f) === f.(v) (it is this why Elixir’s flat_map is not monadic, it breaks this law).
  5. The second law being that the succession order of flat_mapping does not matter, I.E. something |> flat_map(f) |> flat_map(g) === flat_map(something, fn x -> flat_map(f.(x), g) end)

So yes, that looks long but only because there are so many examples, more succinctly:

defmodule ListMonad do
  def wrap(v), do: [v]
  def flat_map([], _f), do: []
  def flat_map([head, rest], f), do: f.(head) ++ flat_map(rest, f)
end

defmodule OkMonad do
  def wrap(v), do: {:ok, v}
  def flat_map(:error, _f), do: :error
  def flat_map({:ok, v}, f), do: f.(v) 
end

Which you could use like:

[1, 2, 3]
|> ListMonad.flat_map(&[&1*2]) # Result: [2, 4, 6]
|> ListMonad.flat_map(&if(&1>=4, do: [], else: [&1])) # Returns: [2, 4]

21
|> OkMonad.wrap() # Returns {:ok, 21}
|> OkMonad.flat_map(&{:ok, &1&2}) # Returns: {:ok, 42}
|> OkMonad.flat_map(&if(&1>30, do: :error, else: {:ok, &1})) # Returns: :error
|> OkMonad.flat_map(&{:ok, &1&2}) # Still returns just: :error

Any kind of container can become a monad if you can define anything that follows the above requirements. In a properly typed system you can make generic functions that work over it all, but in Elixir you need some way to define types, the easiest way is to just name them somehow, like via a module name ListMonad/OkMonad or via atoms passed in plain instances there-of (which is what Enum.wrap/2 does) or whatever.

But overall yeah, Monads are dead-stupid-simple, they just have a few rules that make them complex, but they are so very simple.

21 Likes

OK, thanks a lot for this detailed description. ^.^

This video explains it like mentioned, I think its very easy to understand:

Do you think its accurate?

Since he says at one point, that its always flatMap, just under different names.

P.S: I just saw, that this here is public, while I thought its our private chat :slight_smile:

Not a clue, at work, I can rarely watch video’s in general thus I tend to need text. ^.^;

Lol, all good.

I was curious about implementing the monad pattern in elixir so I went ahead and did so in a new playground

  • Monad definition:
  • Monad implementations for list/map/okerrortuples:
  • And the tests (it already has it’s own built-in tests via deftest but here are explicit ones too to show usage):
1 Like

@OvermindDL1 can split the posts into a new thread then make the thread a PM between you both :023: (prob best to do that for any posts that are not related to the OP, ODL?)

1 Like

Monads are functional so it is related to ReasonML, but not with phoenix yeah, I’ll break it out. Done. ^.^

2 Likes

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

Shouldn’t Enum always return the type enumerable instead of a list? I know you can convert the list back to the enumerable but it seems more logical to generate it from the beginning. So for example the types of filter and flat_map of course should be:

filter(t, (element -> as_boolean(term))) :: t
flat_map(t, (element -> t)) :: t

Considering it is in an Enum module, very probably it should, but the enumerable type in Elixir is a list, so… We need better enumeration modules, perhaps of a category type system style. ^.^

Honestly, who actually does something like Enum.map over something that they do not know the type of, you generally already know if it is a map or a list or a struct or something, so why not just call the right module and get rid of the indirection and get rid of the enum module?

2 Likes

I agree with you, and honestly don’t miss an equivalent enumerable type and Enum module in Erlang. The specific type modules have the traversing functions needed.

1 Like

Likewise, I often use the base erlang modules like :lists and :maps surprisingly often in Elixir, just because Elixir’s List and Map is missing some pretty basic functions that those have. ^.^;

2 Likes

I made an Access clone, and a lens helper for it! ^.^

Lens usage:

    import ExCore.Access, only: [lens: 1]

    o0a = %{a: 42}
    assert l0a = lens a
    assert l0b = lens [:a]
    assert 42 = l0a.get(o0a)
    assert 42 = l0b.get(o0a)

    o1a = %{a: %{b: 42}}
    assert l1a = (lens a.b)
    assert l1b = (lens [:a][:b])
    assert l1c = (lens a[:b])
    assert l1d = (lens [:a].b)
    assert l2a = (lens {:c})
    assert l2b = (lens {:c, 32})
    assert l2c = (lens {:c, %{b: 16}}.b)
    assert l2d = (lens a{:c, %{d: 12}}.d)
    assert 42 = l1a.get(o1a)
    assert 42 = l1b.get(o1a)
    assert 42 = l1c.get(o1a)
    assert 42 = l1d.get(o1a)
    assert nil == l2a.get(o1a)
    assert 32 = l2b.get(o1a)
    assert 16 = l2c.get(o1a)
    assert 12 = l2d.get(o1a)

    o2a = %{a: 21}
    o2b = %{a: %{b: 21}}
    assert l2a = (lens a)
    assert l2b = (lens a.b)
    assert l2c = (lens a{:c, %{d: 21}}.d)
    assert %{a: 42} = l2a.get_and_update(o2a, &(&1*2))
    assert %{a: %{b: 42}} = l2b.get_and_update(o2b, &(&1*2))
    assert %{a: %{b: 21, c: %{d: 42}}} = l2c.get_and_update(o2b, &(&1*2))

Yep, you can even specify defaults inside the lens. ^.^

But essentially:

  • A raw thing, like a is equal to [:a]
  • A [term] uses term as the key
  • A {term} uses term as the key
  • A {term, default} uses term as the key, if the result does not exist then it uses default as the return/accessor
  • Just concat as normal or separate with .'s as necessary because Elixir’s syntax is a bit restrictive. ^.^;

And yes, if you really don’t want to use tuple calls (or some annoyances try to remove it) you can pass the lens in at the place of the key in the Access calls, like ExCore.Access.get(%{a: %{b: 42}}, lens(a.b)) (doesn’t need to be inline, you can store and pass it around).

/me is still irritated that people are trying to remove tuple-calls… give us some other form of first-class modules if not those then!

2 Likes

Hmm, I should break this new ‘Core’ playground into a new thread, I may do that tomorrow. ^.^;

New update, I got curious on if I could make a better for in Elixir so I whipped something up. It is pretty trivial to add new features to it in a backwards safe way (unlike Elixir’s for where trying to add a uniq: true to it is limiting, such a thing is trivial with mine for comparison). However, the benchmark:

defmodule Helpers do
  use ExCore.Comprehension

  # map * 2

  def elixir_0(l) do
    for\
      x <- l,
      do: x * 2
  end

  def ex_core_0(l) do
    comp do
      x <- list l
      x * 2
    end
  end

  # Into map value to value*2 after adding 1

  def elixir_1(l) do
    for\
      x <- l,
      y = x + 1,
      into: %{},
      do: {x, y * 2}
  end

  def ex_core_1(l) do
    comp do
      x <- list l
      y = x + 1
      {x, y * 2} -> %{}
    end
  end
end

inputs = %{
  "List - 10000 - map*2" => {:lists.seq(0, 10000), &Helpers.elixir_0/1, &Helpers.ex_core_0/1},
  "List - 10000 - into map +1 *2" => {:lists.seq(0, 10000), &Helpers.elixir_1/1, &Helpers.ex_core_1/1},
}


actions = %{
  "Elixir.for"  => fn {input, elx, _core} -> elx.(input) end,
  "ExCore.comp" => fn {input, _elx, core} -> core.(input) end,
}


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

And the results here:

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.1
Benchmark suite executing with the following configuration:
warmup: 5.00 s
time: 5.00 s
parallel: 1
inputs: List - 10000 - into map +1 *2, List - 10000 - map*2
Estimated total run time: 40.00 s



Benchmarking with input List - 10000 - into map +1 *2:
Benchmarking Elixir.for...
Benchmarking ExCore.comp...

Benchmarking with input List - 10000 - map*2:
Benchmarking Elixir.for...
Benchmarking ExCore.comp...

##### With input List - 10000 - into map +1 *2 #####
Name                  ips        average  deviation         median
ExCore.comp        344.12        2.91 ms     ±4.00%        2.88 ms
Elixir.for         248.72        4.02 ms    ±18.80%        3.75 ms

Comparison: 
ExCore.comp        344.12
Elixir.for         248.72 - 1.38x slower

##### With input List - 10000 - map*2 #####
Name                  ips        average  deviation         median
ExCore.comp        2.64 K      378.83 μs    ±14.71%      402.00 μs
Elixir.for         2.03 K      493.56 μs    ±11.89%      508.00 μs

Comparison: 
ExCore.comp        2.64 K
Elixir.for         1.03 K - 1.30x slower

Based on knowing what the inputs are (and this is expandable too, whoo!) it can generate better optimized code (which should get even better on larger sets, and there is an obvious optimization here that I’ve not done yet either that could boost it a tiny bit more too). ^.^

Plus it has the boon of not having comma-droppings all over the place! ^.^

I’m actually not even sure why the pure list mapping version is faster though to be honest, I generate about identical code to elixir’s except I keep the most actively changing bindings last in the stack instead of first (why the frick is elixir’s style to put the most changing bindings first, bleh… that is inefficient on the beam…). Meh…

1 Like

Hey all!

I’m a bit late to this discussion, but I’d urge you to checkout a library I wrote a little while back, called fun_land, which implements many algebraic data types, including Monads and the components it is built up from.
It also contains rigorous documentation. That said, Monads are such a vague, abstract subject that it is very hard to describe them in a concrete way without for instance simplifying things that are not true for all Monads. I will not claim that my explanation of Monads does not fall under the ‘Monad Taco tutorial fallacy:slight_smile: .

PRs welcome, as well as feedback on the documentation and the code. :angel:

4 Likes

5 posts were merged into an existing topic: On iteration and enumeration

For a lot more of black magic, check Witchcraft and the rest of their eco-system
https://github.com/expede/witchcraft

1 Like

Check this podcast
I think before getting straight to monads, there are some other concepts to better know first like monoid, functor …

2 Likes

Another legendary talk, this time from Mister JavaScript in a Pyjama :smiley:

2 Likes

So, in short the Monad is a concept of value wrapper.

The value wrapper (monad) has a function which accepts the function as an argument and applies it on wrapped value (or each element of wrapped value if it is a list, depends on particular monad implementation and usage).

If it doesn’t have a “valid” value it should not crash but return some sort of valid result like nil / :error or empty list.

0, 1, or more 'value’s yes, depending on what the ‘container’ is. Like :ok and :error returns could be a ‘monad’, they can still operate on the no-data success or error states.

Yep yep.

Eh, no such thing as an ‘invalid value’ for such a thing, the types define what it is. For example the empty list is the ‘no-value’ version of a list, or :error of an {:ok, value}|:error return as is common in elixir/erlang. These are not invalid values, they are just other ‘states’ of the ‘monad’.

1 Like