home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / p / plbin.zip / pl / boot / list.pl < prev    next >
Text File  |  1992-05-26  |  4KB  |  188 lines
  1. /*  list.pl,v 1.1.1.1 1992/05/26 11:51:22 jan Exp
  2.  
  3.     Copyright (c) 1990 Jan Wielemaker. All rights reserved.
  4.     jan@swi.psy.uva.nl
  5.  
  6.     Purpose: basic list predicates
  7. */
  8.  
  9. :- module($list,
  10.     [ length/2
  11.     , select/3
  12.     , delete/3
  13.     , nth0/3
  14.     , nth1/3
  15.     , last/2
  16.     , reverse/2
  17.     , flatten/2
  18.     , is_set/1
  19.     , list_to_set/2
  20.     , intersection/3
  21.     , union/3
  22.     , subset/2
  23.     , subtract/3
  24.     ]).
  25.  
  26. %    length(?List, ?N)
  27. %    Is true when N is the length of List.
  28.  
  29. length(List, Length) :-
  30.     $length(List, Length), !.        % written in C
  31. length(List, Length) :-
  32.     var(Length),
  33.     length2(List, Length).
  34.  
  35. length2([], 0).
  36. length2([_|List], N) :-
  37.     length2(List, M), 
  38.     succ(M, N).
  39.  
  40. %    select(?List1, ?Elem, ?List2)
  41. %    Is true when List1, with Elem removed results in List2.
  42.  
  43. select([X|Tail], X, Tail).
  44. select([Head|Tail], Elem, [Head|Rest]) :-
  45.     select(Tail, Elem, Rest).
  46.  
  47. %    delete(?List1, ?Elem, ?List2)
  48. %    Is true when Lis1, with all occurences of Elem deleted results in
  49. %    List2.
  50.  
  51. delete([], _, []) :- !.
  52. delete([Elem|Tail], Elem, Result) :- !, 
  53.     delete(Tail, Elem, Result).
  54. delete([Head|Tail], Elem, [Head|Rest]) :-
  55.     delete(Tail, Elem, Rest).
  56.  
  57. %    nth0(?Index, ?List, ?Elem)
  58. %    Is true when Elem is the Index'th element of List. Counting starts
  59. %    at 0.
  60.  
  61. nth0(Index, List, Elem) :-
  62.     integer(Index), !,
  63.     nth0_1(Index, List, Elem).
  64. nth0(Index, List, Elem) :-
  65.     var(Index), !,
  66.     nth0_2(Index, List, Elem).
  67.  
  68. nth0_1(0, [Elem|_], Elem) :- !.        % take nth deterministically
  69. nth0_1(N, [_|Tail], Elem) :-
  70.     M is N - 1,
  71.     nth0(M, Tail, Elem).
  72.  
  73. nth0_2(0, [Elem|_], Elem).        % match
  74. nth0_2(N, [_|Tail], Elem) :-
  75.     nth0_2(M, Tail, Elem), 
  76.     succ(M, N).
  77.  
  78. %    nth1(?Index, ?List, ?Elem)
  79. %    Is true when Elem is the Index'th element of List. Counting starts
  80. %    at 1.
  81.  
  82. nth1(Index, List, Elem) :-
  83.     integer(Index), !,
  84.     N is Index - 1,
  85.     nth0_1(N, List, Elem).
  86. nth1(Index, List, Elem) :-
  87.     var(Index),
  88.     nth0_2(N, List, Elem),
  89.     Index is N + 1.
  90.  
  91. %    last(?Elem, ?List)
  92. %    Succeeds if `Last' unifies with the last element of `List'.
  93.  
  94. last(Elem, [Elem]).
  95. last(Elem, [_|List]) :-
  96.     last(Elem, List).
  97.  
  98. %    reverse(?List1, ?List2)
  99. %    Is true when the elements of List2 are in reverse order compared to
  100. %    List1.
  101.  
  102. reverse(L1, L2) :-
  103.     $reverse(L1, [], L2).
  104.  
  105. $reverse([], List, List).
  106. $reverse([Head|List1], List2, List3) :-
  107.     $reverse(List1, [Head|List2], List3).
  108.  
  109. %    flatten(+List1, ?List2)
  110. %    Is true when Lis2 is a non nested version of List1.
  111.  
  112. flatten(List, FlatList) :-
  113.     $flatten(List, [], FlatList), !.
  114.  
  115. $flatten(Var, Tl, [Var|Tl]) :-
  116.     var(Var), !.
  117. $flatten([], Tl, Tl) :- !.
  118. $flatten([Hd|Tl], Tail, List) :-
  119.     $flatten(Hd, FlatHeadTail, List), 
  120.     $flatten(Tl, Tail, FlatHeadTail).
  121. $flatten(Atom, Tl, [Atom|Tl]).
  122.  
  123.  
  124.         /********************************
  125.         *       SET MANIPULATION        *
  126.         *********************************/
  127.  
  128. %    is_set(+Set)
  129. %    is True if Set is a proper list without duplicates.
  130.  
  131. is_set(0) :- !, fail.        % catch variables
  132. is_set([]) :- !.
  133. is_set([H|T]) :-
  134.     memberchk(H, T), !, 
  135.     fail.
  136. is_set([_|T]) :-
  137.     is_set(T).
  138.  
  139. %    list_to_set(+List, ?Set)
  140. %    is true when Set has the same element as List in the same order
  141.  
  142. list_to_set([], []).
  143. list_to_set([H|T], R) :-
  144.     memberchk(H, T), !, 
  145.     list_to_set(T, R).
  146. list_to_set([H|T], [H|R]) :-
  147.     list_to_set(T, R).
  148.  
  149. %    intersection(+Set1, +Set2, -Set3)
  150. %    Succeeds if Set3 unifies with the intersection of Set1 and Set2
  151.  
  152. intersection([], _, []) :- !.
  153. intersection([X|T], L, Intersect) :-
  154.     memberchk(X, L), !, 
  155.     Intersect = [X|R], 
  156.     intersection(T, L, R).
  157. intersection([_|T], L, R) :-
  158.     intersection(T, L, R).
  159.  
  160. %    union(+Set1, +Set2, -Set3)
  161. %    Succeeds if Set3 unifies with the union of Set1 and Set2
  162.  
  163. union([], L, L) :- !.
  164. union([H|T], L, R) :-
  165.     memberchk(H, L), !, 
  166.     union(T, L, R).
  167. union([H|T], L, [H|R]) :-
  168.     union(T, L, R).
  169.  
  170. %    subset(+SubSet, +Set)
  171. %    Succeeds if all elements of SubSet belong to Set as well.
  172.  
  173. subset([], _) :- !.
  174. subset([E|R], Set) :-
  175.     memberchk(E, Set), 
  176.     subset(R, Set).
  177.  
  178. %    subtract(+Set, +Delete, -Result)
  179. %    Delete all elements from `Set' that occur in `Delete' (a set) and
  180. %    unify the result with `Result'.
  181.  
  182. subtract([], _, []) :- !.
  183. subtract([E|T], D, R) :-
  184.     memberchk(E, D), !,
  185.     subtract(T, D, R).
  186. subtract([H|T], D, [H|R]) :-
  187.     subtract(T, D, R).
  188.