CODEWITHSUNDEEP
listprologreverse
Haise Sasaki
Haise Sasaki

Reputation: 329

Reversing the item order of a list in prolog

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).

Upvotes: 2

Views: 149

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476544

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 list

then 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.

Upvotes: 1

Related Questions