Is there a has_type/2 for difference list?

Help! Predicate
,
1

has_type/2 is used with must_be/2 and is_of_type/2.

It can be used to identify closed list, e.g. is_of_type(list,L) and open list (partial list), e.g.

:- multifile

error:has_type/2.

error:has_type(partial_list,L0) :-
    '$skip_list'(_, L0,L),
    var(L).

Is there a has_type(difference_list,DL) defined somewhere? (A predicate that can verify that 2 list/values make a difference list.)

Found some predicates with related concepts:

list_difference/3 by @stassa.p

diff_list_length/3 by Jan W.

or is it as simple as using dl_append/6

dl_append(DL_1,DL_2,DL_2,Hole_2,DL_1,Hole_2).
1 Like
2

This is what I currently have. It has not been converted into has_type/2 but that is just a wrapper for consistency and ease of using.

** If you are up for a challenge you should try to do this for yourself. **

It is a simple predicate that returns true or false with predicate indicator list_difference(L1,L2).

Current code - click triangle to expand. 
list_difference(L1,L2) :-
    '$skip_list'(Length1,L1,_),
    '$skip_list'(Length2,L2,_), !,
    Length1 >= Length2,
    list_difference(Length1,Length2,L1,L2).

list_difference(Length,Length,L1,L2) :-
    \+ '$skip_list'(Length,L1,_),
    \+ '$skip_list'(Length,L2,_),
    ground(L1),
    ground(L2),
    L1 == L2, !.
list_difference(Length,Length,L1,L2) :-
    '$skip_list'(Length,L1,_),
    '$skip_list'(Length,L2,_),
    ground(L1),
    ground(L2),
    L1 == L2, !.
list_difference(Length,Length,L1,L2) :-
    var(L1),
    var(L2),
    L1 == L2, !.
list_difference(Length10,Length2,L1,L2) :-
    Length10 > 0,
    Length1 is Length10 - 1,
    L1 = [_|T0],
    list_difference(Length1,Length2,T0,L2).

No longer needing to tinker with it for corner cases. Also can probably reduce two of the clauses into one but it is late.

Example run.

?- list_difference(A,B).
false.

?- list_difference([1|T1],T2).
false.

?- list_difference([1,2,3],[2]).
false.

?- list_difference(A,A).
true.

?- list_difference([],[]).
true.

?- list_difference([1|T1],T1).
true.

?- list_difference([1],[1]).
true.

?- list_difference([1],[]).
true.

?- list_difference([1,2],[]).
true.

?- list_difference([1,2],[2]).
true.

Still need to do a lot more test cases.

EDIT

New version passing more extensive test cases.

Code 
error:has_type(difference_list,(L1-L2)) :-
    difference_list_type_check((L1-L2)).

difference_list_type_check((L1-L2)) :-
    error:has_type(list_or_partial_list,L1),
    error:has_type(list_or_partial_list,L2),
    '$skip_list'(Length1,L1,_),
    '$skip_list'(Length2,L2,_), !,
    Length1 >= Length2,
    difference_list_type_check(Length1,Length2,L1,L2).

difference_list_type_check(Length,Length,L1,L2) :-
    ground(L1),
    ground(L2),
    L1 == L2, !.
difference_list_type_check(Length,Length,L1,L2) :-
    var(L1),
    var(L2),
    L1 == L2, !.
difference_list_type_check(Length10,Length2,[_|T],L2) :-
    Length10 > 0,
    Length10 > Length2, !,
    Length1 is Length10 - 1,
    difference_list_type_check(Length1,Length2,T,L2).
difference_list_type_check(Length0,Length0,[H|T1],[H|T2]) :-
    Length0 > 0,
    Length is Length0 - 1,
    difference_list_type_check(Length,Length,T1,T2).
Test cases 
:- begin_tests(difference_list).

% Turn off singleton variable warnings in this module.
:- style_check(-singleton).

