16 Jul 2013, 02:25 Dave Thomas (338 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 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 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 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 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 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 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 ``` 04 Aug 2014, 07:57 Patrick Oscity (6 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 `````` 15 Aug 2014, 01:53 Michael Bishop (2 posts) Here are my split and take which handle the negative indices in a way I haven’t yet seen. ``````defmodule MyList do def split(list, 0), do: {[], list} def split([], _count), do: {[], []} def split([head | tail], count) when count > 0 do {first, rest} = split(tail, count - 1) {[head|first], rest} end def split(list, count) do {first, rest, _rest_size} = _rsplit(list, -count) {first, rest} end defp _rsplit([], _count), do: {[],[], 0} defp _rsplit([head | tail], count) do {first, rest, rest_size} = _rsplit(tail, count) if (rest_size < count) do {first, [head|rest], rest_size + 1} else {[head|first], rest, rest_size} end end def take(_list, 0), do: [] def take([], _count), do: [] def take([head|tail], count) when count > 0 do [head|take(tail, count-1)] end def take(list, count) do {first, _rest_size} = _rtake(list, -count) first end defp _rtake([], _count), do: {[], 0} defp _rtake([head|tail], count) do {rest, rest_size} = _rtake(tail, count) if (rest_size < count) do {[head|rest], rest_size + 1} else {rest, rest_size} end end end `````` You must be logged in to comment