16 Jul 2013, 02:25
Dave_gnome_head_isolated_pragsmall

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</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 (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-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 (55 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
01 Apr 2015, 00:12
Dj-mangatar_pragsmall

Wirianto Djunaidi (4 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
  You must be logged in to comment