greenapple
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?
Marked As Solved
benwilson512
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.
Also Liked
greenapple
I think I understand the solution. Thank you so much for the great explanation, it is very much appreciated!
benwilson512
Great!
So let’s start with something very basic: How would you do this simpler function:
prepend(1, [2,3]) #=> [1,2,3]
NobbZ
Last Post!
Aetherus
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.
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Develop your skills with books, videos, and courses.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #elixirconf-us
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking for Elixir devs who love to ship. Start your free account.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"