Splitting a list into two Separate lists

Question

I'm trying to iterate through a given list and put all the positive numbers into Y and all negatives into Z. My code works until I go to add a second element to either Y or Z. If I run the code like so "divide([1,-2],Y,Z)" the code executes with no errors its only if I were to enter "divide([1,-2,3],Y,Z)" it will fail when trying to add 3 to Y.

divide([],[Y],[Z]):- write(Y), write(Z).

divide([H|T],[Y],[Z]):- split(H,Y,Z), divide(T,Y,Z).

split(H,Y,Z):- (H>0 -> append([H],[],Y); append([H],[],Z)).

`append([H],[Y], Y).` is asking Prolog to find some solutions to put in place of those variables so that adding a list with Y in it onto the end of a list with H in it, results in Y. That seems impossible. Y can't be a list containing itself and something else. — TessellatingHeckler, Oct 04 '21 at 03:32
Do not use append/3. i repeat, do not use append/3. It is useful for splitting, mostly. [Click here](https://github.com/SWI-Prolog/swipl-devel/blob/ef73bb8c16142ae3f34b2ebb47eb8b32b8ed5eb1/library/apply.pl#L140-L158) for a solution. Replace in your code the `call` with the "is positive" comparison and you are done. — User9213, Oct 04 '21 at 03:51
Where do you put the 0s? With the positive or with the negative numbers? — TA_intern, Oct 04 '21 at 07:41
Of interest: [partition/4](https://www.swi-prolog.org/pldoc/man?predicate=partition/4) — Guy Coder, Oct 04 '21 at 17:14
[Example](https://stackoverflow.com/a/68678984/1243762) usage for partition/4. — Guy Coder, Oct 05 '21 at 11:55

CapelliC · Answer 1 · 2021-10-06T05:38:52.893

3

SWI-Prolog library(apply) offers partition/4, a builtin for your problem, but since I think that for learning you're better to correct your own code here is my advise. Keep it simpler: the base case, i.e. when you are given an empty list, would be just this simple clause:

divide([],[],[]).

Then you must handle a non empty list. If the value is positive, put it in the second list. Otherwise, put it in the third list. You see, we need two more clauses, I will show partially the second one:

divide([V|Vs],[V|Ps],Ns) :-
  V>=0,
  ...

As you see, the head parameters act as both destructuring as well as constructing the relevant values. Put a recursive call instead of the three dots, and write the third clause to handle the case V<0.

I've attempted to use descriptive variables names: Vs stands for values, Ps for positives, Ns for negatives.

edited Oct 06 '21 at 05:38

answered Oct 04 '21 at 07:10

CapelliC

59,646
5
47
90

@TA_intern: thanks you for the remarks, even more useful now that I note that User9213 deleted its comment. – CapelliC Oct 06 '21 at 05:33
1

@TA_intern: you're true, the comment it's still there. Sorry I didn't looked carefully... About "it": just I don't know how to refer to a person without being explicit about the gender. Guess I should have used "him" instead. There are some sexist assumptions builtin natural languages. For instance, in Italian, the tranlation of "user" (="utente") is male. – CapelliC Oct 06 '21 at 06:36

score 0 · Answer 2 · answered Oct 04 '21 at 07:58

0

I see the other answer and I am confuse. I have been learning by copying others who know better than me my whole life. Maybe this is why I ended up as a teaching assistant intern, instead of a real job.

Here is what I get when I follow the instructions and try to learn by imitating:

list_pos_neg([], [], []).
list_pos_neg([H|T], P, N) :-
    (   H >= 0
    ->  P = [H|P0],
        list_pos_neg(T, P0, N)
    ;   N = [H|N0],
        list_pos_neg(T, P, N0)
    ).

answered Oct 04 '21 at 07:58

TA_intern

2,222
4
12

2

The if/else pattern seems to break Prolog's ability to reason about the code generally. Apart from partitioning the list, compare some other queries between your code and @CapelliC's fleshed-out answer, e.g. `list_pos_neg(List,[],[]).` his returns an answer and then false, yours returns an answer and then an error. Try `list_pos_neg(A,[4,5],[-1,-2]).` and yours gives an error. His gives `A = [4, 5, -1, -2]` reconstituting the original list, and on backtracking can generate more permutations. Try `list_pos_neg([X,-1], [2], N).`, his can solve for X and yours can't. – TessellatingHeckler Oct 05 '21 at 04:31
@TessellatingHeckler there are trade offs between the different solutions. Without a good reason to prefer the one over the other, they are all equally broken for some use case that someone can think of. – TA_intern Oct 05 '21 at 06:52
1

Your assertion that all things are different therefore there's no difference between them and no reason to prefer one over another, is not sitting comfortably in my head. – TessellatingHeckler Oct 05 '21 at 14:37
@TessellatingHeckler This is an interesting spin on my comment and it leads me to suspect that you did not understand it. This is fine with me. – TA_intern Oct 06 '21 at 05:58

score -1 · Answer 3 · answered Oct 04 '21 at 15:41

I usually try to avoid the cut and use -> ; instead. But in this case, I think it is clearer this way:

div_pos_neg([], [], []).
div_pos_neg([H|T], [H|P], N) :- H >= 0, !, div_pos_neg(T, P, N).
div_pos_neg([H|T], P, [H|N]) :- H <  0,    div_pos_neg(T, P, N).

Note that the condition is still necessary in the last clause so that calls like div_post_neg([1,2], [], [1, 2]) return the right answer (failure!).

score -2 · Answer 4 · answered Oct 04 '21 at 18:24

-2

That seems ... complicated. How about just

partition( []     , []     , []     ) .
partition( [X|Xs] , [X|Ns] , Ps     ) :- X <  0 , partition(Xs,Ns,Ps) .
partition( [X|Xs] , Ns     , [X|Ps] ) :- X >= 0 , partition(Xs,Ns,Ps) .

answered Oct 04 '21 at 18:24

Nicholas Carey

71,308
16
93
135

Splitting a list into two Separate lists

4 Answers4