Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# cgrand/_carry.md

Last active May 2, 2019

# 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  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?

 (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))))

### leonoel commented May 2, 2019

 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.

### cgrand commented May 2, 2019 • edited

 @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] )```

### leonoel commented May 2, 2019

 @cgrand brilliant !
to join this conversation on GitHub. Already have an account? Sign in to comment