;;; CHICKEN Transducers - Transducers for working with foldable data types.
;;;
;;; Copyright (c) 2023 Jeremy Steward
;;;
;;; Permission is hereby granted, free of charge, to any person obtaining a copy
;;; of this software and associated documentation files (the "Software"), to deal
;;; in the Software without restriction, including without limitation the rights
;;; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
;;; copies of the Software, and to permit persons to whom the Software is
;;; furnished to do so, subject to the following conditions:
;;;
;;; The above copyright notice and this permission notice shall be included in all
;;; copies or substantial portions of the Software.
;;;
;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
;;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
;;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
;;; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
;;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
;;; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
;;; SOFTWARE.

(define-library (transducers lists)
  (import (scheme base)
          (scheme case-lambda)
          (srfi 253)
          (transducers base))

  (cond-expand
    (chicken-5
      (import (chicken type))))

  (include-library-declarations "src/transducers.lists.exports.scm")

  (begin
    ;; A helper function to get the last pair of a list
    ;;
    ;; This is used in the `collect-list` collector to get the last pair of the
    ;; sentinel (or the null list) so that we can successively set-cdr! on it
    (define-checked (last-pair (lst list?))
      (if (null? lst)
        lst
        (if (null? (cdr lst))
          lst
          (last-pair (cdr lst)))))

    ;; A reducer that aggregates the transduction into a new list in the order of
    ;; the items reduced.
    (define collect-list
      (case-lambda-checked
        (() (collect-list '()))
        (((sentinel list?))
         ;; We apply-list here because we want a copy of the input list, so
         ;; that side-effects are not observed by callers.
         (let* ((list-head (apply list sentinel))
                (new-sentinel (last-pair list-head)))
           (case-lambda
             (() new-sentinel)
             ((lst) list-head)
             ((lst x)
              (let ((new-tail (list x)))
                (if (null? lst)
                  (set! list-head new-tail)
                  (set-cdr! lst new-tail))
                new-tail)))))))

    ;; A reducer that aggregates the transduction into a list in reverse order of
    ;; the items transduced.
    (define collect-reverse-list
      (case-lambda
        (() (collect-reverse-list '()))
        ((sentinel)
         (let ((sentinel (apply list sentinel)))
           (case-lambda
             (() sentinel)
             ((lst) lst)
             ((lst x) (cons x lst)))))))

    ;; Transducer-aware folding operation on lists.
    ;;
    ;; This procedure takes in a reducer `f`, a `sentinel` value for that
    ;; reducer, and a list `xs` to call `(f sentinel x)` on repeatedly, taking
    ;; the result of the reducer as the new sentinel value each time.
    (define-checked (list-fold f sentinel (xs list?))
      (define (list-fold-inner f sentinel xs)
        (if (null? xs)
          sentinel
          (let ((x (f sentinel (car xs))))
            (if (reduced? x)
              (unwrap x)
              (list-fold-inner f x (cdr xs))))))
      (list-fold-inner f sentinel xs))

    ;; A transducer that flattens lists within a transduction
    (define-flatten-transducer flatten-list list? list-fold)

    ;; A transducer that chains a list onto a transduction
    (define-chain-transducer chain-list list-fold)

    ;; A transducer that interleaves the contents of a list
    (define-interleave-transducer
      interleave-list
      (lambda (coll) coll)
      (lambda (_ s) (null? s))
      (lambda (_ s) (car s))
      (lambda (_ s) (cdr s)))

    ;; A transducer that zips the contents of a list
    (define-zip-transducer
      zip-list
      (lambda (coll) coll)
      (lambda (_ s) (null? s))
      (lambda (_ s) (car s))
      (lambda (_ s) (cdr s)))

    ;; A transducible type-class over lists
    (define list-transducible
      (make-transducible list-fold
                         collect-list
                         flatten-list
                         chain-list
                         interleave-list
                         zip-list)))
  ;; End-of-module
  )