git.fiddlerwoaroof.com
transducers.lisp
b6f51ece
 (in-package :data-lens.transducers.beta)
1f67b287
 (declaim (inline mapping filtering deduping catting splitting
                  exit-early taking dropping transduce
                  hash-table-builder vector-builder list-builder))
b6f51ece
 
498d6599
 (defmacro define-functional-transducer (name () &body body)
   `(defun ,name (function &rest args)
      (flet ((call-function (it) (apply function it args)))
        (lambda (rf)
          (lambda (acc next)
            ,@body)))))
 
 (define-functional-transducer mapping ()
   (funcall rf acc (call-function next)))
 
 (define-functional-transducer mv-mapping ()
   (funcall rf acc (multiple-value-list (call-function next))))
 
 (define-functional-transducer mv-selecting ()
   (multiple-value-bind (value use-p) (call-function next)
     (if use-p
         (funcall rf acc value)
         acc)))
 
 (defun hash-table-select (hash-table)
   (mv-selecting #'gethash hash-table))
 
 (define-functional-transducer filtering ()
   (if (call-function next)
       (funcall rf acc next)
       acc))
 
 (defun mv-filtering (function &rest args)
   (filtering (lambda (it)
                (nth-value 1 (apply function it args)))))
b6f51ece
 
 (defun deduping (&optional (test 'eql))
   (lambda (rf)
     (let (last)
       (lambda (acc next)
         (prog1 (if (funcall test last next)
                    acc
                    (funcall rf acc next))
           (setf last next))))))
 
 (defun catting ()
   (lambda (rf)
     (lambda (acc next)
       (reduce rf next :initial-value acc))))
 
 (defun splitting (&rest functions)
   (let ((splitter (apply #'data-lens:juxt functions)))
     (mapping splitter)))
 
 (defun exit-early (acc)
   (throw 'done acc))
 
 (defun taking (n)
   (lambda (rf)
     (let ((taken 0))
       (lambda (acc next)
         (incf taken)
         (if (< taken n)
             (funcall rf acc next)
             (exit-early (funcall rf acc next)))))))
 
 (defun dropping (n)
   (lambda (rf)
     (let ((taken 0))
       (lambda (acc next)
         (if (< taken n)
             (progn (incf taken)
                    acc)
             (funcall rf acc next))))))
 
1f67b287
 (defgeneric unwrap (it obj)
   (:method (it obj) obj))
 (defgeneric init (it))
 (defgeneric stepper (it))
 
9ff7f446
 (defgeneric reduce-generic (seq func init)
1f67b287
   (:method ((seq sequence) (func function) init)
     (reduce func seq :initial-value init))
   (:method ((seq sequence) (func symbol) init)
9ff7f446
     (reduce func seq :initial-value init))
   (:method (seq (func symbol) init)
     (foldling seq (symbol-function func) init))
   (:method ((seq hash-table) (func function) init)
     (let ((acc init))
       (maphash (lambda (k v)
                  (setf acc (funcall func acc (list k v))))
                seq)
       acc)))
 
b6f51ece
 (defun transduce (xf build seq)
1f67b287
   (unwrap build
           (catch 'done
9ff7f446
             (reduce-generic seq
                             (funcall xf (stepper build))
                             (init build)))))
1f67b287
 
 (defclass lazy-sequence ()
   ((%next :initarg :next :reader next)))
cefd4fba
 (defun lazy-sequence (next)
   (make-instance 'lazy-sequence :next next))
9ff7f446
 (defmethod reduce-generic ((seq lazy-sequence) (func function) init)
1f67b287
   (let ((next (next seq)))
     (loop for next-val = (funcall next)
           for acc = init then next-acc
           for next-acc = (when next-val (funcall func acc next-val))
           while next-val
           finally (return acc))))
b6f51ece
 
 (defmacro comment (&body body)
   (declare (ignore body))
   nil)
 
1f67b287
 (defmethod stepper ((it (eql 'hash-table-builder)))
   (lambda (acc next)
     (destructuring-bind (k v) next
       (setf (gethash k acc) v))
     acc))
 (defmethod init ((it (eql 'hash-table-builder)))
   (make-hash-table))
 
 (defmethod stepper ((it (eql 'vector-builder)))
   (lambda (acc next)
     (vector-push-extend next acc)
     acc))
 (defmethod init ((it (eql 'vector-builder)))
   (make-array 0 :fill-pointer t :adjustable t))
 
 
 (defmethod init ((it (eql 'list-builder)))
   (declare (optimize (speed 3)))
   (coerce (vector nil nil)
           '(simple-array list (2))))
 (defmethod stepper ((it (eql 'list-builder)))
   (lambda (acc a)
     (declare (optimize (speed 3))
              (type (simple-array list (2)) acc))
     (if (elt acc 1)
         (let* ((to-build (elt acc 1)))
           (push a (cdr to-build))
           (setf (elt acc 1) (cdr to-build)))
         (let ((new (list a)))
           (setf (elt acc 0) new
                 (elt acc 1) new)))
     acc))
 (defmethod unwrap ((it (eql 'list-builder)) obj)
   (elt obj 0))
b6f51ece
 
 (comment
   (defun 2* (it)
     (* 2 it))
 
1f67b287
   (let ((result (transduce (alexandria:compose
                             (catting)
                             (mapping #'parse-integer)
                             (filtering (complement #'evenp))
                             (mapping (data-lens:juxt #'identity #'identity))
                             (mapping (data-lens:transform-head #'2*))
                             (mapping (data-lens:transform-head #'1+))
                             (taking 2))
b6f51ece
                            'hash-table-builder
1f67b287
                            '(("123" "234" "345" "454")
                              ("568" "490")
                              ("567" "213")))))
b6f51ece
     (values result
             (alexandria:hash-table-alist result))))