an experiment with join lists

join-list.rkt

#lang racket/base


;; A JL is either a list, or a join-list
(struct join-list (x ;; JL
                   y ;; JL
                   size
                   ))

(define threshold 50)

(define (size jl)
  (cond [(join-list? jl)
         (join-list-size jl)]
        [else
         (length jl)]))

;; join: JL JL -> JL
(define (join jl-1 jl-2)
  (cond
    [(eq? jl-1 '())
     jl-2]
    [(eq? jl-2 '())
     jl-1]
    [else
     (define new-size (+ (size jl-1) (size jl-2)))
     (cond [(< new-size threshold)
            (append (join-flatten jl-1)
                    (join-flatten jl-2))]
           [else
            (join-list jl-1 jl-2 new-size)])]))


;; join-flatten: jl -> list
(define (join-flatten jl)
  (cond [(join-list? jl)
         (let loop ([jl jl]
                    [acc '()])
           (cond
             [(list? jl)
              (append jl acc)]
             [(join-list? jl)
              (loop (join-list-x jl) (loop (join-list-y jl) acc))]))]
        [else
         jl]))


(let ([join         join         #;append]
      [join-flatten join-flatten #;values])
  (time (void (join-flatten (for/fold ([jl '()]) ([i (in-range 20)])
                              (join jl (join (list i) jl))))))
  
  (time (void (join-flatten (for/fold ([jl '()]) ([i (in-range 10000)])
                              (join jl (list i))))))
  
  )