check/2 predicate in prolog that will have sorted list of lists

Question

I am new to prolog and I am trying to create a simple predicate which will have sorted list of lists from a unsorted list of lists. check(A,B).

check( [ [], [1], [1,1] ], [ [], [1,1], [1] ] ). returns true
check( [ [], [1], [1,1] ], [ [1,1], [1] ] ). returns false.

Note that even if A is sorted it should only contain elements from B and not anything more or less.

How do I implement this without any built in prolog predicates?

What you describe does not seem to be sorting. For your example sort([[],[1],[1,1]], X) I get X = [[], [1], [1, 1]] (not [[],[1,1],[1]]). — Wouter Beek
X is unsorted and left variable is sorted. Not the other way around. — alok
Have you made any attempt at a solution? You should show your code and indicate where you are stuck. — lurker

Nicholas Carey Nicholas Carey · Accepted Answer · 2014-11-04T01:31:09

A list of lists is essentially a tree structure: you just walk the tree. Something like this:

validate( [] , _ ) .
validate( [X|Xs] , Valids ) :-
  exists_in( X , Valids ) ,
  validate( Xs , Valids )
  .

exists_in( X , [X|Xs] ) :- !.
exists_in( X , [_|Xs] ) :- exists_in( X , Xs ) .

check/2 predicate in prolog that will have sorted list of lists

1 Answers