Can somebody explain to me the following code:
t(L, NL) :-
t(L, [], NL).
t([], L, L).
t([H|T], A, NL) :-
t(T, [H|A], NL).
I would have implemented it completely differently:
s([], []).
s([H|T], NL) :-
s(T, NT),
append(NT, [H], NL).
You make use of an accumulator, the second parameter. Intitially this is set to the empty list, indeed:
t(L, NL) :-
t(L, [], NL). % ← empty listthen we each time perform pattern matching on the first parameter. If it is empty, we return the accumulator as reversed list:
t([], L, L). % ← list empty? Unify the accumulator L with the result (third parameter)If the list is not empty, we will perform unification with [H|T], so H is the first list, and T the list of remaining elements, and we prepend the accumulator with H:
t([H|T], A, NL) :-
t(T, [H|A], NL). % ← prepend H to the accumutor.If we thus have a list [1,4,2,5] we will each time prepend the accumulator with the head of the list and recurse on the tail, so it looks like:
list (L) | accumulator (A)
-----------------------------
[1,4,2,5] | []
[4,2,5] | [1]
[2,5] | [4,1]
[5] | [2,4,1]
[] | [5,2,4,1]
so when the we eventually call the t/3 predicate with L empty, the accumulator contains the list in reverse.
The advantage of doing this is that it is efficient: prepending takes O(1) time, just as unification with [H|T] does, so this means we reverse in O(n) time.
append/3 takes linear time in the length of the first parameter, so by using append/3 here, you obtain the reverse in O(n2) time.