home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / LIB / LISTS.LF < prev    next >
Text File  |  1996-06-04  |  3KB  |  111 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %    $Id: lists.lf,v 1.2 1994/12/08 23:58:25 duchier Exp $    
  3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  4. %
  5. % List manipulation
  6. %
  7. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  8. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  9.  
  10. import("sets") ?
  11.  
  12. module("lists") ?
  13.  
  14. add_man(lists,
  15.      " module(""lists"").
  16.  
  17.   This module contains a number of utilities for list manipulation.
  18.  
  19.   It imports the 'sets' library, and adds a few more utilities:
  20.  
  21.   sort_remove_all, ad_remove_all,
  22.  
  23.   and a generic quicksort function:
  24.  
  25.      gen_quicksort.")?
  26.  
  27. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  28. %%%
  29. %%% generic operations on lists; the method feature describes the function used
  30. %%% to method for equality.
  31. %%%
  32. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  33.  
  34. add_man(sort_remove_all,
  35.      " sort_remove_all(Sort,List) -> List2
  36.  
  37.   input: Sort: sort. 
  38.          List: a list of terms.
  39.   output: List2: a list.
  40.  
  41.   List2 is List1 with no element of sort Sort")?
  42.  
  43. public(sort_remove_all) ? 
  44. sort_remove_all(A,[B|C]) ->
  45.     cond( A :== B,
  46.           sort_remove_all(A,C),
  47.           [B|sort_remove_all(A,C)]
  48.         ).
  49. sort_remove_all(_,[]) -> [].
  50.  
  51.  
  52. add_man(ad_remove_all,
  53.      " ad_remove_all(Elt,List) -> List2
  54.  
  55.   input: Elt: any psi term. 
  56.          List: a list of terms.
  57.   output: List2: a list.
  58.  
  59.   List2 is List1 with no element unified with Elt")?
  60.  
  61.  
  62. public(ad_remove_all) ? 
  63. ad_remove_all(A,[B|C]) ->
  64.     cond( A === B,
  65.           ad_remove_all(A,C),
  66.           [B|ad_remove_all(A,C)]
  67.         ).
  68. ad_remove_all(_,[]) -> [].
  69.  
  70. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  71. %%%
  72. %%% quicksort
  73. %%%
  74. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  75.  
  76. add_man(gen_quicksort,
  77.      " gen_quicksort(List,order => Order) -> List2.
  78.  
  79.   input: List: a list of elements.
  80.          Order: an order on these elements (a boolean function).
  81.   output: List2: a list.
  82.  
  83.   List2 is the ordered version of List1.")?
  84.  
  85. public(gen_quicksort)?
  86.  
  87. gen_quicksort(List,order => Order) -> gen_dqsort(List,[],order => Order).
  88.  
  89.  
  90. % Difference list version
  91. gen_dqsort([Pivot|Rest],End,order => Order) -> L |
  92.     gen_split(Pivot,Rest,Less,More,order => Order),
  93.     L = gen_dqsort(Less,
  94.                [Pivot|gen_dqsort(More,End,order => Order)],
  95.                order => Order).
  96. gen_dqsort([],End) -> End.
  97.  
  98.  
  99. % split a list at pivot value
  100. gen_split(X,[H|T],R,More,order => Order) :-
  101.     Order(H,X),!,
  102.     R=[H|Less],
  103.     gen_split(X,T,Less,More,order => Order).
  104. gen_split(X,[H|T],Less,R,order => Order) :-
  105.     !,
  106.     R=[H|More],
  107.     gen_split(X,T,Less,More,order => Order).
  108. gen_split(@,[],[],[]).
  109.  
  110.  
  111.