Recursive concatenation

Questions / Help
1

Hi,
I’m a beginner, and I’m trying to solve a rather simple question but I’m kinda stuck. I’m trying to write a fully-recursive function that appends a list to the other one, and I’m also not allowed to use any pre-written functions (like Enum.concat or ++ ). I’m honestly not even sure where I would start. I imagine there would be some pattern matching involved and maybe a base case with just one element in each list but I’m not sure. Can somebody help me with this please?

2 Likes
2

Hi @greenapple, welcome!

Just to make sure I understand what you’re going for, you’re trying to achieve basically:

concat([1,2], [2,4]) #=> [1,2,3,4]
2 Likes
3

Hi,
Thank you for replying. So for example concat ([1, 2, 3] , [4, 5, 6]) would return [1, 2, 3, 4, 5, 6]

4

yes that is correct

5

Great!

So let’s start with something very basic: How would you do this simpler function:

prepend(1, [2,3]) #=> [1,2,3]
3 Likes
6

I would use something like

[1 | [2, 3]]

2 Likes
7

Right perfect. And if you wanted to do a concat on a list that just took one item, you could do:

def concat([item], list) do
  [item | list]
end

concat([1], [2,3] #=> [1,2,3]

The trick then is to just apply this logic recursively. When doing recursive logic, it’s always a good idea to identify the “base case” which you can think of as “when do I stop recursing?”. In the case of this kind of concat function, you stop recursing when you have just 1 item in the list, because at that point you do a simple prepend.

When you have more than one item, you need to recursively prepend until you hit the base case:

def concat([], list), do: list

def concat([item], list) do
  [item | list]
end

def concat([item | rest], list) do
  [item | concat(rest, list)]
end

The first part of [item | concat(rest, list)] is [item | which you’re already familiar with, that’s setting up item to be prepended to whatever is on the right hand side of |. But this time, instead of prepending it to | list] we do | concat(rest, list)] because we want the item to come before the result of prepending all of the other items.

9 Likes
8

I think I understand the solution. Thank you so much for the great explanation, it is very much appreciated!

4 Likes
9

The Erlang implementation of :lists.flatten/1 is similar, simple and efficient.

2 Likes
10

I think you are missing an edge case here: concat([], [1,2,3])

3 Likes
11

I believe if you’re trying to find a more ubiquitous solution, implementing reduce/3 and optionally reduce/2 first should always be the way to go because all list operations can be implemented using reduce, including reduce itself.

@type item :: any
@type acc :: any

@spec reduce([item], acc, (item, acc -> acc)) :: acc
def reduce([], acc, _fun) do
  acc
end

def reduce([item | rest], acc, fun) do
  reduce(rest, fun.(item, acc), fun)
end

Then you can implement reverse using reduce.

@spec reverse([item]) :: [item]
def reverse(list) do
  reduce(list, [], fn item, acc -> [item | acc] end)
end

And finally, you have enough tools to implement concat.

@spec concat([item], [item]) :: [item]
def concat(list1, list2) do
  list1
  |> reverse()
  |> reduce(list2, fn item, acc -> [item | acc] end)
end

See? Down the rabbit hole, it’s just about recursion.

1 Like