Home / Questions / 543869
Accepted
MxiDev
Asked: 2022-08-31 10:35:24 +0800 CST 2022-08-31 10:35:24 +0800 CST

Detail in Prolog code implementation

  • 772

I am trying to implement code in Prolog that will split a list into two parts. Basically, if it is of even length the result is trivial, since the halves are the same size. But for the odd case the left part must contain one more element than the one on the right. It is explained with the following example:

?- div([1,2,3,4,5],X,Y). %Largo impar
X = [1,2,3]
Y = [4,5]

The implementation I thought of, watching some videos and tutorials, was the following:

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    N1 is N + 1,
    length(B, N1).

However, for cases where the list is of odd length, it returns:

?- div([1,2,3,4,5],X,Y).
X = [1,2]
Y = [3,4,5]

I don't know what I may be missing to organize the elements well in the odd length lists. I hope someone can guide me.

prolog

1 Answers

  1. Best Answer

    So that when the list is of odd length, the "odd" element remains in the first list, you must change the restriction of the lengths of both lists so that the first is one unit more than the second.

    Namely,

    div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).
div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    N > 0,  % largo de A mayor a 0
    N1 is N - 1,  % largo de B es uno menos que el de A
    length(B, N1).

    In this way we obtain:

    ?- div([1,2,3,4,5],X,Y). %Largo impar
X = [1,2,3]
Y = [4,5]

    This program is not very efficient as it tries to partition the list in all possible ways until the constraints are met. In addition, although it finds a solution, it leaves open alternatives that must be re-evaluated later (and in general, if the list is not open, it will not find more solutions).

    To solve both problems, you can implement an algorithm that calculates half the length of the list and builds the result on the run. This way you avoid leaving alternatives open and you get the result by going through the list only once:

    div(L, A, B):-
  div(L, L, A, B).
  
div([], B, [], B).
div([_|R], [X|L], [X|A], B):-
  div1(R, L, A, B).
  
div1([], B, [], B).
div1([_|R], L, A, B):-
  div(R, L, A, B).

    Test cases:

    ?- div([1,2,3,4], A, B).
A = [1, 2],
B = [3, 4].

?- div([1,2,3,4,5], A, B).
A = [1, 2, 3],
B = [4, 5].
    • 2