Geek asks and answers

Prologue - What is the logic of this

I tried to understand how this code works, but I failed. It merges the two lists and then cancels the result.

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).


concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).


concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

My teacher told me to go into debug mode and trace the request to understand, but it did not help.

here is an example

5 ?- trace,concat_reverse([1,3],[4,5],S).
   Call: (7) concat_reverse([1, 3], [4, 5], _G1444) ? creep
   Call: (8) concat([1, 3], [4, 5], _G1569) ? creep
   Call: (9) concat([3], [4, 5], _G1564) ? creep
   Call: (10) concat([], [4, 5], _G1567) ? creep
   Exit: (10) concat([], [4, 5], [4, 5]) ? creep
   Exit: (9) concat([3], [4, 5], [3, 4, 5]) ? creep
   Exit: (8) concat([1, 3], [4, 5], [1, 3, 4, 5]) ? creep
   Call: (8) reverse([1, 3, 4, 5], _G1444) ? creep
   Call: (9) reverse([1, 3, 4, 5], [], _G1444) ? creep
   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep
   Call: (12) reverse([5], [4, 3, 1], _G1444) ? creep
   Call: (13) reverse([], [5, 4, 3, 1], _G1444) ? creep
   Exit: (13) reverse([], [5, 4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (12) reverse([5], [4, 3, 1], [5, 4, 3, 1]) ? creep
   Exit: (11) reverse([4, 5], [3, 1], [5, 4, 3, 1]) ? creep
   Exit: (10) reverse([3, 4, 5], [1], [5, 4, 3, 1]) ? creep
   Exit: (9) reverse([1, 3, 4, 5], [], [5, 4, 3, 1]) ? creep
   Exit: (8) reverse([1, 3, 4, 5], [5, 4, 3, 1]) ? creep
   Exit: (7) concat_reverse([1, 3], [4, 5], [5, 4, 3, 1]) ? creep
S = [5, 4, 3, 1].
+3
source share
4 answers

Let's look at it in parts.

You used:

concat_reverse([1,3],[4,5],S).

The prologue is trying to combine this.

concat_reverse(L1,L2,L)

Matches. L1integrates with [1,3]and L2integrates with [4,5]. So, we look at the right side:

concat_reverse(L1,L2,L):-concat(L1,L2,LN),reverse(LN,L)

The prolog does the first depth search for unification, so it checks concat(L1,L2,LN)again with unified L1and L2.

Let's look at two concattogether:

concat([], L, L).
concat([H|T1], L2, [H|T]):- concat(T1, L2, T).

, , . , -, . , Prolog .

, -, , , . , . . " " -. , concat, , " ".

. , . , . . . . . . . , concat concat_reverse.

reverse concat_reverse. Exit(8)/Call(8) . , :

reverse(L, RL):- reverse(L, [], RL).
reverse([], RL, RL).
reverse([H|T], S, RL):- reverse(T, [H|S], RL).

, , . reverse. , ( , ). .

, . , - , .

, , , ( ).

, -, , . , . , concat_reverse.

, , . ( , ). reverse , concat concat_reverse.

+3

: , , , -...

, , :

concat_reverse(L1,L2,L):-reverse(L2,R,L),reverse(L1,[],R).

:

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

iseq([]) -->
   [].
iseq([E|Es]) -->
   iseq(Es),
   [E].

concat_reverse2(L1,L2,L) :-
   phrase( ( iseq(L2), iseq(L1) ), L).

, .

+3

( ) Prolog, .

, concat_reverse : "L - concat_reverse L1 L2, LN L1 L2, -, L LN".

concat, : " [] L L." " [H | T1] L2 [H | T], T1 L2 T.

, - . "concat", : " concat? . [H | T]? L M, M H, M T L. , concat ([H | T], L) M, M [H | RM] concat (T, L) RM."

, , : "RL - L, ...". . , , "S L ( RL), L , S ".

, reverse ([], RL, RL) - RL RL, L RL .

, L [H | T], RL S, [H | S] RL.

, "". . , - :

concat_of_reversed_suffix_and_S([H|T], S, RL) :- concat_of_reversed_suffix_and_S(T, [H|S], RL).

- [H | T] - T, H. [H | T] L S RL, T H, S, RL. :

reverse([H|T], S, RL) :- reverse(T, [H|S], RL).

The debugger can show you this process, but it's better to have a story in your head that explains it, and then you can confirm it with the debugger.

In this case, you can see:

   Call: (10) reverse([3, 4, 5], [1], _G1444) ? creep
   Call: (11) reverse([4, 5], [3, 1], _G1444) ? creep

[3,4,5] is the suffix L, [1] is the suffix RL. This is true only if [3,1] is also the suffix RL, leaving [4,5] as the (smaller) suffix L for consideration.

0
source 

concat_reverse(L1,L2,L) :-
        concat_reverse(L1,L2,[],L).

concat_reverse([],[],L,L).
concat_reverse([],[B|R2],L3,L) :-
        concat_reverse([],R2,[B|L3],L).
concat_reverse([A|R1],L2,L3,L) :-
        concat_reverse(R1,L2,[A|L3],L).
0
source

More articles:


All Articles