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 23puritypcompare(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)