1% List Library
    2:- module(plist, [
    3    plist/1,
    4    plength/2,
    5    pnth0/3,
    6    pnth1/3,
    7    pmemberchk/3,    
    8    psublist/5,
    9    ppartition/4,
   10    pinclude/3,
   11    pexclude/3,
   12    list_in_domain/2,
   13    non_member/3,
   14    remove_dups/2,
   15    list_join/3,
   16    psort/3
   17]).   18
   19:- use_module(purity).   20
   21:- multifile purity:pcompare/4.   22
   23purity:pcompare(plist(D), A, B, C) :- plist_compare(A, B, C, D). 
   24
   25/*
   26% member/2
   27member(A,[A|_]).
   28member(A,[_|T]) :-
   29    member(A,T).
   30
   31% append/3
   32append([], A, A).
   33append([A|B], C, [A|D]) :-
   34    append(B, C, D).
   35
   36% select/3
   37select(A, [A|B], B).
   38select(B, [A|C], [A|D]) :-
   39    select(B, C, D).
   40
   41% select/4
   42select(A,[A|C], B, [B|C]).
   43select(C, [A|B], D, [A|E]) :-
   44    select(C, B, D, E).
   45
   46% reverse/2
   47reverse(A,B) :-
   48    reverse(A,[],B).
   49
   50reverse([], A, A).
   51reverse([B|A], C, R) :-
   52    reverse(A, [B|C], R).
   53
   54% permutation/2
   55permutation([],[]).
   56permutation(A,[E|R]) :-
   57	select(E,A,B),
   58	permutation(B,R).
   59
   60% last/2
   61last([A],A).
   62last([_|T],A) :-
   63    last(T,A).
   64
   65
   66% prefix/2
   67prefix([], _).
   68prefix([A|B], [A|C]) :-
   69    prefix(B, C).
   70
   71% same_length
   72psame_length([],[]).
   73psame_length([_|A],[_|B]) :-
   74    psame_length(A,B).
   75*/
   76
   77
   78% plist(L).
   79%
   80% holds if L is a valid list
   81%
   82plist([]).
   83plist([_|_]).
   84
   85
   86% plist_compare(List1, List2, Comparator, Domain).
   87%
   88% compare two lists of type 'Domain' 
   89% Comparator contains either =, < or >.
   90% comparisons are in relation to the first list
   91% eg: if List1 = 3 and List2 = 4 then List1 < List2
   92%
   93% D = domain
   94% C = the comparator operator
   95% A = list1 element to compare
   96% B = list2 element to compare
   97% T1 = tail of list1
   98% T2 = tail of list2
   99% S = list2
  100% TC = temporary compartor
  101%
  102plist_compare([],S,C, _) :- plist_compare_0(S, C).
  103plist_compare([A|T1], S, C, D) :- plist_compare_1(S, [A|T1], C, D).
  104
  105plist_compare_0([], =).
  106plist_compare_0([_|_], <).
  107
  108plist_compare_1([], _, >, _).
  109plist_compare_1([A|T1], [B|T2], C, D) :-
  110        pcompare(D, B, A, TC), 
  111        plist_compare_cond(TC, T2, T1, C, D).
  112
  113plist_compare_cond(<, _, _, <, _).
  114plist_compare_cond(>, _, _, >, _).
  115plist_compare_cond(=, T1, T2, C, D) :- 
  116        plist_compare(T1, T2, C, D).
  117
  118
  119% plength(List, Length).
  120%
  121% Length is the number of elements in List using the punary domain.
  122%
  123% T = the tail of List
  124% Z = recursive part of Length
  125%
  126plength([], zero).
  127plength([_|T], c(Z)) :- plength(T, Z).
  128
  129
  130% pnth0(Nth, Val, List).
  131%
  132% Val is the Nth element in List starting at zero.
  133% Nth is a punary number.
  134%
  135% V = Val
  136% T = the tail of List
  137% Z = the recursive part of Nth.
  138%
  139pnth0(zero, V, [V|_]).
  140pnth0(c(Z), V, [_|T]) :-
  141    pnth0(Z, V, T).
  142
  143
  144% pnth1(Nth, Val, List).
  145%
  146% Val is the Nth element in List starting at c(zero).
  147% Nth is a punary number.
  148%
  149% V = Val
  150% T = the tail of List
  151% Z = the recursive part of Nth.
  152%
  153pnth1(c(zero), V, [V|_]).
  154pnth1(c(c(Z)), V, [_|T]) :-
  155    pnth1(c(Z), V, T).
  156
  157
  158% list_in-domain(Domain, List).
  159%
  160% Holds if all elements of List are in Domain.
  161%
  162% D = Domain
  163% L = List
  164% A = an element of List
  165% T = the tail of List
  166%
  167list_in_domain_( [], _ ).
  168list_in_domain_( [A|T], D ) :- 
  169	pcompare( D, A, A, = ),
  170	list_in_domain_( T, D ).
  171
  172list_in_domain( D, L ) :- 
  173    list_in_domain( L, D ).
  174
  175
  176% pmemberchk(Domain, Element, List).
  177%
  178% check if Element exists in List once only.
  179%
  180% D = Domain
  181% A = Element 
  182% L = List
  183% B = an element of List that doesn't match Element
  184% T = the tail of List
  185% C = the comparison operator
  186%
  187pmemberchk_(=,_,_,_).
  188pmemberchk_(>,A,L,D) :-
  189	pmemberchk(D,A,L).
  190pmemberchk_(<,A,L,D) :-
  191	pmemberchk(D,A,L).
  192
  193pmemberchk(D, A,[B|T]) :-
  194	pcompare(D, A, B, C ),
  195	pmemberchk_(C,A,T,D).
  196
  197
  198% non_member(Domain, Element, List).
  199%
  200% Holds if Element is not an element in List.
  201% the Element and List must be a member of Domain.
  202%
  203% D = Domain
  204% L = List
  205% A = Element
  206% B = an element of List that is different to Element
  207% T = the tail of List
  208%
  209non_member(D, A, L) :- non_member_(L, A, D).
  210
  211non_member_([], _, _).
  212non_member_([A|T], B, D) :-
  213	pdif(D, A, B),
  214	non_member_(T, B, D).
  215
  216
  217% psublist(List, Before, Length, After, SubList).
  218%
  219% SubList is contained within List in the same sequence.
  220% Before is the number of elements before SubList
  221% Length is the number of elements in SubList
  222% After is the number of elements after SubList
  223%
  224% A = an element of List 
  225% T = the tail of List
  226% St = the tail of SubList
  227% Len = Length
  228% End = After
  229% Start = Before
  230% Sub = SubList
  231%
  232% match! the start is a zero from now on    
  233psublist([A|T], zero, c(Len), End, [A|St]) :-
  234    psublist_(T, Len, End, St).
  235
  236% no match yet, nothing to see here, increment the start
  237psublist([_|T], c(Start), Len, End, Sub) :-
  238    psublist(T, Start, Len, End, Sub).
  239
  240% single character substring, ok, one length?
  241psublist_(L, zero, End, []) :-
  242    plength(L, End).
  243
  244% in the match, counting...
  245psublist_([A|T], c(Len), End, [A|St]) :-
  246        psublist_(T, Len, End, St).
  247
  248
  249% remove_dups(List, NoDups).
  250%
  251% NoDups is List without any repeating items.
  252%
  253% A = an element of List or NoDups
  254% T = the tail of List
  255% R = the tail of NoDups
  256%
  257remove_dups([],[]).
  258remove_dups([A|T],R) :-
  259	member(A,T),
  260	remove_dups(T,R).
  261remove_dups([A|T],[A|R]) :-
  262	non_member(_,A,T),
  263	remove_dups(T,R).
  264
  265
  266% list_join(ListOfLists, DelimList, ResultList).
  267%
  268% ResultList is the ListOfLists flattened with DelimList separating each list
  269% eg: ListOfLists = [[a],[b],[c]], DelimList = [','], ResultList = [a,',',b,',',c]
  270%
  271% Lol = ListOfLists
  272% Dl = DelimList
  273% Rl = ResultList
  274% E = The first element in ListOfLists
  275% E2 = The second element in ListOfLists
  276% Prev = the current accumulated ResultList
  277% PrevE = E appened to Prev
  278% Joined = Dl appended to PrevE 
  279%
  280list_join(Lol, Dl, Rl) :-
  281    list_join(Lol, [], Dl, Rl).
  282
  283list_join([], [], _, []). % joining an empty list?
  284list_join([E|T], Prev, Dl, Rl) :-
  285    list_join2(T, E, Prev, Dl, Rl).
  286
  287list_join2([], E, Prev, _, Rl) :-
  288    append(Prev, E, Rl).
  289list_join2([E2|T], E, Prev, Dl, Rl) :-
  290    append(Prev, E, PrevE),
  291    append(PrevE, Dl, Joined),
  292    list_join([E2|T], Joined, Dl, Rl).
  293
  294
  295% ppartition(Goal, List, Included, Excluded).
  296%
  297% Using Goal as the decider, the elements of list are either in Included or Excluded.
  298% Included and Excluded are also lists. 
  299%
  300% G = Goal - a pb_call formatted goal
  301% L = List
  302% I = Included
  303% E = Excluded
  304% A = the first element of List
  305% B = the binary result of Goal
  306% T = the tail of List
  307% 
  308ppartition(G,L,I,E) :-
  309    ppartition_(L,G,I,E).
  310
  311ppartition_([],_,[],[]).
  312ppartition_([A|T],G,I,E) :-
  313    call(G,A,B),
  314    ppartition__(B,[A|T],G,I,E).
  315
  316ppartition__(true, [A|T],G,[A|I],E) :- 
  317    ppartition_(T,G,I,E).
  318ppartition__(false,[A|T],G,I,[A|E]) :-
  319    ppartition_(T,G,I,E).
  320
  321
  322% pinclude(Goal, List, Included).
  323%
  324% calls partition/4 and keeps the Included part.
  325%
  326pinclude(G, L, I) :-
  327    ppartition(G, L, I, _).
  328
  329
  330% pexclude(Goal, List, Excluded).
  331%
  332% calls partition/4 and keeps the Excluded part.
  333%
  334pexclude(G, L, E) :-
  335    ppartition(G, L, _, E).
  336
  337
  338% psort(Domain, List, Sordered)
  339%
  340% Sorted is an ordered version of List.
  341% all elements in  List and Sorted must be in Domain. 
  342%
  343% D = Domain
  344% L = List
  345% S = Sorted
  346% A = the first element of List
  347% A2 = the second element of list
  348% T = the tail of List
  349%
  350% L = the left split part of List
  351% R = the right split part of List
  352% SL = the sorted version of L
  353% SR = the sorted version of R
  354%
  355psort(D, L, S) :-
  356	same_length(L, S),
  357	psort_(L, S, D).
  358
  359psort_([], [], _).
  360psort_([A|T], S, D) :-
  361    psort_1(T, A, S, D).
  362
  363psort_1([], A, [A], _).
  364psort_1([A2|T], A, S, D) :-
  365	split([A,A2|T], L, R),
  366	psort_(L, SL, D),
  367	psort_(R, SR, D),
  368	pmerge(SL, SR, S, D).
  369
  370
  371% split(List, LeftPart, RightPart )
  372%
  373% Alternate elements of LIST in L and R
  374%
  375% A = the first or an element of List
  376% A2 = the second element of List
  377% T = the tail of List
  378% LT = the tail of LeftPart 
  379% RT = the tail of RightPart
  380% 
  381split([], [], []).
  382split([A|T], R, O) :-
  383    split_(T, A, R, O).
  384
  385split_([], A, [A], []).
  386split_([A2|T], A, [A|LT], [A2|RT]) :-
  387    split(T, LT, RT).
  388
  389
  390% merge(LeftSide, RightSide, Merged, Domain)
  391% 
  392% assuming LeftSide and RightSide are sorted, Merged is the sorted merge of the two
  393% all elements in LeftSide, RightSide and Merged must be in Domain.
  394%
  395% L = an element of LeftSide
  396% Lt = the tail of LeftSide
  397% R = an element of RigtSide
  398% Rt = the tail of RightSide
  399% T = the tail of Merged
  400% D = Domain
  401% C = a comparison operator
  402%
  403pmerge( [], R, M, _ ) :- pmerge_0( R, [], M ).
  404pmerge( [L|Lt], R, M, D ) :- pmerge_x( R, [L|Lt], M, D ).
  405
  406pmerge_0( [], [], [] ).
  407pmerge_0( [R|Rt], [], [R|Rt] ).
  408
  409pmerge_x( [], [L|Lt], [L|Lt], _ ).
  410pmerge_x( [R|Rt], [L|Lt], T, D ) :-
  411	pcompare( D, L, R, C ),
  412	pmerge_( C, [L|Lt], [R|Rt], T, D ).
  413
  414pmerge_( =, [L|Lt], [R|Rt], [L,R|T], D ) :-
  415	pmerge( Lt, Rt, T, D ).
  416pmerge_( <, [L|Lt], [R|Rt], [L|T], D ) :-
  417	pmerge( Lt, [R|Rt], T, D ).
  418pmerge_( >, [L|Lt], [R|Rt], [R|T], D ) :-
  419	pmerge( [L|Lt], Rt, T, D)