16 Jul 2013, 02:25
Dave_gnome_head_isolated_pragsmall

Dave Thomas (337 posts)

  • Implement the following Enum functions using no library functions or list comprehensions: all?, each, filter, split, and take
A Possible Solution
defmodule MyList do

  def all?(list),     do: all?(list, fn x -> !!x end) # !! converts truthy to `true`
  def all?([], _fun), do: true
  def all?([ head | tail ], fun) do
    if fun.(head) do
      all?(tail, fun)
    else
      false
    end
  end

  def each([], _fun), do: []
  def each([ head | tail ], fun) do
    [ fun.(head) | each(tail, fun) ]
  end

  def filter([], _fun), do: []
  def filter([ head | tail ], fun) do
    if fun.(head) do
      [ head, filter(tail, fun) ]
    else
      [ filter(tail, fun) ]
    end
  end

  def split(list, count),      do: _split(list, [], count)
  defp _split([], front, _),   do: [ Enum.reverse(front), [] ]
  defp _split(tail, front, 0), do: [ Enum.reverse(front), tail ]
  defp _split([ head | tail ], front, count)  do
    _split(tail, [head|front], count-1)
  end

  def take(list, n), do: hd(split(list, n))

end


IO.inspect MyList.all?([])                 #=> true
IO.inspect MyList.all?([true, true])       #=> true
IO.inspect MyList.all?([true, false])      #=> false
IO.inspect MyList.all?([4, 5, 6], &1 > 3)  #=> true

MyList.each([1,2,3], IO.puts(&1))          #=> 1/2/3

IO.inspect MyList.split([1,2,3,4,5,6], 3)  #=> [[1, 2, 3], [4, 5, 6]]

IO.inspect MyList.take('pragmatic', 6)     #=> 'pragma'
24 Jul 2013, 19:01
Generic-user-small

Eugene Dorfman (4 posts)

Hi Dave

Maybe this is done intentionally to check who is doing exercises and checks with the answers :), but still looks like there are couple issues in this solution

Enum.each executes the function for each element in the list and returns :ok. MyList.each instead collects all function results in a list (sort of like Enum.map does) and returns it, thus we get:

iex(102)> Enum.each([1,2,3,4],IO.puts(&1))   
1
2
3
4
:ok
iex(103)> MyList1.each([1,2,3,4],IO.puts(&1))
1
2
3
4
[:ok, :ok, :ok, :ok]

So no need to add the results into the list, this implementation seems to work right:

def each([],fun), do: :ok
def each([h|t],fun) do 
	fun.(h)
	each(t,fun)
end

In filter implementation you are creating nested lists, because there is a coma used where a join operator is needed, and also in the else: case you do not need to nest the call to filter(tail, fun) into []. Here is the test output:

iex(104)> Enum.filter([1,2,3,4],fn x -> rem(x,2)==0 end)
[2, 4]
iex(105)> MyList1.filter([1,2,3,4],fn x -> rem(x,2)==0 end)
[[2, [[4, []]]]]

My implementation looks like this (I was trying to omit using the if else, thus the code is a bit ugly, I guess if else is better to use instead of pattern matching in this case, and also it would allow to not use accumulator):

def filter(list,fun), do: do_filter(list,fun,[])

defp do_filter([],fun,acc), do: Enum.reverse acc

defp do_filter([h|t],fun,acc) do
	acc = add_if?(fun.(h),h,acc)
	do_filter(t,fun,acc)
end

defp add_if?(true,h,acc), do: [h|acc]
defp add_if?(_,_,acc), do: acc

Enum.split produces a tuple as a result, while MyList.split creates a list. Also Enum.split works with negative numbers as well, by cutting it from the right. Here is the solution that handles the negatives:

#Enum.split
def split(list,n), do:  do_split([],list,n)
defp do_split(head,tail=[],n), do: pack(head,tail)
defp do_split(head,tail,0), do: pack(head,tail)
defp do_split(head,tail,n) when n<0 do
	n = n+length(tail)
	if n<0 do 
		n = 0
	end
	do_split(head,tail,n)
end
defp do_split(head,[h|t],n) do 
	head = [h | head]
	do_split(head,t,n-1)
end

defp pack(head,tail), do: {Enum.reverse(head), tail}
28 Jul 2013, 23:38
Generic-user-small

