1:- module(flat). 2 3:- local flatten/2. 4 5:- export 6 7 binary_to_list/4, 8 binary_to_list/5, 9 list_to_binary/3, 10 list_to_binary/4, 11 12 and_to_list/2, 13 list_to_and/2, 14 or_to_list/2, 15 list_to_or/2, 16 plus_to_list/2, 17 list_to_plus/2, 18 times_to_list/2, 19 list_to_times/2. 20 21 22% File : FLAT.PL 23% Author : R.A.O'Keefe 24% Updated: 5 April 1984 25% Converted for NIP: Ken Johnson, 1-6-87 26% Purpose: Flatten various binary trees to lists and convert back. 27 28/* This file was originally for PRESS, where you often want to take 29 a tree such as 1+x+0+(u*v+9)+(x^2+2) and flatten it to a list 30 such as [1,x,u*v,9,x^2,2] so that you can easily pick out all the 31 constants or all the terms involving x or something, without having 32 to write N different sets of predicates to handle N different 33 binary operators. It can be useful for other things as well. 34 35 The <operator>_to_list predicates take a binary tree (where leaf 36 nodes are anything not labelled by the operator) and flatten it 37 to a list. They also omit "units" of that operator, that is, if 38 the operator is & {| + *} the constant true {false 0 1} will not 39 appear in the list. The predicate 40 binary_to_list(Tree, Operator, Unit, Before, After) 41 enables you to make your own versions. Note that the answer is 42 accumulated in the differnce Before-After. 43 binary_to_list(Tree, Operator, Before, After) 44 lets you convert trees where the operator has no unit. 45 46 The well known and not often useful predicate "flatten" is a not 47 very interesting special case of binary_to_list/5. 48 49 The list_to_<operator> predicates take a list and turn it back 50 into a tree. Now there is an interesting question here: is 51 [a,b,c] to be turned into f(a,f(b,c)) or into f(f(a,b),c)? The 52 former is a good idea for & | and '.', while the latter is a 53 good idea for + and *. My solution was to have the top-level 54 predicate check whether the Operator is a yfx operator (such as 55 + and * are) and if so to generate f(f(a,b),c). In all other 56 cases (xfy,xfx, or no operator declaration) f(a,f(b,c)) is 57 generated. 58 list_to_binary(List, Operator, Unit, Tree) 59 lets you make your own versions. If the list is [] the Unit will 60 be returned, that is the only use of the Unit. 61 list_to_binary(List, Operator, Tree) 62 should be used when the Operator has no Unit, if given an empty 63 list it will fail. 64*/ 65 66% Example 1 67% binary_to_list(1+2+3,Op,B,A) 68% sets 69% Op = + 70% B = [1,2,3|_1] 71% A = _1 72 73% Example 2 74% list_to_binary([1,2,3],+,A) and list_to_binary([1,2,3|_],+,A) 75% both set 76% A = 1+2+3 77 78and_to_list(Conjunction, List) :- 79 binary_to_list(Conjunction, &, true, List, []). 80 81 82list_to_and(List, Conjunction) :- 83 list_to_binary(List, &, true, Conjunction). 84 85 86 87or_to_list(Disjunction, List) :- 88 binary_to_list(Disjunction, (';'), false, List, []). 89 90 91list_to_or(List, Disjunction) :- 92 list_to_binary(List, (';'), false, Disjunction). 93 94 95 96plus_to_list(Sum, List) :- 97 binary_to_list(Sum, +, 0, List, []). 98 99 100list_to_plus(List, Sum) :- 101 list_to_binary(List, +, 0, Sum). 102 103 104 105times_to_list(Product, List) :- 106 binary_to_list(Product, *, 1, List, []). 107 108 109list_to_times(List, Product) :- 110 list_to_binary(List, *, 1, Product). 111 112 113 114flatten(List, Flat) :- 115 binary_to_list(List, ., [], Flat, []). 116 117 118 119binary_to_list(Unit, _, Unit, List, List) :- !. 120binary_to_list(Term, Operator, Unit, Before, After) :- 121 Term =.. [Operator,Lhs,Rhs], % Term can't be a variable 122 !, 123 binary_to_list(Lhs, Operator, Unit, Before, Middle), 124 binary_to_list(Rhs, Operator, Unit, Middle, After). 125binary_to_list(Term, _, _, [Term|After], After). 126 127 128binary_to_list(Term, Operator, Before, After) :- 129 nonvar(Term), 130 Term =.. [Operator,Lhs,Rhs], 131 !, 132 binary_to_list(Lhs, Operator, Before, Middle), 133 binary_to_list(Rhs, Operator, Middle, After). 134binary_to_list(Term, _, [Term|After], After). 135 136 137 138list_to_binary([], _, Unit, Unit) :- !. 139list_to_binary([Head|Tail], Operator, _, Answer) :- 140 current_op(_, yfx, Operator), 141 !, 142 list_to_binaryL(Tail, Operator, Head, Answer). 143list_to_binary(List, Operator, _, Answer) :- 144 list_to_binaryR(List, Operator, Answer). 145 146 147list_to_binary([Head|Tail], Operator, Answer) :- 148 current_op(_, yfx, Operator), 149 !, 150 list_to_binaryL(Tail, Operator, Head, Answer). 151list_to_binary(List, Operator, Answer) :- 152 list_to_binaryR(List, Operator, Answer). 153 154 155list_to_binaryL([], _, Answer, Answer) :- !. 156list_to_binaryL([Head|Tail], Operator, Sofar, Answer) :- 157 Next =.. [Operator,Sofar,Head], 158 list_to_binaryL(Tail, Operator, Next, Answer). 159 160 161list_to_binaryR([Term], _, Term) :- !. 162list_to_binaryR([Head|Tail], Operator, Answer) :- 163 Answer =.. [Operator,Head,Rest], !, 164 list_to_binaryR(Tail, Operator, Rest). 165 166 167