In my example, I show how the predecessor-index data structure can be used
to express both depth-first and breadth-first trees. I also give examples
of doing some useful operations on trees using this structure. I don't yet
see any advantage to using ordinal fractions since I've seen no examples of
doing anything other than expressing a tree structure.
On Mon, Sep 8, 2014 at 5:48 PM, 'Bo Jacoby' via Programming <
programm...@jsoftware.com> wrote:
> DevonMcCormick's example
> C: |__n0 | |_n00 | |_n01 | |__n1 |__n10 | |__n100 |__n11 |
> |__n110 | |__n111 | |__n112 |__n12
>
> is expressed by ordinal fraction like this:
>
> 0 |__1 | |__11 | |__12 | |__2 |__21 | |__211 |__22
> | |__221 | |__222 | |__223 |__23
>
> This tree is represented by
>
> '0 1 11 12 2 21 211 22 221 222 223 23'
> or
> '000 100 110 120 200 210 211 220 221 222 223 230'
>
> Note
>
> 1. that ordinal fractions are one-origin-indexed unlike J-arrays
> that are zero-origin-indexed
>
> 2. that ordinal fractions are left-justified unlike integers that
> are right-justified
> 3. that ordinal fractions may be zeropadded to the right (23=230),
> unlike integers that may be zeropadded to the left. (23=023)
> 4. that ordinal fractions also represents general arrays using
> zero as a general wild-card character.
> 5. the ordering is alphabetic unlike Devon's which is breadth-first
>
> for your information.
>
> Bo.
>
>
>
> Den 22:55 mandag den 8. september 2014 skrev 'Pascal Jasmin' via
> Programming <programm...@jsoftware.com>:
>
>
> >
> >
> >I think that is awesome, Thomas. For those who didn't load the code, its
> much easier to use than it looks as everything is a verb, and the whole
> thing is like a mini stack language, and each operation produces intuitive
> and visible results.
> >
> >
> >
> >
> >----- Original Message -----
> >From: Thomas Costigliola <tcost...@gmail.com>
> >To: J Programming Forum <programm...@jsoftware.com>
> >Cc:
> >Sent: Monday, September 8, 2014 4:04 PM
> >Subject: Re: [Jprogramming] Ragged Array Shapes are Trees
> >
> >Array representations and "pointer" representations of trees both have
> >their uses. In the end it depends on what problem you are trying to solve.
> >As Devon demonstrated, for his purpose, array representation was not a
> >hindrance at all. But, as Dan mentions, trees are also used to implement
> >abstract data structures with certain run-time properties where finding
> the
> >children of a node or inserting / moving sub-trees in less than constant
> >time is not acceptable. J already can do the "pointer" representation with
> >boxed arrays but as stated by others previously, there are insufficient
> >primitives for working with them conveniently without additional overhead.
> >
> >I have played around with code similar to Pascal's for working with trees.
> >I felt, however, this type of stuff has limited usefulness in production
> >code without help from the interpreter to optimize it. It's the same idea
> >as a "zipper" data structure in other languages. Here is a bare bones
> >implementation with lots of room for more bells and whistles if desired.
> >
> >x=. @ [
> >
> >y=. @ ]
> >
> >focus=. (3&{::) y
> >
> >addrs=. (2&{::) y
> >
> >crumbs=. (1&{::) y
> >
> >stack=. (0&{::) y
> >
> >
> >zip=. '';'';'';<
> >
> >unzip=. focus @: (zout ^: (#@crumbs))
> >
> >
> >zin=. (stack) ; (crumbs , <@focus) ; (addrs , <x) ; <@([ {:: focus)
> >
> >zout=. (stack) ; (}:@crumbs) ; (}:@addrs) ; <@(0 (([:*@L. _1{::crumbs)
> ><y^:[ focus)`(_1{::addrs)`(_1{::crumbs)} ])
> >
> >zam=. <x 3} ] NB. amend
> >
> >zap=. (@ focus)(<@:)(`((3})`]))(`:6) NB. apply
> >
> >zpush=. (stack , <@focus) ; (crumbs) ; (addrs) ; (<@focus) NB. push focus
> >in temp stack
> >
> >zpop=. (}:@stack) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. pop from temp
> >stack
> >
> >zswap=. (}:@stack,<@focus) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. swap
> >focus and top of temp stack
> >
> >
> >]T=. (i.3 3);(11;22;<(_1;i.5));(<'AAA';<'BBB';'CCC')
> >
> >┌─────┬──────────────────────┬───────────────┐
> >
> >│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
> >
> >│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
> >
> >│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC│││
> >
> >│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
> >
> >│ │└──┴──┴──────────────┘│└───┴─────────┘│
> >
> >└─────┴──────────────────────┴───────────────┘
> >
> >NB. zip tree
> >
> >zip T
> >
> >┌┬┬┬──────────────────────────────────────────────┐
> >
> >││││┌─────┬──────────────────────┬───────────────┐│
> >
> >│││││0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐││
> >
> >│││││3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐│││
> >
> >│││││6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC││││
> >
> >│││││ ││ │ │└──┴─────────┘│││ │└───┴───┘│││
> >
> >│││││ │└──┴──┴──────────────┘│└───┴─────────┘││
> >
> >││││└─────┴──────────────────────┴───────────────┘│
> >
> >└┴┴┴──────────────────────────────────────────────┘
> >
> >NB. Change 'CCC' to 'DDD'
> >
> >unzip 'DDD' zam _1 zin _1 zin _1 zin zip T
> >
> >┌─────┬──────────────────────┬───────────────┐
> >
> >│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
> >
> >│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
> >
> >│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│DDD│││
> >
> >│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
> >
> >│ │└──┴──┴──────────────┘│└───┴─────────┘│
> >
> >└─────┴──────────────────────┴───────────────┘
> >
> >NB. Copy the third sub-tree down into the second
> >
> >unzip zpop _1 zin (,&a:) zap 2 zin 1 zin zout zpush 2 zin zip T
> >
> >┌─────┬──────────────────────────────────────┬───────────────┐
> >
> >│0 1 2│┌──┬──┬──────────────────────────────┐│┌───┬─────────┐│
> >
> >│3 4 5││11│22│┌──┬─────────┬───────────────┐│││AAA│┌───┬───┐││
> >
> >│6 7 8││ │ ││_1│0 1 2 3 4│┌───┬─────────┐││││ ││BBB│CCC│││
> >
> >│ ││ │ ││ │ ││AAA│┌───┬───┐│││││ │└───┴───┘││
> >
> >│ ││ │ ││ │ ││ ││BBB│CCC│││││└───┴─────────┘│
> >
> >│ ││ │ ││ │ ││ │└───┴───┘││││ │
> >
> >│ ││ │ ││ │ │└───┴─────────┘│││ │
> >
> >│ ││ │ │└──┴─────────┴───────────────┘││ │
> >
> >│ │└──┴──┴──────────────────────────────┘│ │
> >
> >└─────┴──────────────────────────────────────┴───────────────┘
> >
> >NB. This time swap the sub-trees in the previous example
> >
> >unzip zpop 2 zin zout zout zswap 2 zin 1 zin zout zpush 2 zin zip T
> >
> >┌─────┬───────────────────────┬──────────────┐
> >
> >│0 1 2│┌──┬──┬───────────────┐│┌──┬─────────┐│
> >
> >│3 4 5││11│22│┌───┬─────────┐│││_1│0 1 2 3 4││
> >
> >│6 7 8││ │ ││AAA│┌───┬───┐│││└──┴─────────┘│
> >
> >│ ││ │ ││ ││BBB│CCC││││ │
> >
> >│ ││ │ ││ │└───┴───┘│││ │
> >
> >│ ││ │ │└───┴─────────┘││ │
> >
> >│ │└──┴──┴───────────────┘│ │
> >
> >└─────┴───────────────────────┴──────────────┘
> >
> >
> >On Mon, Sep 8, 2014 at 3:45 PM, Devon McCormick <devon...@gmail.com>
> wrote:
> >
> >> A little research clarified what we see here: apparently it's part of
> the
> >> definition of a binary tree that the left node be smaller than its
> parent
> >> but the right one is greater. Right away, I see a problem for the
> >> predecessor-index representation of a tree that I'm advocating as it
> does
> >> not distinguish between right and left nodes as it is usually
> implemented.
> >>
> >>
> >> On Mon, Sep 8, 2014 at 3:03 PM, Devon McCormick <devon...@gmail.com>
> >> wrote:
> >>
> >> > Do you have a reference to a good example of this? Looking at the
> >> > "before" and "after" pictures on the right here -
> >> > http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree - the
> >> > rebalancing seems arbitrary as it preserves some relations but changes
> >> > others.
> >> >
> >> >
> >> > On Mon, Sep 8, 2014 at 2:30 PM, Dan Bron <j...@bron.us> wrote:
> >> >
> >> >> Raul wrote:
> >> >> > Note that J already supports trees.
> >> >>
> >> >> Devon wrote:
> >> >> > I have J code that uses trees which I run daily and
> >> >> > have been doing so for years.
> >> >>
> >> >> Pascal wrote:
> >> >> > I think trees are done at least ok, if not "right" already.
> >> >>
> >> >> Challenge: express, in J, the logic of rebalancing a heap (say, a
> >> >> Fibonacci
> >> >> heap, but I'm not particularly picky).
> >> >>
> >> >> For the sake of this exercise, you may ignore considerations of
> >> efficiency
> >> >> (though that's a bit of a self-contradiction, because heaps are
> >> frequently
> >> >> introduced specifically for the sake of efficiency). I am only
> >> interested
> >> >> in the directness, simplicity, elegance (lyricality) of the
> notation, in
> >> >> its current form, for expressing ideas about trees. We can make it
> >> >> efficient "later" (Pepe's TCO utility is a start).
> >> >>
> >> >> -Dan
> >> >>
> >> >>
> >> >>
> >> >>
> ----------------------------------------------------------------------
> >> >> For information about J forums see
> http://www.jsoftware.com/forums.htm
> >> >>
> >> >
> >> >
> >> >
> >> > --
> >> > Devon McCormick, CFA
> >> >
> >> >
> >>
> >>
> >> --
> >> Devon McCormick, CFA
> >
> >
> >
> >
> >> ----------------------------------------------------------------------
> >> For information about J forums see http://www.jsoftware.com/forums.htm
> >>
> >----------------------------------------------------------------------
> >For information about J forums see http://www.jsoftware.com/forums.htm
> >----------------------------------------------------------------------
> >For information about J forums see http://www.jsoftware.com/forums.htm
> >
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
Devon McCormick, CFA
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
