How To Do A For Loop In Elixir (using only recursion)

Chat / Discussions
,
22

I found your question challenging @Onor.io, so I tinkered with your approach for a bit, until I ended up with this

the main difference with your approach come from the question “why limit ourselves with integers when we can pass any data type, specially functions”.
Any feedback is more than welcome.

PS: I haven’t looked at the implementation of Enum.reduce/3 but It feels like it’s something of the sorts of what I have just implemented.

1 Like
23

here’s my simplified version from my previous post.

defmodule Loop.Basic do
  @spec loop(term, (term -> term), (term -> term), (term -> term)) :: list
  def loop(term, condition, transform \\ &(&1 + 1), fun \\ &(&1))
      when is_function(condition, 1) and is_function(transform, 1) and is_function(fun, 1) do
    do_loop(term, condition, transform, fun, [])
  end

  defp do_loop(current, condition, transform, fun, acc) do
    if condition.(current) do
      do_loop(transform.(current), condition, transform, fun, [fun.(current) | acc])
    else
      Enum.reverse(acc)
    end
  end  
end

Examples:

      iex> Loop.Basic.loop(1, &(&1 <= 5))
      [1, 2, 3, 4, 5]

      iex> Loop.Basic.loop(12345, &(String.length("#{&1}") <= 10), &(&1 * 7), &(:"#{&1}"))
      [:"12345", :"86415", :"604905", :"4234335", :"29640345", :"207482415", :"1452376905"]

it’s pretty functional in the mathematical sense of the word.

I called it basic, because functions only accept one argument (term)

Once I finished that, I was like…well, it gotta be concurrent as well,
so I ended up with a library.
https://github.com/eksperimental/loop/

please have a look at the sources:

and tell me what you think of it,
and if it can be improved in some way.

1 Like
24

How to do a for loop in Elixir (using only recursion)

I had this same question, but it seems that I have to think differently about this, and instead of trying to make a for loop, I just need to embrace recursion as the proper way to drill through things. Someone asked for a link: I thought this was a good one.

http://elixir-lang.org/getting-started/recursion.html#loops-through-recursion

25

I’m Johnny Come lately on this subject but from what I’ve been told by the pro’s you’re not a programmer or at least you cannot get hired as one until you actually understand what’s going on under the hood. Sure Enum.each, Enum.map, etc are already implemented for us but most books I’ve read teach you how recursion works. I would assume that once Elixir becomes more mainstream programmers will be asked to implement recursive functions in interviews.

26

I wonder, is using the Y-combinator cheating? I would actually suggest that it might be the ‘nicest’ solution, because it sort of does ‘meta’-recursion; calling a function with itself as argument, so the function can recurse if and when it wants to, without using explicit recursion. (For instance, this will even work when using anonymous functions).

27

I would love to see a solution like this.

1 Like
28

I think it would be something like this:

defmodule For do
    # Create a closure which contains a function that applies itself to itself.
    # Call this function with as argument a function that calls the passed function with the passed `arg`.
    # In lambda calculus: `Y = λf.(λx.f(x x))(λx.f(x x))`
    # An easier definition: `Y f = f (Y f)`
    # If there exist at least one 'fixed point' where the function `f` does not call the passed function, this structure terminates.
    # 
    # This `y_combinator/0` can be called with a double anonymous function: 
    #   The outermost receives the fixpoint function as input, which can be called when you want to recurse.
    #   The innermost receives whatever argument needs to be passed during iterations.
  def y_combinator do
   fn f -> 
      (fn x -> 
        x.(x) 
      end).(
        fn y -> 
          f.(
            fn arg -> 
              y.(y).(arg) 
            end
          ) 
        end
      ) 
    end
  end

  def loop(initialization, condition, body) do
    y_combinator.(fn recurse ->
      fn state ->
        if !condition.(state) do 
          state
        else
          state
          |> body.()
          |> recurse.()
        end
      end
    end).(initialization)
  end
end

Which could then be called as follows:

For.loop(0, &(&1 <= 10), fn i -> 
  IO.puts(i)
  i + 1
end)

I wonder if this could be made even more ‘idiomatic imperative programming-like’ when doing something with (unhygienic) macros.

6 Likes
29

This might be on of my favorite posts of all time.

2 Likes
30

I once used a recursive anonymous function for an elixir golf challenge :slight_smile:

1 Like