difference_list_type_check_test(success,01,(T1-T1)).
difference_list_type_check_test(success,02,([1|T1]-T1)).
difference_list_type_check_test(success,03,([1,2|T1]-T1)).
difference_list_type_check_test(success,04,([1,2,3|T1]-T1)).
difference_list_type_check_test(success,05,([1|T1]-[1|T1])).
difference_list_type_check_test(success,06,([1,2|T1]-[2|T1])).
difference_list_type_check_test(success,07,([1,2,3|T1]-[3|T1])).
difference_list_type_check_test(success,08,([1,2|T1]-[1,2|T1])).
difference_list_type_check_test(success,09,([1,2,3|T1]-[2,3|T1])).
difference_list_type_check_test(success,10,([1,2,3,4|T1]-[3,4|T1])).
difference_list_type_check_test(success,11,([1,2,3|T1]-[1,2,3|T1])).
difference_list_type_check_test(success,12,([1,2,3,4|T1]-[2,3,4|T1])).
difference_list_type_check_test(success,13,([]-[])).
difference_list_type_check_test(success,14,([1]-[])).
difference_list_type_check_test(success,15,([1,2]-[])).
difference_list_type_check_test(success,16,([1,2,3]-[])).
difference_list_type_check_test(success,17,([1]-[1])).
difference_list_type_check_test(success,18,([1,2]-[2])).
difference_list_type_check_test(success,19,([1,2,3]-[3])).
difference_list_type_check_test(success,20,([1,2]-[1,2])).
difference_list_type_check_test(success,21,([1,2,3]-[2,3])).
difference_list_type_check_test(success,22,([1,2,3,4]-[3,4])).
difference_list_type_check_test(success,23,([1,2,3]-[1,2,3])).
difference_list_type_check_test(success,24,([1,2,3,4]-[2,3,4])).
difference_list_type_check_test(success,25,([A|B]-B)).
difference_list_type_check_test(success,26,([A|B]-[A|B])).
difference_list_type_check_test(success,27,([A,B|C]-C)).
difference_list_type_check_test(success,28,([A,B|C]-[B|C])).
difference_list_type_check_test(success,29,([A,B|C]-[A,B|C])).
difference_list_type_check_test(success,30,([1,A|B]-B)).
difference_list_type_check_test(success,31,([1,A|B]-[A|B])).
difference_list_type_check_test(success,32,([1,A|B]-[1,A|B])).
difference_list_type_check_test(success,33,([A,1|B]-B)).
difference_list_type_check_test(success,34,([A,1|B]-[1|B])).
difference_list_type_check_test(success,35,([A,1|B]-[A,1|B])).

difference_list_type_check_test(fail   ,01,([1|T1]-[1|T2])).
difference_list_type_check_test(fail   ,02,([1,2|T1]-[2|T2])).
difference_list_type_check_test(fail   ,03,([1,2,3|T1]-[3|T2])).
difference_list_type_check_test(fail   ,04,([1,2|T1]-[1,2|T2])).
difference_list_type_check_test(fail   ,05,([1,2,3|T1]-[2,3|T2])).
difference_list_type_check_test(fail   ,06,([1,2,3,4|T1]-[3,4|T2])).
difference_list_type_check_test(fail   ,07,([1,2,3|T1]-[1,2,3|T2])).
difference_list_type_check_test(fail   ,08,([1,2,3,4|T1]-[2,3,4|T2])).
difference_list_type_check_test(fail   ,09,([]-T2)).
difference_list_type_check_test(fail   ,10,([1]-T2)).
difference_list_type_check_test(fail   ,11,([1,2]-T2)).
difference_list_type_check_test(fail   ,12,([1,2,3]-T2)).
difference_list_type_check_test(fail   ,13,(T1-T2)).
difference_list_type_check_test(fail   ,14,([1|T1]-T2)).
difference_list_type_check_test(fail   ,15,([1,2|T1]-T2)).
difference_list_type_check_test(fail   ,16,([1,2,3|T1]-T2)).
difference_list_type_check_test(fail   ,17,([]-[1])).
difference_list_type_check_test(fail   ,18,([1]-[2])).
difference_list_type_check_test(fail   ,19,([1,2]-[3])).
difference_list_type_check_test(fail   ,20,([1]-[1,2])).
difference_list_type_check_test(fail   ,21,([1,2]-[2,3])).
difference_list_type_check_test(fail   ,22,([1,2,3]-[3,4])).
difference_list_type_check_test(fail   ,23,(a-b)).
difference_list_type_check_test(fail   ,24,(a-T2)).
difference_list_type_check_test(fail   ,25,((a)-T2)).
difference_list_type_check_test(fail   ,26,([[]]-T2)).
difference_list_type_check_test(fail   ,27,(a-a)).
difference_list_type_check_test(fail   ,28,([]-a)).
difference_list_type_check_test(fail   ,29,(a-[])).

test(is_type_success,[forall(difference_list_type_check_test(success,_,(L1-L2)))]) :-
    difference_list_type_check((L1-L2)).

test(is_type_fail,[fail,forall(difference_list_type_check_test(fail,_,(L1-L2)))]) :-
    difference_list_type_check((L1-L2)).

:- end_tests(difference_list).

Example run.

?- run_tests.
% PL-Unit: difference_list ................................................................ done
% All 64 tests passed
true.

If it was not for the help I received in this post of better understating what is a difference list I would not have been able write this code.

3

Isnā€™t that very complicated? I came to this:

Click to see code 
list_difference(L, T) :-
    L == T,
    !,
    is_of_type(list_or_partial_list, L).
list_difference(DL, T) :-
    nonvar(DL),
    DL = [_|L],
    list_difference(L, T).

The only minor problem might be that this loops if the first argument is a cyclic list, so you may want a layout around it using ā€˜$skip_listā€™ to verify this isnā€™t the case. This wrapper may also be used to test for the really common case where the first argument is a list for which the tail is a variable that is the second argument.

1 Like
4

Thanks. :grinning:

This reminds me of when a mathematician does a proof then another mathematician comes up with a different proof and others learn from it.

Your code passed all of my test including a few I have yet to post.

Now to dissect it to better understand it.

I hope you plan to add this to error.pl.

Personal notes
  1. L == T - The comparison is able to handle list with variables and ground values in the same list. Did not know that ==/2 was that powerful.
?- [A,1,B] == [A,1,B].
true.

?- [A,1|B] == [A,1|B].
true.
  1. nonvar/1 - Not use to using this. Will have to consider it when I use either var/1 or ground/1.
5

Iā€™m not seeing the point very clearly. Never felt the need to check for a difference list as a type check. I think one should in general be careful with must_be/2 and friends. They easily make your code slow and unreadable. They are mostly a poor menā€™s alternative for a proper type system. I only use them to trap common mistakes that would otherwise lead to silent failures. Notably I wonā€™t use them if some built-in will catch the mistake anyway.

It is commonly used when you want to check something is (now) of some specific compound and you want to process the arguments. Just unifying with the compound would bind a possible plain variable with the compound. You can also consider subsumes_term/2, but I always forget the argument order :frowning:

1 Like
6

I see your point in the rest of the paragraph. The reason I was suggesting it was that I spent more than a year or two never fully understanding difference list and am only now starting to feel confident that I am understanding them. When learning it would have been helpful to see the test cases for the difference list and have the has_type/2 for difference_list as a safety net.

But if the has_type/2 for difference list is in the production code then others might think that is the way to go when it is not as you note.

After this little exercise I realize how much I need to fix the Wiki on difference list.

Thanks. :grinning:

7

list_difference/3 by @stassa.p

Uh, unfortunately thatā€™s just my clumsy attempt at set difference. I think. Thatā€™s very old code from my graduate days.

Gods but it looks awful :frowning:

8

Did you look at the post by Jan. There is code which can be revealed by clicking Click to see code.

I changed the visibility of the code so that people who want to try and write the predicate as an exercise donā€™t accidentally see the code. His code is elegant.

9

Yes, I read Janā€™s code and yours. Mine didnā€™t do the same thing at all. I wrote the original version of the project that is now on github for WIN-LPA Prolog and I guess it was missing library(lists)? So I didnā€™t realise there were already library predicates to do what I wanted, which was to find the set difference of two sets, represented as lists. The name ā€œlist_differenceā€ is just very misleading, the predicate didnā€™t have anything to do with difference lists. As far as I can remember.

10

Yes, I found that out when I tested your code.