[Maxima-discuss] Assigning positions to an expression's parts

[Pankaj S. <pan...@gm...>]

Hi,
Recently there was discussion regarding assigning position to list elements
but that method wasn't for expressions.

I have written some new methods that shall address this problem,
_______________________________
load(basic);
/*------------*/
call_expr_tree(lis):=block([final:[],temp:[],count:0,curr_exp],expr_tree(lis),
final:map(lambda([x],[cons(first(x[1]),last(x[1])),last(x)]),final),finalize_list(final))$
/*------------*/
expr_tree(lis):=block([oper],if(atom(lis)=false) then
(oper:op(lis),push([[oper,args(lis)],curr_exp],final),(for i:1 thru
length(args(lis))
do (curr_exp:args(lis)[i],
expr_tree(args(lis)[i]))))else lis)$
/*------------*/
finalize_list(tt):=block(for item:1 thru length(tt) do ( for i:1 thru
length(tt) do
(for j:1 thru length(first(tt[i])) do
(if(last(tt[item])=first(tt[i])[j]) then
first(tt[i])[j]:tt[item][1]))),
first(last(tt)))$
/*------------*/
%in:      call_expr_tree(a^2+b^3+c^4);
%out:    ["+",["^",c,4],["^",b,3],["^",a,2]]
/*------------*/
%in: tt:call_expr_tree((z+y+k+ll)^4+a^2+b^3+c^4+sin(s+f));
%out: ["+",["^",["+",z,y,ll,k],4],[sin,["+",s,f]],["^",c,4],["^",b,3],["^",a,2]]
________________________________
This shall give a expression tree sort of output. I tried searching a lot
but there is no example I could find that could tell how trees are
represented in functional languages, though there are plenty of examples
for c/java etc. So, I tried this approach.
In case someone knows how trees are implemented in functional languages,
please share some link/details.
__________________________________
/*These methods were discussed earlier but I am keeping it here to prevent
the effort of re-search(in case one tries). It also has a subtle difference
than earlier usage */
/*------------*/
assign_positions(lis):=block([ltemp2:[],count:-1],for item in lis do
if(listp(item)) then
(push([assign_positions(item),
[count:count+1]],ltemp2))
else (push([item,[count:count+1]],ltemp2))
,reverse(ltemp2))$
/*------------*/
call_from_inside(lis):=block([olast:[],temp:0,final:[]],olast:from_inside(lis),reverse(final))$
/*------------*/
from_inside(lis):=block([count:0],for item in lis do
 (if(atom(first(item))) then
(if(olast=[]) then (push(item,final))
 else (push([first(item),
flatten(endcons(last(item),reverse(olast)))
],final))) else (push(last(item),olast),
from_inside(first(item)),pop(olast))))$
​/*------------*/
​%in:  call_from_inside(assign_positions(tt));
%out:
[["+",[0]],["^",[1,0]],["+",[1,1,0]],[z,[1,1,1]],[y,[1,1,2]],[ll,[1,1,3]],[k,[1,1,4]],[4,[1,2]],[sin,[2,0]],["+",[2,1,0]
],[s,[2,1,1]],[f,[2,1,2]],["^",[3,0]],[c,[3,1]],[4,[3,2]],["^",[4,0]],[b,[4,1]],[3,[4,2]],["^",[5,0]],[a,[5,1]],[2,[5,2]]]​

/* To see if it rhymes with "part" addressing,
expr:(z+y+k+ll)^4+a^2+b^3+c^4+sin(s+f);
part(expr,2,1,2); => f
part(expr,2,1,0); => +
___________________________________
Which shows that results are consistent. Here addressing it upto leaf
level, so a user can easily make out what's maximum address available to be
used. The output is "depth-first" and it shouldn't be difficult to read it
"breadth-first" too based on positions. It can also help find other stats
on tree say depth,size etc.

Here count for assignment is from "0" because of operators enlisted in
lists while in case of simple lists discussed earlier it is from 1 as "["
need not be enlisted separately.
_____________________________________
/* Collecting subtrees from main tree */

call_collect_subtrees(lis):=block([temp:[]],collect_subtrees(lis),push(lis,temp))$
/*------------*/
collect_subtrees(lis):=block(for item in lis do if(listp(item)) then
(push(item,temp),collect_subtrees(item)) else push(item,temp))$
/*------------*/
%in:: call_collect_subtrees(tt);
%out::
[["+",["^",["+",z,y,ll,k],4],[sin,["+",s,f]],["^",c,4],["^",b,3],["^",a,2]],2,a,"^",["^",a,2],3,b,"^",["^",b,3],4,c,"^",["^",c,4],f,s,"+",["+",
s,f],sin,[sin,["+",s,f]],4,k,ll,y,z,"+",["+",z,y,ll,k],"^",["^",["+",z,y,ll,k],4],"+"]

/* This will help in checking tree membership and specially if someone
implements pattern sort of functionality no need to recurse through tree
every time.
______________________________________
/*After someone has made some changes to the list, there is need to
regenerate the expression */

call_create_exp(lis):=block([count:0,prev:[],tt1:lis,n_tt1],prev:tt1,
create_expr_outwards(tt1),
while(prev#tt1) do (prev:tt1,create_expr_outwards(tt1)),tt1)$
/*---------*/
create_expr_outwards(lis):=block([],
if(listp(lis) and sublist(lis,listp)=[])
then
tt1:subst(apply(first(lis),rest(lis)),lis,tt1) else (for item in lis do
if(listp(item))then
(create_expr_outwards(item))))$
/*---------*/
%in :: f1:call_expr_tree(sin(x+y)*'integrate(x,x))
%out:: ["*",[integrate,x,x],[sin,["+",y,x]]]

%in:: subst(call_expr_tree(cos(w+d+diff(tan(x),x))),call_expr_tree(y+x),f1);
%out:: ["*",[integrate,x,x],[sin,[cos,["+",["^",[sec,x],2],w,d]]]]

%in:: call_create_exp(%);
%out:: integrate(x,x)*sin(cos(sec(x)^2+w+d))
___________________________________________
I have been suggested at times to write in lisp but I find it problematic
to add appropriate headers at places in lisp code to make it compatible to
Maxima though I am trying.

Please try these once and suggest improvements. I find these useful, can we
use them in share with more modifications/additions needed? There could be
an experimental code in share that users can contribute to and others can
use at their own risk :P and suggest modifications !.


--
​-----​

Regards,
Pankaj Sejwal
________________________________________
"The more I read, the more I acquire, the more certain I am that I know
nothing.” - Voltaire