the guy takes a derivative of a binary tree

[juan_gandhi]

Everybody knows that a binary tree is defined by a formula T(x)=1+x*T2(x), where x is the type of the value that the tree contains.

For the beginners: A tree is either empty (=1) or a triple: (x, t1, t2) where t1 and t2 are also binary trees of the aforementioned kind.

So there. Easy. You can see that this is a quadratic equation, and that it can be represented as a cubic root on a complex plane... it's not about this; let's see how we can store changes in trees, that is, differences, that is, derivatives.

dT/dx = T2 + 2*x*T*dT/dx, whereby we have
dT/dx = T2/(1-2*x*T)

Oh, wait, you probably heard already that List(x) is defined by a formula List(x)=1+x*List(x), right? Either empty (=1) or a pair (ok, a product) (x, List(x)), right?

but this equation, List(x)=1+x*List(x) has a solution, List(x)=1/(1-x). Remember this.

Now 1/(1-2*x*T) is a list, List(2*x*T)

So dT/dx = T2 * List(2*x*T)

An update of a tree can be represented as two trees and a list of triples (bool, x, T), where T is a tree.
But what is it?

The two trees are left and right subtrees of the point-of-change; and the list of triples is the path from the root to the point of change; each element of the path being this:
- left or right
- the changed value
- the intact subtree

On this picture you see gray left, black right, and the path is red values with brown intact subtrees.



Cool eh?

Note, I did not use any particular programming language.

Source: http://www.youtube.com/watch?v=YScIPA8RbVE&noredirect=1

Comments

[rezkiy.livejournal.com]

Небольшое количество матана превращает алгебраическую муть в интересную математическую зарисовку.

[yatur.livejournal.com]

Скоро, небось, криволинейные интегралы от деревьев брать начнут. И ведь не отступятся, пока не получат фракталы какие-нибудь :)

[ivan-gandhi.livejournal.com]

HoTT вполне может привести к криволинейным интегралам.

[nivanych.livejournal.com]

"Так и до топологии недалеко!" ;-)

[bytebuster463.livejournal.com]

А вот интересно, в этом контексте какой-нибудь fold не является ли интегралом?

[ivan-gandhi.livejournal.com]

Надо подумать.

[nokachi.livejournal.com]

Что-то похожее было про домино у Кнута в Concrete Mathematics

[archaicos.livejournal.com]

> Cool eh?

Kind of.

> Note, I did not use any particular programming language.

Right. But there's a problem:

> Everybody knows that a binary tree is defined by a formula T(x)=1+x*T²(x)

Not everybody knows *that*.

[ivan-gandhi.livejournal.com]

Sure; but is not it obvious now? :)

[archaicos.livejournal.com]

Not yet, watching (just started, in fact, but I do remember you mention the list "formula" before).

[archaicos.livejournal.com]

One cannot unsee *that*!

Now, if only I knew what to do with this unconventional knowledge! :)

[os80.livejournal.com]

1. Is dT/dx an "elementary" change or it is any change?
2. Why we need intact tree to define change?

[ivan-gandhi.livejournal.com]

"Elementary"

And well... it is actually not the change that we keep, but a "hole", an opportunity for the change. You need to mutliply T' by dx to get dT :)

[os80.livejournal.com]

What is dA/dt, where A = ((1,(2,3)),((4,5),(6,7)))?
(Hmmm, is it correct question? Maybe I must say A = ((*,(*,*)),((*,*),(*,*)))? )

[os80.livejournal.com]

Surprizingly, all answers are in video :-)
"Простите меня дядя, больше не буду" :-)

[sassa-nf.livejournal.com]

This needs taking further.

{- T = 1 + X*T*T
 - dT/dx = T^2 * List(2*x*T)
 - The idea here is to show what data structure describes a change in the tree. It actually only describes a "hole" around the change
 -
 - dT = dx*T*T*List(2*x*T)
 - This is the actual change.
 -
 - Now, this latter thing describes the tree from a different perspective - instead of specifying children, it specifies children and a list of parents.
 - Clearly it is isomorphic to tree.
 -
 - If we start from a leaf node, any 1, then dx*T*T goes away, and we end up with describing just a list of parents:
 - T' = List(2*x*T)
 - T inside the list can be transformed using the same isomorphism, so we end up with:
 - T' = List(2*x*T')
 - which is basically a list of nodes along a path to root
 - which is the same as:
 - T' = 1 + (2*x*T')*T' = 1 + 2*x*T'*T'
 - If we describe the tree from leftmost leaf node, the value picked by "2" is going to be the same, so we can eliminate it, and, well, duh, we get T=1+x*T*T
 -}
data T a = N | T a (T a) (T a) deriving (Eq,Show)
data T' a = T' {unT :: [(Bool,a,T' a)]} deriving (Show)

tree = T "a" (T "b" (T "c" N N) N) (T "d" (T "e" (T "f" N N) (T "g" (T "h" N N) N)) (T "i" (T "j" N N) (T "k" N N)))

t2t' N = T' []
t2t' (T x l r) = T' $ (True, x, t2t' l) : (unT $ t2t' r) -- clearly, Bool is redundant here - we always insert True, because we construct tree by picking the leftmost leaf

t'2t (T' []) = N
t'2t (T' ((True, x, l):r)) = T x (t'2t l) $ t'2t $ T' r
t'2t (T' ((False, x, r):l)) = T x (t'2t $ T' l) $ t'2t r

main = do
  print tree
  print $ t2t' tree
  print $ t'2t $ t2t' tree

[sassa-nf.livejournal.com]

2. if you are asking about 2*x*T, then T here is "the other" subtree.

[madf.livejournal.com]

Где-то я это уже видел... Ага, вот здесь: http://blog.lab49.com/archives/3011
Правда, язык программирования там все-же использовался.

[sassa-nf.livejournal.com]

duh, d(1+x*T^2)/dx = T^2 + 2*x*T*dT/dx

(your formula misses T)

[sassa-nf.livejournal.com]

oh, you do use the right formula from then onwards.

[ivan-gandhi.livejournal.com]

10x!

[blacklion.livejournal.com]

Очень красиво.

[migmit.livejournal.com]

Ещё один интересный фактик. Будем считать, что никаких меток у нас нет, т.е., x=1. Тогда T = 1 + T2. Это уравнение вполне решается, получаются два примитивных корня шестой степени из 1. То есть, T6=1, что очевидный бред, так как утверждает, что шесть деревьев можно выбрать только одним образом.

Но вот T7=T — уже не бред. Есть хорошая биекция, работающая за O(1), между семёрками бинарных деревьев и, собственно, бинарными деревьями.

[lodin]

Where does the T(x) = 1 + x * T^2(x) notation come from?

[ivan-gandhi.livejournal.com]

From categories: it is a sum of an empty tree, which is a terminal object ("point") and a product of three types, x, T(x) and T(x) - value, left subtree, right subtree.

[anton kumaigorodskiy (from livejournal.com)]

I just can't understand how do we get from dT/dx = T^2 + 2*x*dT/dx to dT/dx = (T^2)/(1-2*x*T)
Could you please elaborate on this?

[ivan-gandhi.livejournal.com]

Oops, sorry, there was a typo

dT/dx=T^2+2*x*T*dT/dx - that's how it should look like. Fixed in the text

T'=T^2+2xTT' => T'(1-2xT)=T^2 => T'=T^2/(1-2xT).

[anton kumaigorodskiy (from livejournal.com)]

Thanks! Got it.