| 123456789101112131415161718192021222324252627282930313233343536 |
- #import std
- #import nat
- #import sol
- #comment -[
- This module contains some functions for counting with trees according
- to one possible enumeration (the fastest I can think of). There is a
- one to one correspondence between trees and natural numbers, but
- sometimes smallish trees can have extremely large ordinals. I'm not
- convinced dendriform always works (the inverse of the ordinal
- function) but have never found a counterexample.
- Copyright (C) 2007 Dennis Furey]-
- #library+
- #optimize+
- # tsuc = ~&a^?\~&aaX ~&ar?\~&NfalPRX ^/~&falPR ~&farPJ; ~&aal2fafalPJPRafarPRPXaar2fafarPJPRNXBq
- #fix function_fixer
- tsuc = ~&?\&! ~&r?/^(tsuc+~&l,tpred+~&r) ~&/0+ tsuc+ ~&l
- tpred = &?=/0! ~&l?/^(tpred+~&l,tsuc+~&r) ~&\0+ tpred+ ~&r
- ordinal = # returns the position any tree would have in the above series
- ~&a^& ~&W; ^(sum,~&l); successor+ sum^\~&r ~&l; half+ product^/~& successor
- dendriform = # returns the tree given the ordinal; uses newton's method to solve a quadratic recurrence
- ~&a^?\0! ^W/~&f predecessor+~&a; -+
- ^(~&r,nat-difference)+ ^/~&rl nat-difference+~&lrrPX,
- ^/~& ^(~&,half+ product^/~& successor)+ {0,1}?</~& ^H\(skip^\~& predecessor+ half+ length) -+
- predecessor++ ^=+ nat-difference^/~&+ quotient+,
- ^\successor+double+ nat-difference^/(product^/successor ~&)+ !+ double+-+-
|
