1% File : Higher_Order.PL 2% Author : Neil Smith 3% Updated: 25 January 2000 4% Purpose: Various "function" application routines based on lpa_apply/2. 5% Based on the 'applic.pl' library file from the Edinburgh Prolog libraries 6 7:- module(higher_order, 8 [ % call/2, 9 /* call/3, 10 call/4, 11 call/5, 12 call/6,*/ 13 lpa_apply/1, 14 lpa_apply/2, 15 16 identity/2, 17 complement/1, 18 complement/2, 19 every/2, 20 some/2, 21 somechk/2, 22 map/3, 23 filter/3, 24 mapfilter/3, 25 partition/4, 26 foldl/4, 27 foldl1/3, 28 foldr/4, 29 foldr1/3 ]). 30 31 32% call(X, A):- 33% X =.. XL, 34% append(XL, [A], XLA), 35% XA =.. XLA, 36% XA. 37:- if( \+ current_predicate(call/3) ). 38 39call(X, A, B):- 40 X =.. XL, 41 append(XL, [A, B], XLA), 42 XA =.. XLA, 43 . 44call(X, A, B, C):- 45 X =.. XL, 46 append(XL, [A, B, C], XLA), 47 XA =.. XLA, 48 . 49call(X, A, B, C, D):- 50 X =.. XL, 51 append(XL, [A, B, C, D], XLA), 52 XA =.. XLA, 53 . 54call(X, A, B, C, D, E):- 55 X =.. XL, 56 append(XL, [A, B, C, D, E], XLA), 57 XA =.. XLA, 58 . 59:- endif. 60 61% lpa_apply(Pred, Args) 62% is the key to this whole module. It is basically a variant of call/1 63% (see the Dec-10 Prolog V3.43 manual) where some of the arguments may 64% be already in the Pred, and the rest are passed in the list of Args. 65% Thus lpa_apply(foo, [X,Y]) is the same as call(foo(X,Y)), 66% and lpa_apply(foo(X), [Y]) is also the same as call(foo(X,Y)). 67% BEWARE: any goal given to lpa_apply is handed off to call/1, which is the 68% Prolog *interpreter*, so if you want to lpa_apply compiled predicates you 69% MUST have :- public declarations for them. The ability to pass goals 70% around with some of their (initial) arguments already filled in is 71% what makes lpa_apply/2 so useful. Don't bother compiling anything that 72% uses lpa_apply heavily, the compiler won't be able to help much. LISP 73% has the same problem. Later Prolog systems may have a simpler link 74% between compiled and interpreted code, or may fuse compilation and 75% interpretation, so lpa_apply/2 may come back into its own. At the moment, 76% lpa_apply and the routines based on it are not well thought of. 77 78:- if(\+ current_predicate(lpa_apply/1)). 79lpa_apply(Pred):- 80 lpa_apply(Pred, []). 81 82lpa_apply(Pred, Args) :- 83 ( atom(Pred) 84 -> Goal =.. [Pred|Args] 85 ; Pred = complement(Term) 86 -> Goal = complement(Term, Args) 87 ; Pred = FormalArgs ^ Term 88 -> copy_term(FormalArgs ^ Term, Args ^ Goal) 89 ; Pred =.. OldList, 90 append(OldList, Args, NewList), 91 Goal =.. NewList ), 92 !, 93 call(call,Goal). 94 95:- endif. 96 97 98% identity(Item, Item) 99% For those cases where predictes are needed, but values supplied 100 101identity(Item, Item). 102 103 104% complement(Pred) 105% succeeds if Pred fails, otherwise it fails 106 107complement(Pred):- 108 complement(Pred, []). 109 110complement(Pred, Args):- 111 ( lpa_apply(Pred, Args) 112 -> fail 113 ; true ). 114 115 116% every(List, Pred) 117% suceeds when Pred(Elem) succeeds for each Elem in the List. 118 119every([], _Pred):-!. 120every([Head|Tail], Pred) :- 121 lpa_apply(Pred, [Head]), 122 every(Tail, Pred). 123 124 125% some(List, Pred) 126% succeeds when Pred(Elem) succeeds for some Elem in List. It will 127% try all ways of proving Pred for each Elem, and will try each Elem 128% in the List. somechk/2 is to some/2 as memberchk/2 is to member/2; 129% you are more likely to want somechk with its single solution. 130 131some([Head|_], Pred) :- 132 lpa_apply(Pred, [Head]). 133some([_|Tail], Pred) :- 134 some(Tail, Pred). 135 136 137somechk([Head|_], Pred) :- 138 lpa_apply(Pred, [Head]), 139 !. 140somechk([_|Tail], Pred) :- 141 somechk(Tail, Pred). 142 143 144 145 146% map(OldList, Pred, NewList) 147% succeeds when Pred(Old,New) succeeds for each corresponding 148% Old in OldList, New in NewList. 149 150map([], _, []). 151map([X|Xs], Pred, [Y|Ys]):- 152 lpa_apply(Pred, [X, Y]), 153 map(Xs, Pred, Ys). 154 155 156% filter(List, Pred, SubList) 157% succeeds when SubList is the sub-sequence of the List containing all 158% the Elems of List for which Pred(Elem) succeeds. 159 160filter([], _Pred, []). 161filter([Head|List], Pred, SubList) :- 162 ( lpa_apply(Pred, [Head]) 163 -> SubList = [Head|Rest] 164 ; SubList = Rest ), 165 filter(List, Pred, Rest). 166 167 168% mapfilter(OldList, Rewrite, NewList) 169% is a sort of hybrid of map/3 and filter/3. 170% Each element of NewList is the image under Rewrite of some 171% element of OldList, and order is preserved, but elements of 172% OldList on which Rewrite is undefined (fails) are not represented. 173% Thus if foo(X,Y) :- integer(X), Y is X+1. 174% then 175% mapfilter([1,a,0,joe(99),101], foo, [2,1,102]). 176% 177% (could be rewritten as 178% mapfilter([1,a,0,joe(99),101], [X,Y]^(integer(X), Y is X + 1), [2,1,102]). 179% ) 180 181mapfilter([], _Pred, []). 182mapfilter([Old|Olds], Pred, NewList) :- 183 ( lpa_apply(Pred, [Old,New]) 184 -> NewList = [New|News] 185 ; NewList = News ), 186 mapfilter(Olds, Pred, News). 187 188 189% partition(Elements, Predicate, Trues, Falses) 190% Partitions a list according to Predicate. Each element of Elements 191% for which Predicate succeeds is in Trues, and in Falses otherwise. 192partition([], _Pred, [], []). 193partition([Head|List], Pred, Trues, Falses):- 194 ( lpa_apply(Pred, [Head]) 195 -> Trues = [Head|RestTrues], 196 Falses = RestFalses 197 ; Trues = RestTrues, 198 Falses = [Head|RestFalses] ), 199 partition(List, Pred, RestTrues, RestFalses). 200 201 202 203% foldl (Elements, Pred(Folded0, Element, Folded), Base, Result) 204% Folds a list of items, by combining the leftmost items first 205% Predicate is true if the Element folds into Folded0 to give Folded. 206% The first item in the list is folded into the base item 207foldl([], _, Term0, Term0). 208foldl([X|Xs], Pred, Term0, Term):- 209 lpa_apply(Pred, [Term0, X, Term1]), 210 foldl(Xs, Pred, Term1, Term). 211 212 213% foldl1 (Elements, Pred(Folded0, Element, Folded), Result) 214% Folds a non-empty list of items, by combining the leftmost items first 215% Predicate is true if the Element folds into Folded0 to give Folded. 216% The first item in the list forms the base item 217foldl1([X|Xs], Pred, Term):- 218 foldl(Xs, Pred, X, Term). 219 220 221% foldr (Elements, Pred(Element, Folded0, Folded), Base, Result) 222% Folds a list of items, by combining the rightmost items first 223% Predicate is true if the Element folds into Folded0 to give Folded. 224% The empty list folds into the base item. 225foldr([], _, Term0, Term0). 226foldr([X|Xs], Pred, Term0, Term):- 227 foldr(Xs, Pred, Term0, Term1), 228 lpa_apply(Pred, [X, Term1, Term]). 229 230% foldr (Elements, Pred(Element, Folded0, Folded), Result) 231% Folds a non-empty list of items, by combining the rightmost items first 232% Predicate is true if the Element folds into Folded0 to give Folded. 233% The last element of the list forms the base item. 234 235foldr1([X|Xs], Pred, Term):- 236 ( Xs = [] 237 -> Term = X 238 ; foldr1(Xs, Pred, Term0), 239 lpa_apply(Pred, [X, Term0, Term]) )