Skip to content

Instantly share code, notes, and snippets.

@StevenJL
Last active October 19, 2016 00:33
Show Gist options
  • Save StevenJL/e33fda8f74af024b93da to your computer and use it in GitHub Desktop.
Save StevenJL/e33fda8f74af024b93da to your computer and use it in GitHub Desktop.
Writing foldr and foldl in elixir
# Looks like List.foldr and List.foldl are delegated to erlang:
# https://github.com/elixir-lang/elixir/blob/v1.0.3/lib/elixir/lib/list.ex#L116L118
# But if we wanted to implement these in elixir, seems like we can only write fold1, but not foldr
# Question: Can we define `foldr` without using high-level functions (ie. List.reverse)
# and using a recursive approach similar to `foldl`? I really can't think how but would be
# very interested if someone can show me a solution (if it exists).
defmodule MyList do
def foldl([], acc, _) do
acc
end
def foldl([head|tail], acc, func) do
foldl(tail, func.(head, acc), func)
end
def foldr() do
end
end
ExUnit.start
defmodule MyListTest do
alias MyList, as: L
use ExUnit.Case
test "it folds a list from right to left" do
list = ["e", "l", "i", "x", "i", "r"]
assert L.foldl(list, "", &(&1 <> &2)) == "rixile"
end
test "it folds a list from left to right" do
list = ["e", "l", "i", "x", "i", "r"]
assert L.foldr(list, "", &(&1 <> &2)) == "elixir"
end
end
@dotmilk
Copy link

dotmilk commented Oct 18, 2016

defmodule MyList do
  def foldr([h | []],acc,f), do: f.(h,acc)
  def foldr([h | t],acc,f) do
    f.(h,foldr(t,acc,f))
  end

  def dbg(x,acc) do
    IO.puts x
    x * acc
  end
end

And then to demonstrate we are actually folding from the right 'MyList.foldr([1,2,3,4],1,&MyList.dbg/2)' yields:

4
3
2
1
24

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment