← Home

Efficient Transfinite Lists

A list whose places are ordinals. put(n) pushes everything n places along and get(n) drops the first n, so after put(ω) the list starts again past every natural number. It's built from pairs, and get(n) just follows n's own parentheses: ( goes left, ) goes right. That takes as many steps as n has parentheses, however many places stand in the way. From the post Efficient Transfinite Lists

Places

The hollow nodes, counted from the head. Tap one to get it.

    Differences

    The post's naive list: the gaps between places, which get would walk one by one.

    put(n)

    Builds n's path in front of the head (orange), following the same path through the old list (bold). Where it goes right it copies the old path's left edge (gold).

      get(n)

      Follows n's path from the head (green). Ask for something that isn't a place, like get(1) before an ω, and it falls off.

        Lists to start from

        The post's code

        From asvarga/tf-lists ↗, in Racket, where a list is a pair or '(). l and r give a pair's left and right, or '(). The gold line is the copy. This page runs a port of it, and puts any ordinal by putting its powers, last first.

        (define (get ord L)
          (define (get path L) (match path
            [(cons #\( rst) (get rst (l L))]
            [(cons #\) rst) (get rst (r L))]
            [_ L]))
          (get (o2p ord) L))
        
        (define (put ord L)   ; ord = ω^a
          (define (put path M) (match path
            [(cons #\( rst) (cons (put rst (l M)) '())]
            [(cons #\) rst) (cons (l M) (put rst (r M)))]
            [_ L]))
          (put (o2p ord) L))

        The post had no proof that it works. This page's tests check it against the naive list on random puts and gets: every place is found, and nothing else is.

        Hollow nodes are places, where values would go; the head is ringed. Filled nodes are pairs that join them. Each place's path runs up and back down to the ground, ( up to the left child and ) down to the right. Gold arcs are copied left edges, the shortcuts. Keys: U undoes. The URL keeps your steps.