CODEWITHSUNDEEP
prolog
mik
mik

Reputation: 21

Prolog program comprehension

This is the program I have:

foo(L,[H|R1]) :-
    foo(L,R1,H).

foo([H],[],H).
foo([H|T],[H|T1],R) :-
    foo(T,T1,R).

This is the query:

foo([1,2,3,4,5,6],X).

I don't understand what this program does, can someone help me and explain how does it work?

Upvotes: 2

Views: 126

Answers (3)

false
false

Reputation: 10120

In Prolog, there is no need to understand the source code. Instead, let Prolog do this for you. Just ask the most general query:

?- foo(L,R).
   L =    [_A],
   R =    [_A]
;  L =    [_A,_B],
   R = [_B,_A]
;  L =    [_A,_B,_C],
   R = [_C,_A,_B]
;  L =    [_A,_B,_C,_D],
   R = [_D,_A,_B,_C]
;  L =    [_A,_B,_C,_D,_E],
   R = [_E,_A,_B,_C,_D]
;  L =    [_A,_B,_C,_D,_E,_F],
   R = [_F,_A,_B,_C,_D,_E]
;  L =    [_A,_B,_C,_D,_E,_F,_G],
   R = [_G,_A,_B,_C,_D,_E,_F]
;  L =    [_A,_B,_C,_D,_E,_F,_G,_H],
   R = [_H,_A,_B,_C,_D,_E,_F,_G]
;  ... .

Do you see a pattern here?

Upvotes: 2

Will Ness
Will Ness

Reputation: 71074

To understand it easier, put the recursive clause above the base one:

foo( [H | T], [H | T1], R) :- foo(          /* T = [_|_] */
          T,       T1,  R).
foo( [R],     [],       R).

So we advance along the two lists (that hold the same elements, H) until we hit the last element in the first list ([R]), at which point the second list is exhausted ([]), and we get hold of that last element (R).

This means that foo( A, B, R) :- append( B, [R], A).. Thus,

foo( L, [E | R1]) :- % foo( L, R1, E).
                     append( R1, [E], L).    % R1 ++ [E] = L

i.e. foo( L, M) relates two lists L, M, where L is M with its first element E "flipped" to the list's end:

 L :     .............E
 M :    E.............
 %       ---- R1 -----

Upvotes: 0

user502187
user502187

Reputation:

You could try to refactor it. If I start with:

foo(L, [H|R1]) :-
    foo(L, R1, H).

foo([H], [], H).
foo([H|T], [H|T1], R) :-
    foo(T, T1, R).

I can change the argument order foo(1,2,3) to foo(2,3,1):

foo(L,[H|R1]) :-
    foo(R1, H, L).

foo([], H, [H]).
foo([H|T1], R, [H|T]) :-
    foo(T1, R, T).

Now I can change the 2-nd argument of foo, and pass [H] instead of H:

foo(L, [H|R1]) :-
    foo(R1, [H], L).

foo([], H, H).
foo([H|T1], R, [H|T]) :-
    foo(T1, R, T).

Now you can rename the predicates to roll and append:

roll(L, [H|R1]) :-
    append(R1, [H], L).

append([], H, H).
append([H|T1], R, [H|T]) :-
    append(T1, R, T).

Upvotes: 2

Related Questions