Published
Edited
Jul 30, 2020
md`# Expression 2`
Ex = {
const Ex = {};
const Form = (name, attr = {}) => {
const obj = {
name: name,
up: [],
down: [],
attr: attr
}
const fn = (...ex) => {
if(obj.attr.atom) return [obj, ...ex];
ex = ex.map( (o) => {
switch (typeof o) {
case 'string':
return Ex.Literal(o);
case 'number':
return Ex.Integer(o);
case 'function':
return Ex.Function(o);
default:
return o;
}
});
return [obj, ...ex];
}
Ex[name] = fn;
return fn;
}
const Integer = Form('Integer', {atom: true});
const Rational = Form('Rational', {atom: true});
const Literal = Form('Literal', {atom: true});
const Function = Form('Function', {atom: true});
const List = Form('List');
const Plus = Form('Plus', {flat: true, orderless: true});
const Times = Form('Times', {flat: true, orderless: true});
const Divide = Form('Divide');
const Power = Form('Power');
const Cat = Form('Cat');
const Apply = Form('Apply');
const Map = Form('Map');
const Sqrt = Form('Sqrt');
const Sequence = Form('Sequence');
const Blank = Form('Blank');
const BlankSequence = Form('BlankSequence');
const BlankNullSequence = Form('BlankNullSequence');
const LaTeX = Form('LaTeX');
const isAtom = (e) => e[0].attr.atom === true;
const same = (a, b) => a[0] === b[0];
const apply = (h, e) => e[0]=h()[0];
const equal = (a, b) => {
if(!same(a, b)) return false;
if(a.length != b.length) return false;
if(isAtom(a) && isAtom(b)) {
for(let i=1; i<a.length; ++i)
if(a[i] !== b[i]) return false;
return true;
} else if(!isAtom(a) && !isAtom(b)) {
for(let i=1; i<a.length; ++i)
if(!equal(a[i], b[i])) return false;
return true;
}
return false;
}
const match = (ex, pat, cap) => {
const matchR = (ex, pat, cap) => {
if(isAtom(pat)) return equal(ex, pat);
if(same(pat, Blank())) {
const name = pat[1] ? pat[1][1] : undefined;
const head = pat[2] ? pat[2][1] : undefined;
if(head && ex[0].name !== head) return false;
if(!name) return true;
const en = cap[name];
if(en) return equal(ex, en);
cap[name] = ex;
return true;
}
if(!same(ex, pat)) return false;
for(let i=1;i<pat.length;++i) {
if((same(pat[i], BlankNullSequence()) ||
same(pat[i], BlankSequence())) && i != pat.length-1 )
throw "BlankSequence not at last";
if(same(pat[i], BlankNullSequence()) ||
(same(pat[i], BlankSequence()) && i < ex.length )) {
const name = pat[i][1] ? pat[i][1][1] : undefined;
const head = pat[i][2] ? pat[i][2][1] : undefined;
const exr = Sequence();
for(let j=i; j<ex.length; ++j) {
exr.push(ex[j]);
if(head && ex[j][0].name !== head) return false;
}
if(!name) return true;
const en = cap[name];
if(en) return equal(exr, en);
cap[name] = exr;
return true;
}
if(i == ex.length) return false;
if(!match(ex[i], pat[i], cap)) return false;
}
if(pat.length < ex.length) return false;
return true;
}
const cap2 = {};
const r = matchR(ex, pat, cap2);
if(r) Object.assign(cap, cap2);
return r;
}
const isNumeric = (e) => (same(e, Integer()) || same(e, Rational()));
const numericValue = (e) => same(e, Rational()) ? e[1]/e[2] : e[1];
const less = (a, b) => {
if(isNumeric(a) && isNumeric(b))
return numericValue(a) < numericValue(b);
if(same(a, Literal()) && same(b, Literal()))
return a[1] < b[1];
if((same(a, Plus()) && same(b, Plus())) ||
(same(a, Times()) && same(b, Times()))) {
let m = a.length-1;
let n = b.length-1;
while(m>=1 && n>=1) {
if(equal(a[m], b[n])) {
m = m-1;
n = n-1;
} else {
return less(a[m], b[n]);
}
}
return m < n;
}
if((same(a, Power()) && same(b, Power()))) {
if(equal(a[1], b[1])) return less(a[2], b[2]);
return less(a[1], b[1]);
}
if(same(a, b)) {
let m = a.length;
let n = b.length;
let i = 1;
while(i<m && i<n) {
if(equal(a[i], b[i])) {
i = i+1;
} else return less(a[i], b[i]);
}
return m < n;
}
if(isNumeric(a) && !isNumeric(b)) return true;
else if(!isNumeric(a) && isNumeric(b)) return false;
if(same(a, Times())) return less(a, Times(b));
else if(same(b, Times())) return less(Times(a), b);
if(same(a, Power())) return less(a, Power(b, 1));
else if(same(b, Power())) return less(Power(a, 1), b);
if(same(a, Plus())) return less(a, Plus(b));
else if(same(b, Plus())) return less(Plus(a), b);
}
const Eval = (e) => {
if(isAtom(e)) return e;
let ex = [];
if(e[0].attr.holdAll) {
for(let i=1;i<e.length; ++i) ex.push(e[i]);
} else {
for(let i=1;i<e.length; ++i) {
if(i == 1 && e[0].attr.holdFirst) {
ex.push(e[i]);
} else {
ex.push(Eval(e[i]));
}
}
}
if(!e[0].attr.sequenceHold) {
let i = 0;
while(i<ex.length) {
let exi = ex[i];
if(same(exi, Sequence())) {
ex.splice(i,1);
for(let j=1; j<exi.length; ++j) ex.splice(i+j-1, 0, exi[j]);
i = i+exi.length-1;
} else i = i+1;
}
}
if(e[0].attr.flat) {
let i = 0;
while(i<ex.length) {
let exi = ex[i];
if(same(exi, e)) {
ex.splice(i,1);
for(let j=1; j<exi.length; ++j) ex.splice(i+j-1, 0, exi[j]);
i = i+exi.length-1;
} else i = i+1;
}
}
if(e[0].attr.orderless)
ex.sort((a,b) => less(a,b) ? -1 : 1);
ex.splice(0, 0, e[0]);
let tex;
for(let i=1; i<ex.length; ++i) {
let exi = ex[i];
for(let j=0; j<exi[0].up.length; ++j) {
tex = exi[0].up[j](ex);
if(tex) {
return Eval(tex);
}
}
}
for(let j=0; j<ex[0].down.length; ++j) {
tex = ex[0].down[j](ex);
if(tex) {
return Eval(tex);
}
}
return ex;
}
const addRule = (rule, fn, up) => {
let tab;
if(up) tab = up[0].up;
else tab = rule[0].down;
tab.push( (ex) => {
let cap = {}
if(match(ex, rule, cap)) return fn(cap);
return null;
});
}
const toString = (e) => {
if(same(e, Integer())) return e[1].toString();
if(same(e, Rational())) return `Rational(${e[1]}, ${e[2]})`;
if(same(e, Literal())) return "'"+e[1]+"'";
if(same(e, Function())) return '#func';
let r = e[0].name+'(';
for(let i=1; i<e.length; ++i) {
if(i!=1) r = r + ',';
r = r + toString(e[i]);
}
return r + ')';
}
const _ = (b) => {
const s = b.split('_');
switch(s.length) {
case 2:
return Blank(s[0], s[1]);
case 3:
return BlankSequence(s[0], s[2]);
case 4:
return BlankNullSequence(s[0], s[3]);
}
}
addRule(Map(_('f_Function'), _('a_')), ({f,a}) => {
for(let i=1; i<a.length; ++i) a[i] = f[1](a[i]);
return a;
});
addRule(Apply(_('f_Function'), _('a_')), ({f,a}) => {
a[0] = f[1]()[0];
return a;
});
addRule(Cat(_('l___')), ({l}) => {
let r = '';
for(let i=1; i<l.length; ++i) r = r + l[i][1];
return Literal(r);
});
addRule(Plus(), () => Integer(0));
addRule(Plus(_('a_')), ({a}) => a);
addRule(Plus(0,_('a__')), ({a}) => Plus(a));
addRule(Plus(_('a_Integer'),_('b_Integer'),_('c___')),
({a,b,c}) => Plus(a[1]+b[1], c));
const fracNorm = (num, den) => {
const g = gcd(num, den);
num = num/g; den = den/g;
if(den<0) {
num = -num;
den = -den;
}
return [num, den];
}
addRule(Divide(_('a_Integer'),_('b_Integer')),
({a,b}) => {
const [num, den] = fracNorm(a[1], b[1]);
if(den==1) return Integer(num);
else return Rational(num, den);
});
addRule(Divide(_('a_'),_('b_')),
({a,b}) => Times(a, Power(b, -1)));
addRule(Plus(_('a_Integer'),_('b_Rational'),_('c___')),
({a,b,c}) => Plus(Divide(a[1]*b[2]+b[1], b[2]), c));
addRule(Plus(_('b_Rational'),_('a_Integer'),_('c___')),
({a,b,c}) => Plus(Divide(a[1]*b[2]+b[1], b[2]), c));
addRule(Plus(_('a_Rational'),_('b_Rational'),_('c___')),
({a,b,c}) => Plus(Divide(a[1]*b[2]+b[1]*a[2], a[2]*b[2]), c));
addRule(Times(), () => Integer(1));
addRule(Times(_('a_')), ({a}) => a);
addRule(Times(1,_('a__')), ({a}) => Times(a));
addRule(Times(_('a_Integer'),_('b_Integer'),_('c___')),
({a,b,c}) => Times(a[1]*b[1], c));
addRule(Times(_('a_Integer'),_('b_Rational'),_('c___')),
({a,b,c}) => Times(Divide(a[1]*b[1], b[2]), c));
addRule(Times(_('b_Rational'),_('a_Integer'),_('c___')),
({a,b,c}) => Times(Divide(a[1]*b[1], b[2]), c));
addRule(Times(_('a_Rational'),_('b_Rational'),_('c___')),
({a,b,c}) => Times(Divide(a[1]*b[1], a[2]*b[2]), c));
addRule(Times(-1, Plus(_('a__'))),
({a}) => {
const r = Plus();
for(let i = 1; i<a.length;++i) r.push(Times(-1, a[i]));
return r;
});
const ins = (t, a, b) => {
const sa = toString(a);
if(!t[sa]) {
t[sa] = [a, Sequence(b)];
return false;
} else {
t[sa][1].push(b);
return true;
}
}
addRule(Plus(_('c__')), ({c}) => {
const r = Plus();
let flag = false;
const coefs = {};
for(let i=1; i<c.length; ++i) {
const cap = {};
if(match(c[i], Times(_('a_Integer'), _('b_')), cap))
flag = ins(coefs, cap.b, cap.a) || flag;
else if(match(c[i], Times(_('a_Integer'), _('b__')), cap))
flag = ins(coefs, cap.b, cap.a) || flag;
else if(match(c[i], Times(_('a_Rational'), _('b_')), cap))
flag = ins(coefs, cap.b, cap.a) || flag;
else if(match(c[i], Times(_('a_Rational'), _('b__')), cap))
flag = ins(coefs, cap.b, cap.a) || flag
else if(match(c[i], Times(_('b__')), cap))
flag = ins(coefs, cap.b, Integer(1)) || flag;
else
flag = ins(coefs, c[i], Integer(1)) || flag;
}
if(flag) {
for (let k in coefs) {
const v = coefs[k];
apply(Plus, v[1]);
r.push(Times(v[1], v[0]));
}
return r;
}
return null;
});
addRule(Times(_('c__')), ({c}) => {
const r = Times();
let flag = false;
const coefs = {};
for(let i=1; i<c.length; ++i) {
const cap = {};
if(match(c[i], Power(_('a_Integer'), _('b_Rational')), cap))
flag = ins(coefs, Power(cap.a, cap.b), Integer(1)) || flag;
else if(match(c[i], Power(_('a_'), _('b_')), cap))
flag = ins(coefs, cap.a, cap.b) || flag;
else
flag = ins(coefs, c[i], Integer(1)) || flag;
}
if(flag) {
for (let k in coefs) {
const v = coefs[k];
apply(Plus, v[1]);
r.push(Power(v[0], v[1]));
}
return r;
}
return null;
});
addRule(Times(_('c__')), ({c}) => {
const r = Times();
let flag = false;
const coefs = {};
for(let i=1; i<c.length; ++i) {
const cap = {};
if(match(c[i], Power(_('a_Integer'), _('b_')), cap))
flag = ins(coefs, Power(cap.a, cap.b), Integer(1)) || flag;
else if(match(c[i], Power(_('a_'), _('b_')), cap))
flag = ins(coefs, cap.a, cap.b) || flag;
else
flag = ins(coefs, c[i], Integer(1)) || flag;
}
if(flag) {
for (let k in coefs) {
const v = coefs[k];
apply(Plus, v[1]);
r.push(Power(v[0], v[1]));
}
return r;
}
return null;
});
addRule(Power(_('_'), 0), () => Integer(1));
addRule(Power(1, _('_')), () => Integer(1));
addRule(Power(_('a_'), 1), ({a}) => a);
addRule(Power(_('a_Integer'),_('b_Integer')),
({a,b}) => {
if(b[1]<0)
return Rational(1, Math.pow(a[1], -b[1]));
else
return Integer(Math.pow(a[1], b[1]));
});
addRule(Power(_('a_Rational'),_('b_Integer')),
({a,b}) => {
if(b[1]<0)
return Divide(Math.pow(a[2], -b[1]), Math.pow(a[1], -b[1]));
else
return Rational(Math.pow(a[1], b[1]), Math.pow(a[2], b[1]));
});
const rootContent = (fact, p, q) => {
let [u, v] = [1, 1];
for(let i = 0; i<fact.length; ++i) {
const fip = fact[i][1] * p;
const prime = fact[i][0];
const a = Math.floor(fip / q);
const b = fip - a * q;
u = u * Math.pow(prime, a);
v = v * Math.pow(prime, b);
}
return [u, v];
}
addRule(Power(_('a_Integer'),_('b_Rational')),
({a,b}) => {
if(a[1]<0) return null;
const fact = factorization(a[1]);
if(b[1]>0) {
const [u, v] = rootContent(fact, b[1], b[2]);
if(u==1 && b[1]==1) return null;
else return Times(u, Power(v, Rational(1, b[2])));
} else {
const b1 = -b[1];
const k = Math.floor(b1 / b[2]);
const r = b1 - k * b[2];
const [u, v] = rootContent(fact, b[2] - r, b[2]);
return Times(Divide(u, Math.pow(a[1], (k + 1))), Power(v, Rational(1, b[2])));
}
});
addRule(Power(_('a_Rational'),_('b_Rational')),
({a,b}) => Times(Power(a[1], b), Power(a[2], Rational(-b[1], b[2]))) );
addRule(Power(Power(_('a_'), _('b_')), _('c_Integer')),
({a,b,c}) => Power(a, Times(b, c)));
addRule(Power(Times(_('a__')), _('b_Integer')),
({a,b}) => {
const r = Times();
for(let i = 1; i<a.length;++i) r.push(Power(a[i], b));
return r;
});
addRule(Sqrt(_('a_')), ({a}) => Power(a, Rational(1,2)));
addRule(LaTeX(), ({a}) => Literal(''));
addRule(LaTeX(_('a_Integer')), ({a}) => Literal(`${a[1]}`));
addRule(LaTeX(_('a_Literal')), ({a}) => a);
addRule(LaTeX(_('a_Rational')), ({a}) => {
if(a[1]<0) return Literal(`-\\frac{${-a[1]}}{${a[2]}}`);
else return Literal(`\\frac{${a[1]}}{${a[2]}}`);
});
addRule(LaTeX(Plus(_('c__'))), ({c}) => {
let r = '';
for(let i=1; i<c.length; ++i) {
const s = Eval(LaTeX(c[i]))[1];
if(!s.startsWith('-') && i!=1) {
r = r + '+';
}
r = r + s;
}
return Literal(r);
});
addRule(LaTeX(Times(-1,_('c__'))), ({c}) => {
const r = '-'+Eval(LaTeX(Times(c)))[1];
return Literal(r);
});
const parenthesisPlus = (c) => {
let r = '';
for(let i=1; i<c.length; ++i) {
let s = Eval(LaTeX(c[i]))[1];
if(same(c[i], Plus())) {
s = '(' + s + ')';
}
r = r + s;
}
return r;
}
addRule(LaTeX(Times(_('a_Rational'), Power(_('b_Integer'),_('c_Rational')),_('d___'))),
({a,b,c,d}) => {
if(c[1]==1 && c[2]==2) {
let r = Eval(LaTeX(Power(b, c)))[1];
let s = parenthesisPlus(d);
//if(s==='1') s = '';
if(a[1]!=1) r = `${a[1]}` + r;
r = `\\frac{${r}}{${a[2]}}`
return Literal(r+s);
}
return null;
});
addRule(LaTeX(Times(_('c__'))), ({c}) => {
return Literal(parenthesisPlus(c));
});
addRule(LaTeX(Power(_('a_'), _('b_Rational'))), ({a,b}) => {
if(b[1]==1 && b[2]==2) {
let s = Eval(LaTeX(a))[1];
return Literal(`\\sqrt{${s}}`);
}
return null;
});
addRule(LaTeX(Power(_('a_'), _('b_'))), ({a,b}) => {
let r = '';
let s = Eval(LaTeX(a))[1];
if(!(same(a, Literal()) || same(a, Integer()))) {
s = '(' + s + ')';
}
r = r + s +'^{'+Eval(LaTeX(b))[1]+'}';
return Literal(r);
});
Ex.toString = toString;
Ex.Eval = Eval;
return Ex;
}
{
const {Eval, toString, Power, LaTeX, List, Plus, Times, Divide, Rational, Function, Cat, Apply, Map} = Ex;
return tex`${(Eval(LaTeX(Times(Power(81,Rational(1,3)),Power(12, Rational(-1,2)),Plus(1,'x'))))[1])}`;
// return toString(Eval((Times(Power(3, Rational(-1,2)),'x'))));
}
function gcd(a, b) {
return (b==0) ? a : gcd(b, a % b);
}
function factorization(n) {
const f = [];
for(let p of primes) {
let e = 0;
while (n % p == 0) {
n = (n / p);
e = e + 1;
}
if(e != 0) f.push([p, e]);
if(n == 1) break;
}
if(n == 1) return f;
else throw "Factorization fail.";
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.