(use-modules (srfi srfi-41))
(use-modules (ice-9 match))
(use-modules (srfi srfi-9))  ;; records
(use-modules (srfi srfi-9 gnu))  ;; set-record-type-printer! and set-field


(define (list->traversi lst)
  (let loop ((lst lst))
    (lambda ()
      (if (null? lst)
          '()
          (cons (cons (car lst) '()) (loop (cdr lst)))))))

(define (traversi->list traversi)
  (let loop ((traversi traversi)
             (out '()))
    (match (traversi)
      ('() (reverse out))
      ((item . next) (loop next (cons (car item) out))))))

(define (traversi-map proc traversi)
  (let loop ((traversi traversi))
    (lambda ()
      (match (traversi)
        ('() '())
        ((item . next) (cons (cons (proc (car item)) item) (loop next)))))))

(define (traversi-filter proc traversi)
  (let loop1 ((traversi traversi))
    (lambda ()
      (let loop2 ((traversi traversi))
        (match (traversi)
          ('() '())
          ((item . next) (if (proc (car item))
                             (cons item (loop1 next))
                             (loop2 next))))))))

(define (traversi-parent traversi)
  (let loop ((traversi traversi))
    (lambda ()
      (match (traversi)
        ('() '())
        ((item . next)
         (let ((parents (cdr item)))
           (if (null? parents)
               (throw 'traversi "item has no parent")
               (cons parents (loop next)))))))))

(define-syntax-rule (timeit body ...)
  (let ((start (current-time)))
    (begin body ...)
    (- (current-time) start)))

(define count 10000000)

(pk (timeit (traversi->list (traversi-filter odd? (traversi-map (lambda (x) (* 3 x)) (list->traversi (iota count)))))))

(pk (timeit (stream->list (stream-filter odd? (stream-map (lambda (x) (* 3 x)) (list->stream (iota count)))))))