16 Jul 2013, 02:25
Dave_gnome_head_isolated_pragsmall

Dave Thomas (342 posts)

  • Implement the following Enum functions using no library functions or list comprehensions: all?, each, filter, split, and take

A Possible Solution</summary>

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'

</details>

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 (3 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-6kites_pragsmall

Nathan Feaver (8 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_pragsmall

Patrick Oscity (13 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
Generic-user-small

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
05 Dec 2014, 21:15
9863_pragsmall

Suraj Kurapati (15 posts)

I’m posting my solution here, for the sake of discussion, because it’s different from what’s been posted so far.

My split() function projects the negative-count case onto the positive-count case in one fell swoop using max():

  def split(collection, count) when count < 0 do
    split(collection, max(0, length(collection) + count))
  end
  def split(collection, 0), do: { [], collection }
  def split([head|tail], count) do
    { left, right } = split(tail, count - 1)
    { [head|left], right }
  end
  def split([], _count), do: { [], [] }

My take() function simply re-uses my split() function from above:

  def take(collection, count) do
    { left, right } = split(collection, count)
    if count < 0 do
      right
    else
      left
    end
  end
13 Dec 2014, 17:52
Generic-user-small

Kent Worstein (1 post)

I don’t get why this approach to split fails to assign new values to the lists left and right. Am I using the for i <- list syntax correctly?

  def split(list, 0), do: {[], list}
  def split(list, count) when count > 0 do
    { left, right } = { [], [] }
    if count > length(list) - 1 do
      { list, [] }
    else
      for l <- (0 .. count - 1), do: left = left ++ [Enum.at(list, l)]
      for r <- (count .. length(list) - 1), do: right = right ++ [Enum.at(list, r)]
      { left, right }
    end
  end
  def split(list, count) when count < 0 do
    { left, right } = { [], [] }
    if abs(count) > length(list) - 1 do
      { [], list }
    else
      for l <- (0 .. length(list) - 1 + count), do: left = left ++ [Enum.at(list, l)]
      for r <- (length(list) + count .. length(list)), do: right = right ++ [Enum.at(list, r)]
      { left, right }
    end
  end
26 Dec 2014, 22:26
Generic-user-small

Pierre Sugar (56 posts)

defmodule MyEnum do

  # all?
  def all?([], _func), do: true
  def all?([head|tail], func) do
    func.(head) && all?(tail, func)
  end

  # each
  def each([], _func), do: :ok
  def each([head|tail], func) do
    func.(head)
    each(tail, func)
  end

  # filter
  def filter([], _func), do: []
  def filter([head|tail], func) do
    if func.(head) do
      [head|filter(tail, func)]
    else
      filter(tail, func)
    end
  end

  # split
  def split([], _count), do: {[],[]}
  def split(collection, count) 
    when count > length(collection), do: {collection, []}
  def split(collection, count) 
    when abs(count) > length(collection) or count == 0, do: {[], collection}
  def split(collection, count) do
    if count > 0 do
      first = _split(collection, count)
    else
      first = _split(collection, length(collection) + count)
    end
    {first, collection -- first}
  end
  defp _split(_, count) when count == 0, do: []
  defp _split([head|tail], count), do: [head|_split(tail, count-1)]

  # take
  def take(collection, count) 
    when abs(count) >= length(collection), do: collection
  def take(collection, count) when count < 0 do 
    collection -- _take(collection, length(collection)+count)
  end
  def take(collection, count), do: _take(collection, count)
  def _take(collection, count) when count == 0 or collection == [], do: []
  def _take([head|tail], count), do: [head|_take(tail, count-1)]
end
21 May 2015, 21:03
Dj-mangatar_pragsmall

Wirianto Djunaidi (5 posts)

My solution for split and take are in the same line as Suraj’s. I like his use of max(), which can reduce an extra pattern matching conditional method in mine.

defmodule MyList do

  defp type_check(x) when is_nil(x), do: false 
  defp type_check(x), do: x

  def all?(list, func \\ &type_check/1)

  def all?([], _), do: true

  def all?([head | tail], func) do
    func.(head) && MyList.all?(tail, func)
  end

  def each([], _), do: :ok

  def each([head|tail], func) do 
    func.(head)
    MyList.each(tail, func)
  end

  def filter([], _), do: []

  def filter([head | tail], func) do
    if func.(head) do
      [head | MyList.filter(tail, func)]
    else
      MyList.filter(tail, func)
    end
  end

  defp move_item(target, source, count) when count == 0 or length(source) == 0 do
    {target, source}
  end

  defp move_item(target, [head | tail], count) do
    move_item(target ++ [head], tail, count - 1)
  end

  def split([], _), do: {[], []}

  def split(list, count) when count < 0 and length(list) <= abs(count) do
    {[], list}
  end

  def split(list, count) when count < 0 do
    split(list, length(list) + count)
  end

  def split(list, count) do
    move_item([], list, count)
  end
  
  def take([], _) do
    []
  end

  def take(list, count) when count < 0 and length(list) < abs(count) do
    list
  end

  def take(list, count) when count < 0 do
    {_, rhs} = move_item([], list, length(list) + count)
    rhs
  end

  def take(list, count) do
    {lhs, _} = move_item([], list, count)
    lhs
  end

end

10 Apr 2015, 22:50
Me_pragsmall

Vignesh Rajagopalan (2 posts)

defmodule MyEnum do

  # all?
  def all?([], _), do: true
  def all?(list, fun), do: _all?(list, true, fun)
  defp _all?(_, false, _), do: false
  defp _all?([], true, _), do: true
  defp _all?([h|t], _, fun), do: _all?(t, fun.(h), fun)

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

  # filter
  def filter([], _), do: []
  def filter(list, fun), do: _filter(list, [], fun)
  defp _filter([], res, _), do: :lists.reverse res
  defp _filter([h|t], res, fun) do
    if fun.(h) do
      _filter(t, [h | res], fun)
    else
      _filter(t, res, fun)
    end
  end

  # split
  def split([], _), do: {[], []}
  def split(list, 0), do: {[], list}
  def split([h|t], n), do: _split({[h], t}, 1, n)
  defp _split({l1, l2}, cnt, n) when cnt == n or l2 == [], do: {:lists.reverse(l1), l2}
  defp _split({l1, [h|t]}, cnt, n), do: _split({[h|l1], t}, cnt+1, n)

  # take
  def take([], _), do: []
  def take(_, 0), do: []
  def take([h|t], n), do: _take([h], t, 1, n)
  defp _take(res, rem, cnt, n) when cnt == n or rem == [], do: :lists.reverse res
  defp _take(res, [h|t], cnt, n), do: _take([h | res], t, cnt+1, n)
end
27 Apr 2015, 02:22
Generic-user-small

Matt Schreck (2 posts)

all? Is this confusing or what? ~~~elixir def all?(list), do: all?(list, fn x -> !!x end) # !! converts truthy to true ~~~

AND he uses an if statement, even though he only mentions it might be necessary for filter! Anyway, here’s my solution, pretty readable and seems to work without truthy conversions

def all?([], _), do: true
def all?([head| [] ], func), do: func.(head) && true
def all?([head|tail], func), do: func.(head) && all?(tail, func)

each Eugene already mentioned what I was going to say for this, my answer is the same as most:

def each([],_), do: :ok
def each([head|tail], func) do
  func.(head)
  each(tail, func)
end

filter There is some conversation on this in the thread, and some invalid answers. Remember, the instructions said “using no library functions or list comprehensions” so you aren’t supposed to use Enum.reverse/1. I think Dave T. just made a typo in his answer, accidentally putting comma where he meant a pipe. My answer is the same as others:

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

split This time even Dave used Enum.reverse/1! Am I misunderstanding what “library function” means here? Figuring out the answer for non-negative counts is pretty easy, but getting negative counts without using library functions is very hard. You can see the above all use some function or another.

17 May 2015, 13:24
Generic-user-small

Rebecca Skinner (3 posts)

I’m glad I wasn’t the only one baffled by all the responses using library functions, when the task specifically says “don’t use any”.

I’m not sure about the use of

def all?(list), do: all?(list, fn x -> !!x end) # !! converts truthy to true 

either, tbh.

I like the optimization of returning false in all? if fun.(head) is false. Didn’t think of that one.

  You must be logged in to comment