Is there a functional way to implement this idea?

Questions / Help
1

Given a list [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1]
I want to return a list containing [3, 4, 3, 2]

ie count the number of consecutive elements that are the same.

I can’t seem to figure out a good way to do this in a purely functional way using Elixir Enum methods.

Is it possible?

2 Likes
2

you could start with chunk_by(enumerable, fun)

Would also be a good exercise to do it without the stdlib.

1 Like
3

Certainly with Enum.reduce/3

1 Like
4

Yes, generally, if you have a problem, you do not know how to solve in a functional manner. Ask reduce if it can help (It can. Always.). Big step forward if you can implement reduce yourself.

2 Likes
5

To be honest when somebody who is starting with the language wants to solve something, and can be solved with Enum.reduce, my answer will be this. :joy:

6

This make the job :
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1] |> Enum.chunk_by(&(&1)) |> Enum.map(&Enum.count(&1))

8 Likes
7

Using good’ol reduce.

[0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1]
|> Enum.reduce({[], 0}, fn
  previous, {[count | rest_acc], previous} ->
    {[count + 1 | rest_acc], previous}

  elem, {acc, _previous} ->
    {[1 | acc], elem}
end)
|> elem(0)
|> Enum.reverse()
4 Likes
8

Normally you should use the stdlib if there is some help there (most of the time there is, in this case chunk_by/2 can do all the hard work). But you can also do it by hand…

defmodule Chunker do
  def chunk([]), do: []
  def chunk([head|tail]), do: _chunk(tail, [], 1, head)

  # this is the stop condition, all elements of the input are consumed
  defp _chunk([], acc, count, _), do: acc ++ [count]
  # this function only matches when the head of the list is the same as the last
  # you just have to give them the same name ("last") - nice, isn't it?
  defp _chunk([last|tail], acc, count, last), do: _chunk(tail, acc, count+1, last)
  # a new chunk begins!
  defp _chunk([head|tail], acc, count, _last), do: _chunk(tail, acc ++ [count], 1, head)
end

Note: this is slow for large lists because of

acc ++ [count]

In each of those, the whole acc-list is walked until the end is found.
Can be optimized by

[count] ++ acc

and a new stop condition:

defp _chunk([], acc, count, _), do: Enum.reverse([count] ++ acc)
4 Likes
9

Can’t believe i over looked that!

10

I really need to learn to use reduce more, thanks for this, I’m gonna study it for a bit!

1 Like
11

You should. Let us know if you’ve got any questions regarding the reduce.

12 
 elem, {acc, _previous} ->
    {[1 | acc], elem}

One question is, what even is this syntax?
It looks like a function but there is no fn before it… how does that work?

1 Like
13

it is an anonymous function, just look on the line above.

you can have multiple clauses in anonymous functions.
for instance:

fn 
  x, acc when x in 1..10 ->
     do_something()

   x, acc ->
     do_something_else()
end

the only limitation is that all of them have to have the same number of arguments (x, acc)

3 Likes
14

wow had no idea that was even possible, i’ve never seen that before!

1 Like
15

This is such a cool solution!

Took me a while to get it but it makes sense now.

Gonna try use reduce as much as possible in the future!

1 Like
16

Reduce is your friend, but it’s good practice to understand the solution @Sebb presented.

This explanation of how recursion, map, filter & reduce (also known as fold in Erlang-speak) hang together is written for Erlang but the concepts are directly applicable to Elixir: Higher Order Functions | Learn You Some Erlang for Great Good!

2 Likes
17

You can [count | acc] and you reverse the list when you return the result.

2 Likes
18

There you go:

defmodule MyOwn do
  @spec reduce(list, acc, (element :: any, acc -> acc)) :: acc when acc: any
  def reduce(list, acc, fun) when is_list(list) and is_function(fun, 2) do
    reduce_list(list, acc, fun)
  end

  defp reduce_list([head | tail], acc, fun),
    do: reduce(tail, fun.(head, acc), fun)

  defp reduce_list([], acc, _fun),
    do: acc

  @spec reverse([]) :: []
  @spec reverse(nonempty_list(element)) :: nonempty_list(element) when element: any
  def reverse(list) when is_list(list) do
    reverse_list(list, [])
  end

  defp reverse_list([head | tail], acc),
    do: reverse_list(tail, [head | acc])

  defp reverse_list([], acc),
    do: acc
end

{acc, _} =
  MyOwn.reduce([0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1], {[], 0}, fn
    previous, {[count | rest_acc], previous} ->
      {[count + 1 | rest_acc], previous}

    elem, {acc, _previous} ->
      {[1 | acc], elem}
  end)

MyOwn.reverse(acc)
3 Likes
19

Indeed, it is a really simple and performant solution.

You do one pass (iteration) to count the values, and one pass to reverse them.

There are no additional copies of the list, if you give 1 million elements in the list, there will never be more than 1million elements in total between the current list and the accumulator, and as the list is process this number will decrease.

Sebb’s solution is pretty much the same but with function definitions.

The source code for the Enum module is full of examples like this one.
elixir/lib/elixir/lib/enum.ex at main · elixir-lang/elixir · GitHub

20

A for comprehension for comparison

iex(30)> list = [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1]
iex(31)> for chunk <- Enum.chunk_by(list, & &1), do: length(chunk)
[3, 4, 3, 2]
5 Likes