It’s basically compensating for the fact that Erlang’s primary data structure, the linked list, sucks for this job. Unless you cheat!
We want to build up some output, which can be character lists or binaries. So we need to put all of that in something. We want to add to it dynamically, so a tuple is out. Appending to binaries is too much memory copying. It’s gotta be a list, but:
iex(1)> letters = ~w[a b c d e f]
["a", "b", "c", "d", "e", "f"]
iex(2)> Enum.reduce(letters, [""], fn letter, output -> output ++ [letter] end)
["", "a", "b", "c", "d", "e", "f"]
++ is O(n) every time it’s called, making my stupid example above something like O(n!). Ouch. Of course, lists can be O(1):
iex(3)> Enum.reduce(letters, [""], fn letter, output -> [letter | output] end)
["f", "e", "d", "c", "b", "a", ""]
Only that reverses our output. Adding a call to a reverse() would slow I/O operations.
Good thing the Erlang team is clever! If you don’t care about nesting or proper lists, you can append as an O(1) action!!! Behold:
iex(4)> Enum.reduce(letters, [""], fn letter, output -> [output | letter] end)
[[[[[[[""] | "a"] | "b"] | "c"] | "d"] | "e"] | "f"]
It’s still just a linear (recursive) scan to write it out too!
It’s essentially an abuse of linked lists to switch them from a stack into a queue. Awesome, eh?
