Recursive concatenation

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

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

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

yes that is correct

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

I would use something like

[1 | [2, 3]]

2 Likes

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

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

4 Likes

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

2 Likes

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

3 Likes

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