Understanding Erlang Basic recursion with function guards

Question

I've been looking at some Erlang recursion examples asked earlier here on stackoverflow.

Specifically with this question Erlang basic recursion with guards

But I can't quite understand how the code works. So I have created a module to see the results it returns with a simple list with 3 elements.

-module(recursion). 
-export([start/0]). 


start() -> 
    List = [1,2,3],
    Final = delete(1,List),
    Final.
   

delete(_, []) -> 
    io:format("return []~n~n~n"),
    [];
delete(Del, [Del|Xs]) ->
    io:format("~p =:= ~p~n",[Del,Del]),
    io:format("delete(~p, ~p)~n~n~n~n",[Del,Xs]),
    delete(Del, Xs);
delete(Del, [X|Xs]) ->
    io:format("~p =/= ~p~n",[Del,X]),
    io:format(" [~p|delete(~p, ~p)]~n~n~n~n",[X,Del,Xs]),
    [X|delete(Del, Xs)].

And this is the result of the log

1> recursion:start().
1 =:= 1
delete(1, [2,3])



1 =/= 2
 [2|delete(1, [3])]                



1 =/= 3
 [3|delete(1, [])]               


return []    The result of the 'Final' variable of the main function, shouldn't it be []?
             bacause [3|delete(3, [])] in the last call matches with delete(_, []) -> []
             
             or is it this way?  [2,[3,[]]] -> [2,3]


[2,3]
2> 

My question is: Every time the program calls delete(Del, [X|Xs]) ->, is the function returning the value to the previous call? Is it being stored somewhere? or is it just something like that? [2,[3,[]]] -> [2,3]

edit: I think I have found the solution in this link, about how the final result is built https://learnyousomeerlang.com/starting-out-for-real#lists where

13> List = [2,3,4].
[2,3,4]
14> NewList = [1|List].
[1,2,3,4]

So [2|[3|[]]] -> [2,3]

is that so?

Answer 1

Yes.

This is how the function works:

1. If the head of the list matches the first argument, 1 in this case, then the head of the list isn't saved anywhere, i.e. it's skipped, and the function is called again with the tail of the list:

    delete(Del, [Del|Xs]) ->
        delete(Del, Xs);
   

2. If the head of the list does NOT match the first argument, then the head of the list is saved by adding it to a result list:

   [X|delete(Del, Xs)].
   

3. When the list is empty, the function returns [], which is very important when cons'ing elements together:

    [3 | f(X) ]
   

if f(X) does not return a list at some point, then the list won't be a proper list. A proper list, such as:

    [1, 2, 3]

is equivalent to:

    [1 | [2 | [3 | [] ]]]

as you can see here:

    2> [1 | [2 | [3 | [] ]]].
    [1,2,3]

When you write:

[X|delete(Del, Xs)]

that's a little be tricky, and you need some experience to know how that works. You can understand things better, by writing out by hand what is happening:

delete(1, [1,2,3])
        |
        V
   delete(1, [2, 3])
           |
           V
      [2 | delete(1, [3]) ]  %% Can't know the result here without determining the return value of delete(1, [3])
                    |
                    V
                [3 | delete(1, []) ]  %% Can't know the result here without determining the return value of delete(1, [])
                          |
                          V
                          []

Once, you've got the return value [], because there are no more function calls in the result, now you can move upwards substituting:

delete(1, [1,2,3])
        |
        V
   delete(1, [2, 3])
           |
           V
      [2 | delete(1, [3]) ]
                    |
                    V
                [3 | [] ]

And substituting again:

delete(1, [1,2,3])
        |
        V
   delete(1, [2, 3])
           |
           V
      [2 | [3 | [] ] ]

which is equivalent to:

[2, 3]

Here is a conceptually simpler version of delete():

start() -> 
    List = [1,2,3],
    Final = delete(1,List),
    Final.
   

delete(Term, List) ->
    delete(Term, List, _Acc=[]).

delete(_, [], Acc) -> 
    Acc;
delete(Term, [Term|Xs], Acc) ->
    delete(Term, Xs, Acc);
delete(Term, [X|Xs], Acc) ->
    delete(Term, Xs, [X|Acc]).

However, the result is:

 [3, 2]

So, when you use an accumulator variable, you need to reverse the final result:

delete(_, [], Acc) -> 
    lists:reverse(Acc);