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