keep_zen

Why did not optimize `Enum.map`s chain

For a functor, map(map(functor, fun), fun2) equal as map(functor, fun2*fun).
In Elixir, I think Enum module is a functor, but |> did not optimize it.
Like this:

defmodule A do
   def add1(e) do
     IO.puts("+1")
    e+1
  end
 def sub1(e) do
   IO.puts("-1")
  e-1
 end
end
1..10
|> Enum.map(&A.add1/1)
|>Enum.map(&A.sub1/1)

The console outputs like:

+1
+1
+1
...
-1
-1
-1
...
-1

If the code have optimzed it should show as:

+1
-1
+1
-1
...

Redefine |>, I think I can do the optimation for Enum.maps. If there is functors’ list, optimize for all functors’ chains,can also be done. I meaning, It not hard to do. But Why it is not happend in Elixir?

11 comments

#pipe-operator

9 1179 11

2022-05-25 14:20:08 UTC

Marked As Solved

krstfk

There’s a lot of confusion here.
Functors (and the likes) are an abstraction that helps to reason about some compositions, they’re not magic.
So what is a functor (in programming):
It’s a data structure, with a (f)map function that has the following properties :

    fmap id = id
    fmap (f . g)  ==  fmap f . fmap g

That’s it those are the rules of a functor.
So, is a list, under Enum.map a functor? No. Because, elixir/erlang/ocaml/scala… allow for side effects.
Namely, if you were to write:

f = fn x -> 
   IO.puts(x)
   x + 1
g = fn x ->
   IO.puts(x)
  x * 2

Now let’s try this :

iex(60)> Enum.map([1,2,3], fn x -> f.(g.(x)) end )
1
2
2
4
3
6
[3, 5, 7]
iex(61)> Enum.map(Enum.map([1,2,3], g), f)
1
2
3
2
4
6
[3, 5, 7]

So plainly, list under map is not a functor, unless you ignore the side effects. But if you guarantee that f and g are side effects free, list under map is a functor.

Now, nowhere in the functor laws is it specified that one side of the equation should be favoured over the other side.

What you’re talking about is something called fusion, or operations fusion or shortcut fusion or stream fusion. These have little to do with functors (at most, functor laws may allow you to prove that these optimisations are safe), and they are not ‘not hard’. Take a look at the map implementation for list in Haskell, look at the rewriting rules. Also, note that those optimisations don’t apply for all instances of functor (check fmap for Maybe).

Operations fusions, come with some sort of trade off, and if you have long chains of operations, maybe use Stream.map instead of Enum.map, but I don’t know, benchmark (more on that later). (BTW ops fusion are not that common).

Regarding the pipe operator (|>) vs functional composition, the main difference is wether you read left to right or right to left (at least in strict languages). Ocaml doesn’t have an infix composition operator either. Again, this is orthogonal to compiler optimisations. But, you may implement it trivially:

defmodule Compose
   # DO NOT DO THAT
   defp compose(f,g), do: fn x -> f.(g.(x)) end
   def f <~> g, do: compose(f, g)
end
iex(2)> import Compose
Compose
iex(3)> test = fn x -> x + 1 end <~> fn x -> x * 2 end
#Function<0.15966921/1 in Compose.compose/2>
iex(4)> test.(1)
3

It’s not that different from the pipe operator (except you read it in the other direction, and it’s a bit more fiddly with anonymous functions):

iex(16)> test = fn x -> x  |> then(fn x -> x * 2 end) |> then(fn x -> x + 1 end)  end
#Function<44.65746770/1 in :erl_eval.expr/5>
iex(17)> test.(1)
3

TLDR; : don’t worry about functional abstractions, you probably don’t need them. Learn the standard library. Then learn OTP abstraction.

( Final note : optimisation
In general we have good frameworks for getting a sense of software complexity. However, for mere mortals, the only way to actually optimise for one’s use case is benchmarking. Put another way constant factors may be extremely important regardless of O)

Post #11

Also Liked

dorgan

Enum is not a functor, it always goes from enumerable to lists. It’s also a set of eager funcions, the funcional composition you assume is not used here nor is it common in Elixir.

If you want to consider it a functor, you need to apply its properties yourself, Elixir won’t do it for you. But know that functors as a concept dont exist in elixir the way they exist in Haskell or Ocaml.

I also have to note that the Pipe operator just pipes function calls like the unix Pipe does, it’s not a functional composition operator.

Post #2