_carry.md

Carry

Frequently I want to use reductions only to quickly realize that I'm not interested in the successive values of the state.

A simple example is to imagine one wants to increment a number represented by a sequence of its binary digits:

(inc '()) is (1)
(inc '(1)) is (0 1) ; yes the list is inversed, the lowest significant bit is the first item
(inc '(0 1)) is (1 1)

The essence of the computation is simple, this is this function:

(fn [c d] ; c for carry, d for digit
  ; returns [new-carry incremented-digit]
  (case [c d]
    [1 1] [1 0]
    [0 0] [0 0]
    [0 1])) ; all remaining cases

Not captured by this function is the fact that at the end of the number we want to "flush" the carry: append one more item if the carry is one.

Go ahead, try and implement increment with reductions! I would be delighted to see an elegant solution.

So, this is a iteration pattern that I have struggled with on numerous occasions, hence I propose the below carry function to express it.

(defn inc-digit
  ([] 1)
  ([c] (case c 1 [1] nil))
  ([c d]
    (case [c d]
      [1 1] [1 0]
      [0 0] [0 0] 
      [0 1])))

=> (take 10 (iterate #(carry inc-digit %) ()))
(() (1) (0 1) (1 1) (0 0 1) (1 0 1) (0 1 1) (1 1 1) (0 0 0 1) (1 0 0 1))

Have you already encountered this pattern too? Does it have a name? Am I oblivious to a simpler expression?

carry.clj

(defn carry
  "Takes a function `f` of two arguments (state and item), a collection and
   an optional initial state `init` (else `(f)` is used as `init`).
   `(f state x)` must return a sequential collection whose first item is the
   new state and subsequent items are appended to the output sequence.
   When the input collection is done being processed, the value of `(f state)`
   is appended to the output sequence.
   Returns a lazy sequence."
  ([f coll]
    (lazy-seq (carry f (f) coll)))
  ([f init coll]
    (letfn [(step [state s]
              (lazy-seq
                (if-some [[x] (seq s)]
                  (let [[state & outs] (f state x)]
                    (concat outs (step state (rest s))))
                  (f state))))]
      (step init coll))))

I'm surprised you didn't mention transducers. inc-digit is a stateful process producing an arbitrary number of output values when it's fed with an input value, so my knee-jerk reaction would be to write a transducer here :

(defn inc-digit-xf [rf]
  (let [state (doto (object-array 1) (aset 0 1))]
    (fn
      ([]
       (rf))
      ([r]
       (rf (case (aget state 0)
             1 (rf r 1) r)))
      ([r d]
       (let [c (aget state 0)]
         (aset state 0 (if (= 1 c d) 1 0))
         (rf r (if (= c d) 0 1)))))))

And then carry would be sequence :

(sequence inc-digit-xf [0 0 1])
#_=> (1 0 1)

IMO what you have here is an alternative representation of transducers, a purely functional one where state is made explicit. In the general case, you can convert an arbitrary carry function to a transducer :

(defn carry-fn->transducer [cf]
  (fn [rf]
    (let [state (doto (object-array 1) (aset 0 (cf)))]
      (fn
        ([]
         (rf))
        ([r]
         (reduce rf r (cf (aget state 0))))
        ([r x]
         (let [[s & xs] (cf (aget state 0) x)]
           (aset state 0 s)
           (reduce rf r xs)))))))

(sequence (carry-fn->transducer inc-digit) [0 0 1])
#_=> (1 0 1)

Note that converting the other way round is not possible, because transducers encapsulate their state.

@leonoel It's indeed a statelesspurely functional transducer. However, let me disagree on your last claim:

Note that converting the other way round is not possible, because transducers encapsulate their state.

(defn xf->carry-fn [xf]
  (fn 
    ([] (xf conj))
    ([xrf] (xrf []))
    ([xrf x] (xrf [xrf] x))))

=> (carry (xf->carry-fn (partition-all 2)) (range 5))
([0 1] [2 3] [4])

@cgrand brilliant !