Dave Kennedy (1 post)

Yeah not so sure about the filter implementation provided as mentioned by Eugene it yields nested lists. Mine looks like:

def filter([], _func), do: []
def filter([head | tail], func) do
  if func.(head) do
    [head] ++ filter(tail, func)
  else
    [] ++ filter(tail, func)
  end
end
29 Jul 2013, 18:54
Generic-user-small

Eugene Dorfman (4 posts)

Dave K., while your implementation looks like it will work, it seems to be suboptimal, since your filter function will not be a subject to the tail call optimization, because it is not the last thing executed in the filter function body (instead the concatenation operator Kernel.++ is).

In Elixir, Erlang and I think other functional languages it is super-important to pay attention that your recursive call is the last thing you do in the function body, otherwise - you are risking to get a stack overflow. That’s why the accumulators are needed. I don’t remember if the book mentions this, however there is an excellent screencast with Jose Valim here: https://peepcode.com/products/elixir - where he mentions this tail call optimization and other things.

Also suboptimality comes from using list concatenation on every step. when you do join h | t , you always reuse the tail. Then you do Enum.reverse only once. And this is much cheaper, than creating a new list on every step and copy all items from both concatenated lists into it (this is how Kernel.++/2 seems to work, although I might be wrong, need to check that).

30 Aug 2013, 03:44
Generic-user-small

Arvind Dhiman (2 posts)

My implementation for split


    def split(list, count), do: _split(list,[], count)

    defp _split(_list, acc, 0), do: [Enum.reverse(acc), _list]

    defp _split([], acc, count) when count < 0  do
            [acc, []]
    end
    defp _split([], acc, count), do: [Enum.reverse(acc), []]


    defp _split([head|tail], acc, count) when count > 0 do
            _split(tail, [head|acc], count - 1)
    end

    defp _split(list, acc, count) when count < 0 do
            [head|tail] = Enum.reverse(list)
            result = _split(Enum.reverse(tail), [head|acc], count + 1)
            Enum.reverse(result)
    end

I used following test cases: http://elixir-lang.org/docs/stable/Enum.html#split/2

06 Sep 2013, 19:16
Generic-user-small

Fred Hsu (2 posts)

My version of all? without using if/else:

def all?(list), do: all?(list, fn x -> !!x end)
def all?([], _), do: true
def all?([head|tail], f), do: f.(head) and all?(tail, f)
11 Mar 2014, 22:07
Generic-user-small

Nathan Feaver (3 posts)

I found some unit tests were really helpful for building these methods. My test for #each doesn’t test that the function actually gets called. Just run this file as a script:

$ elixir my-list_test.exs

# my-list_test.exs
Code.load_file("my-list.exs")
require Integer

ExUnit.start

defmodule MyListTest do
  use ExUnit.Case

  test "all? is true" do
    expected = MyList.all?([1,2,3], &(&1))
    assert expected
  end

  test "all? is false" do
    expected = MyList.all?([1,2,3], &(&1 == 1))
    assert expected == false
  end

  test "each function is invoked" do
    expected = MyList.each([1,2,3], &(&1 == 1))
    assert expected == :ok
  end

  test "filter returns matching elements" do
    expected = MyList.filter([1,2,3], &(Integer.odd?(&1)))
    assert expected == [1, 3]
  end

  test "split cuts the collection in two" do
    expected = MyList.split([1,2,3,4],1)
    assert expected == {[1], [2, 3, 4]}
  end

  test "take the first few items" do
    expected = MyList.take([1,2,3,4],1)
    assert expected == [1]
  end
end
22 Jul 2014, 21:22
Generic-user-small

Patrick Oscity (5 posts)

My approach for split and take:

defmodule MyList
  def split([head | tail], count) when count > 0 do
    {left, right} = split(tail, count-1)
    {[head | left], right}
  end
  def split(list, _count), do: {[], list}

  def take([head | tail], count) when count > 0 do
    [head | take(tail, count-1)]
  end
  def take(list, _count), do: []
end

If you want take to work with negative indices like Enum.take:

defmodule MyList
  def take(list, count) when count < 0 do
    Enum.reverse take(Enum.reverse(list), -count)
  end
  def take([head | tail], count) do
    [head | take(tail, count-1)]
  end
  def take(list, _count), do: []
end
  You must be logged in to comment