small medium large xlarge

Dave_gnome_head_isolated_pragsmall
16 Jul 2013, 02:25
Dave Thomas (344 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>

Generic-user-small
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}
Generic-user-small
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
Generic-user-small
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).

Generic-user-small
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

Generic-user-small
06 Sep 2013, 19:16
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)
Nathan-6kites_pragsmall
11 Mar 2014, 22:07
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
Patrick_pragsmall
04 Aug 2014, 07:57
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
Generic-user-small
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
9863_pragsmall
05 Dec 2014, 21:15
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
Generic-user-small
13 Dec 2014, 17:52
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
Generic-user-small
26 Dec 2014, 22:26
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
Dj-mangatar_pragsmall
21 May 2015, 21:03
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

Me_pragsmall
10 Apr 2015, 22:50
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
Generic-user-small
27 Apr 2015, 02:22
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.

C2f77d9bcc71d1f9ddabd89a8ddf9615_pragsmall
17 May 2015, 13:24
Rebecca Skinner (6 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