DEV Community: Vincent Cantin

Building trees with and without zippers

Vincent Cantin — Sun, 07 Apr 2019 00:00:00 +0000

In his blog post and video from november 2018, Arne Brasseur explains the idea behind the functional zippers in the clojure.zip namespace. He describes how to use them to navigate existing tree-shaped data structures and how modify them.

There is something that he did not mention explicitly, it is that they are an excellent choice when you don’t have a tree but need to build one.

From sequence to tree

As an example, suppose that you have the following sequence of data:

(def elements [{:type :todo-list
                :name "Things I should do today"}
               {:type :text
                :value "Buy some bread"}
               {:type :url-list
                :title "Read blogs"}
               {:type :url
                :value "https://vincent.404.taipei"}
               {:type :url
                :value "https://lambdaisland.com/blog"}
               {:type :text
                :value "Look for some interesting Clojure blogs."}
               {:type :url-list-end}
               {:type :foo
                :value :bar}
               {:type :todo-list-end}
               {:type :life
                :description "Take the time to relax"}])

Now, suppose that what you really want is a tree structure like that one:

[{:type :todo-list
  :name "Things I should do today"
  :children [{:type :text
              :value "Buy some bread"}
             {:type :url-list
              :title "Read blogs"
              :children [{:type :url
                          :value "https://vincent.404.taipei"}
                         {:type :url
                          :value "https://lambdaisland.com/blog"}
                         {:type :comment
                          :value "Look for some interesting Clojure blogs."}]}
             {:type :foo
              :value :bar}]}
 {:type :life
  :description "Take the time to relax"}]

In order to do the transformation, you would intuitively need to:

find the beginning and the end of each block in the sequence,
build a tree node for each block,
have the elements of each block’s sub-sequence placed in that block as children,
look for the other blocks to process.

The recursive algorithm

Supposing that we already have the full sequence of data available when we want to process it, we could recursively build our tree by iterating on the sequence in this way:

(defn build-tree [data-sequence]
  (letfn [;; Returns [built-children unconsumed-sequence]
          (append-children [children [element & next-sequence :as data-sequence]]
            ;; End of the tree construction.
            (if (nil? data-sequence)
              [children nil]

              (case (:type element)
                ;; If we need to open a new block.
                (:todo-list :url-list)
                (let [[sub-node-children unconsumed-sequence]
                      (append-children [] next-sequence)]
                  (append-children (conj children (assoc element :children sub-node-children))
                                   unconsumed-sequence))

                ;; If we need to close the current block.
                (:todo-list-end :url-list-end)
                [children next-sequence]

                ;; If we want to add a leaf node to the tree.
                (append-children (conj children element) next-sequence))))]

    (first (append-children [] data-sequence))))

;; Transforms the sequence into a tree.
(build-tree elements)

That implementation is hard to understand simply because it does too many things at the same time:

Build a tree, nodes and children.
Keeps track of where we are in the sequence, in and out of recursive calls.
Iterate on the sequence and handle termination.

It also has limitations:

Messy code flow, hard to read and maintain with 3 different recursion calls combined in a complicated way.
Does not check the match between elements like :url-list and :url-list-end,would need an additional parameter for that (sigh!).
Not an incremental algorithm.

That type of recursive function takes a lot of time to write and debug. It is not good for its writer, and it is not good for the co-workers who have to read it at some point later in the future.

We certainly can - and therefore we should - do better.

Improvements

Important observation:

The tree is being built at the same time than the data-sequence is being read.

Instead of organizing the tree’s construction around the shape of the tree, we could organize it around the shape of the sequence. After all, thinking linearly is way more easy than thinking on a tree.

The idiomatic way to process sequences in Clojure is to use the reduce operation. For building our tree, it would look like this:

(reduce (fn [tree data-element]
          ;; Add the element to the existing tree, return the updated-tree.
          (some-magic tree data-element))
        empty-tree
        data-sequence)

Once we have an algorithm that updates the tree in a reducing process, we know that our algorithm is incremental, as the reduce function is an incremental process.

(reduce f :init [1 2 3])

;; The above can be rewritten as:
(-> :init
    (f 1) ; process one data
    (f 2) ; process another data
    (f 3)) ; and so on, and so on

The incremental algorithm

We need to replace the some-magic function above with some real code. Since we don’t have magic, let’s compensate using analytical thinking.

Tracking the node to edit

Adding an element to a tree is easy, but knowing where to add it is not trivial. The recursive algorithm knew where to add them because it implicitly kept track of the node being currently edited.

To emulate this, we need to keep track of that node.

“I am your father”

A shortcoming of the recursive algorithm was that there was no easy way to access the other existing nodes of the tree being built.

Ideally, it would be nice for the whole tree to be accessible at any time, specially the nodes close to the node been edited.

The zipper solution

Zippers have both of the features above:

They keep track of a tree structure and a current location in that tree.
They provide an access to the whole tree at any time of the editing, from the node being tracked.

Here is how the whole function looks like using a zipper:

(require '[clojure.zip :as z])

(defn build-tree [data-sequence]
  (let [;; Build a custom zipper
        empty-tree-zipper
        (z/zipper (comp #{:root :todo-list :url-list} :type) ; branch?
                  :children ; children
                  (fn [node children] ; make-node
                    (assoc node :children (vec children)))
                  {:type :root}) ; root

        ;; The incremental update function
        update-zipper
        (fn [zipper element]
          (case (:type element)
            (:todo-list :url-list) (-> zipper
                                       (z/append-child element)
                                       (z/down)
                                       (z/rightmost))
            (:todo-list-end :url-list-end) (z/up zipper)
            (z/append-child zipper element)))]

    ;; Process the whole sequence
    (-> (reduce update-zipper
                empty-tree-zipper
                data-sequence)

        ;; Return the tree data structure from the zipper
        z/root)))

(build-tree elements)

Noteworthy:

The update-zipper function is the most important part, it only take 8 lines of code and about 15 seconds to read and understand.
Modifying the code to check for matching open/close elements is trivial and is left to the reader as an exercise.
The function that manipulates the tree only do that, the function that define show to update node’s children is defined elsewhere.

What’s next

In the next article, I will talk about a real life problem where a tree needed to be built, and which was solved elegantly by using a custom zipper.

Transducer Exercises

Vincent Cantin — Wed, 30 May 2018 11:26:03 +0000

Contains exercises on implementing custom transducers in Clojure.

UPDATE: All the solutions are now posted on Github. This present article is no longer updated, please use the github version.

Fair notice

Implementing transducers is hard and you may feel confused.

That's normal and to be expected, it happens also to me when I read my own code. Just don't give up.

No Operation transducer

Implement a transducer that does nothing but passing the data from his input to his output. Functionally speaking, it is an identity transducer.

(into [] nop (range 3))
; => [0 1 2]

Use it as your transducer template for the following.

Prepare for battle

Implement the (debug in out) transducer that helps to debug.

; We use this function instead of `into` for debugging.
; The reason is that this avoids using transient
; structures which do not `print` nicely.
(defn slow-into [to xf from]
  (transduce xf conj to from))

(slow-into [] (debug "in" "out") (range 3))
;; Outputs:
; in 0 
; out [0] 
; in 1 
; out [0 1] 
; in 2 
; out [0 1 2]

Add the (debug), (debug indent) and (debug indent in out) variants for convenience. They are all calling the (debug in out) transducer under the hood.

(slow-into []
           (comp (debug)
                 (debug 2)
                 (debug 4 ">" "<"))
                 (debug "      >" "      <")) ; 6-spaces prefix
           (range 3))
;; Outputs:
; > 0 
;   > 0 
;     > 0 
;       > 0 
;       < [0] 
;     < [0] 
;   < [0] 
; < [0] 
; > 1 
;   > 1 
;     > 1 
;       > 1 
;       < [0 1] 
;     < [0 1] 
;   < [0 1] 
; < [0 1] 
; > 2 
;   > 2 
;     > 2 
;       > 2 
;       < [0 1 2] 
;     < [0 1 2] 
;   < [0 1 2] 
; < [0 1 2]

Strange patterns, it reminds me of ...

The PHP Hadouken !!!

We are now ready to face real transducer implementations and confront an army of problems.

May I beg your pardon?

You heard me well, I want you to implement the following transducer.

(def beg-data (list :may :i :beg :your :pardon :?))

(into [] (beg 2) beg-data)
; => [:may :may :i :i :beg :beg :your :your :pardon :pardon :? :?]

Make sure that you are handling the early termination as well.

(into []
      (comp (take 3)
            (beg 2))
      beg-data)
; => [:may :may :i :i :beg :beg]

Test for both sides.

(into []
      (comp (beg 2)
            (take 3))
      beg-data)
; => [:may :may :i]

Test with the debug transducer (expect problems and losing some hair).

(slow-into []
           (comp (debug 0)
                 (beg 2)
                 (debug 2)
                 (take 3)
                 (debug 4))
           beg-data)
; Output:
; > :may 
;   > :may 
;     > :may 
;     < [:may] 
;   < [:may] 
;   > :may 
;     > :may 
;     < [:may :may] 
;   < [:may :may] 
; < [:may :may] 
; > :i 
;   > :i 
;     > :i 
;     < [:may :may :i] 
;   < #reduced[{:status :ready, :val [:may :may :i]} 0x8cdcdd1] 
; < #reduced[{:status :ready, :val [:may :may :i]} 0x8cdcdd1] 

; Result:
; => [:may :may :i]

The beg transducer should not continue sending data downstream after it receives a reduced result. Fix your implementation if needed.

All your data are belong to me

Implement the my-cat transducer. For each step, you will need to adapt your implementation to the new requirements described by the test samples.

Step 1, shapeless cat

It functions similarly to clojure.core/cat. Don't handle early termination at the moment.

(def cat-data [[1 2 :fish 3] [:heat 4] [5 :sleep 6] [7]])

(into [] my-cat cat-data)
; => [1 2 :fish 3 :heat 4 5 :sleep 6 7]

Step 2, hungry cat

As you can see, the transducer is keeping for itself all the fishes and the heat.

(into [] my-cat cat-data)
; => [1 2 3 4 5 :sleep 6 7]

Step 3, sleepy cat

That version of the transducer falls asleep an the :sleep keyword and do not process any subsequent data.

(into [] my-cat cat-data)
; => [1 2 3 4 5]

Step 4, correct cat

At last, we want our transducer to respect the normal early termination (with reduced? tested on the downstream result) in a correct manner.

(into [] (comp (take 2)
               my-cat)
      cat-data)
; => [1 2 3 4]

(into [] (comp my-cat
               (take 2))
      cat-data)
; => [1 2]

(slow-into [] (comp (debug 0)
                    my-cat    ; try replacing it with `cat` and compare
                    (debug 2)
                    (take 2)
                    (debug 4))
           cat-data)
;; Outputs:
; > [1 2 :fish 3] 
;   > 1 
;     > 1 
;     < [1] 
;   < [1] 
;   > 2 
;     > 2 
;     < [1 2] 
;   < #reduced[{:status :ready, :val [1 2]} 0x517a7e8e] 
; < #reduced[{:status :ready, :val [1 2]} 0x517a7e8e]

Provide an idiomatic equivalent to my-cat.

A.D.D. transducer

Implement a transducer that daydream during a number of elements. While in the daydream state, it buffers its input. When it stops daydreaming, it processes all of its buffer as a batch, then daydreams again.

The a-d-d transducer never loses data.

(into [] (a-d-d 3) (range 10))
; => [0 1 2 3 4 5 6 7 8 9]

; Try:
(slow-into [] (comp (debug 0)
                    (a-d-d 3)
                    (debug 2))
           (range 10))

Change a-d-d so that it works similarly to clojure.core/partition-all.

(into [] (a-d-d 3) (range 10))
; => [[0 1 2] [3 4 5] [6 7 8] [9]]

Verify that it works well with early termination.

(slow-into [] (comp (debug 0)
                    (a-d-d 3)
                    (debug 2)
                    (take 2))
           (range 10))
; => [[0 1 2] [3 4 5]]

A reducer inside a transducer

Implement serieduce which provides a transducer which reduces incoming elements and emits all intermediary elements.

(into [] (serieduce conj [1 2]) (range 3 6))
; => [[1 2 3] [1 2 3 4] [1 2 3 4 5]]

(into [] (serieduce +) (range 5))
; => [0 1 3 6 10]

Congratulations if you made it that far!

You are one of a few.

Transducer Workshop Announcement

Vincent Cantin — Thu, 24 May 2018 02:03:37 +0000

Sharpen your Clojure transducer skills and have fun.

Where, When

There will be a transducer workshop during the Meetup of the Clojure Taiwan Community on May 30th 2018, at 19:45 (UTC+8).

Live broadcast

The workshop (in English) will be interactive and will mainly consist in practicing implementing strange transducers. The workshop will be broadcasted live on the community's Youtube channel.

For those interested to join the event and ask questions, you can do so via the community's Telegram channel.

Be prepared

I invite you to prepare yourself before the workshop by reading my blog serie on Transducers.

Build Your Own Transducer and Impress Your Cat - Part 5

Vincent Cantin — Mon, 21 May 2018 14:29:07 +0000

This post is a part of a serie:

Introduction to transducers
Anatomy of a transducer
Stateful transducers
Early termination in transducers
Functions which are using transducers (this post)
Transducer exercises and solutions

This article describes some functions which are using transducers, and how to write your own.

Transducers, getting `into` using them

If you followed the previous 4 parts of this blog serie, you may have noticed that I only mentioned one function which is using transducers so far: the into function.

(into [] (map inc) (list 3 4 5))
; => [4 5 6]

There are more of that kind. Their role is to provide the context of a stream transformation. This includes to provide a data stream to the transducer, and to deal with the transformed stream that they get from the transducer.

They are:

the from where and the to where,
the how do I take that input and the what should I do with that output.

And since they are the one which are calling the transducer, they are also in charge of deciding the when do I do this to that.

Transducer users from the standard library

Note: In the following paragraph, the parameter xform refers to a transducer.

(into to xform from): When you want the output stream's elements to be all stored in a collection, which can be a vector, a list, a map, a sorted map, or any other type of other collection. I love that function because it appends to the collection in a very efficient way.
(sequence xform coll): When you want the stream to be processed "only when needed". Useful if you think that the sequence consumer may not need all the output elements, or if don't want all of it to be processed immediately. That's useful for throttling the transformation w.r.t. the CPU workload, or if you need to send the output stream over a slower channel like the network and you don't want to buffer the whole output stream in advance.
(eduction xform* coll): ... it's complicated, see the docs for a precise explanation. Rarely needed by the average programmer. It returns a non-lazy sequence which is evaluated using the transducers each time it is being used by a reduce function.
(transduce xform f init coll): When you want to use the reduce operation but you also want to perform a stream transformation on the data to be reduced.

Transducer users from the `clojure.core.async` library

(chan buf-or-n xform): Creates a channel where the data stream on the reader side will be the one of the writer side transformed by the transducer.
(pipeline n to xf from): "Takes elements from the from channel and supplies them to the to channel, subject to the transducer xf, with parallelism n [...]". To be used only with stateless transducers. Has the pipeline-blocking variant.
(transduce xform f init ch): A variant of clojure.core/transduce where the data stream comes from a channel instead of a collection.

Other uses of transducers

There may be other functions that use transducers, adapted to different contexts. If you know some, please let me know by leaving a comment and I will add them if they are relevant to the audience.

Let's implement some!

Good news, transducers are now your friends, you can call them when you want. But if you want to be a good friend, there are some rules to follow.

The output function

Transducers are technically functions which transform a reducing function into another reducing function.

If you don't know what that mean, you can also see them as a functions that transform a kind of output function into another one, except that this output function is taking a kind of accumulator value as its first parameter.

Let's play with this idea a bit and let's implement a function that provides a stream of data from a collection to a transducer and outputs the transformed stream to the standard output, element by element.

; Notes:
; - Don't do this at home, this is still a toy function.
; - The transducer is often called 'xf' and the reducer function 'rf'.
(defn print-duce [transducer coll]
  (let [reduction-fn #(print (str %2 \space))
        process (transducer reduction-fn)]
    (loop [c coll]
      (when (seq c)
        (do
          (process nil (first c))
          (recur (rest c)))))))

(print-duce (map inc) (list 3 4 5))
; Output:
; 4 5 6

; But this does not work:
(print-duce (partition-all 2) (list 3 4 5))
; Output:
; [3 4]
;
; the [5] is missing!

{0 1 2}-Arity

If you read the parts 1 to 4 of this blog serie, you will know that transducers are expected to be called with different arities.

0-Arity: Just ignore it, don't call it unless you know what you are doing (and let me know why in the comments or in that StackOverflow question).

2-Arity: Call it each time you want to feed one more data element to the transducer.

1-Arity: Call it once you to inform that there are no inputs available anymore. The transducer (even a stateless one) may flush a few more data to your output function.

Now let's improve our print-ducer a bit.

; Note: Still a toy function.
(defn print-duce [xf coll]
  (let [rf (fn ([])
               ([result] (print (str \newline "--EOS")))
               ([result input] (print (str input \space))))
        process (xf rf)]
    (loop [c coll]
      (if (seq c)
        (do
          (process nil (first c)) ; 2-arity 'process'
          (recur (rest c)))
        (process nil)))))         ; 1-arity 'flush'

(print-duce (map inc) (list 3 4 5))
; Output:
; 4 5 6 
; --EOS

; Now this works:
(print-duce (partition-all 2) (list 3 4 5))
; Output:
; [3 4] [5] 
; --EOS

Enough is enough (early termination)

Your transducer has its say on when to stop the stream. It will return a reduced value when it thinks that there should not be any other element. You need to pay attention to it and not ask too much.

(defn print-duce [xf coll]
  (let [rf (fn ([])
               ([result] (print (str \newline "--EOS")))
               ([result input] (print (str input \space))))
        process (xf rf)]
    (loop [c coll]
      (if (seq c)
        (let [result (process nil (first c))]
          (if (reduced? result)
            (process (deref result)) ; unwraps it and stop processing the stream
            (recur (rest c))))       ; continue processing the stream
        (process nil)))))

Note that I used deref in order to unwrap the reduced value while I was using unreduced in the part 4. Those two functions are different, deref really does unwrap the reduced value, and unreduced is unwrapping a value only if it is reduced.

Source code:

(defn unreduced [x]
  (if (reduced? x) (deref x) x))

Reduce function as a parameter

What if we want to make our function more general and accept a "1-and-2-arity" reducing function as a parameter?

(defn multi-duce [xf rf init coll]
  (let [process (xf rf)]
    (loop [acc init
           c coll]
      (if (seq c)
        (let [result (process acc (first c))]
          (if (reduced? result)
            (process (deref result))
            (recur result (rest c))))
        (process acc)))))

(multi-duce (map inc) conj [] (list 3 4 5))
; => [4 5 6]

(multi-duce (partition-all 2) conj [] (list 3 4 5))
; => [[3 4] [5]]

Easy made simple (by my cat)

My cat just told me that I am an idiot as there is a shorter and more efficient way to implement the function above.

I gave the keyboard to him and here is what he shown me:

(defn cat-duce [xf rf init coll]
  (let [process (xf rf)
        result (reduce process init coll)]
      (process result)))

(cat-duce (map inc) conj [] (list 3 4 5))
; => [4 5 6]

(cat-duce (partition-all 2) conj [] (list 3 4 5))
; => [[3 4] [5]]

Indeed, it seems to work. Thank you cat!

The `transduce` function

The cat-duce function is very close to the implementation of the legendary transduce function. It has the same signature and almost the same implementation, the difference being the added support for collections which want to be noticed when they are being reduced (like the result of the eduction function).

What's next

Congratulations !!!

By now you should probably know anything you need to use the transducers in your own custom way. You may still need to exercise your skills a little bit - Practice makes perfect.

I am going to publish some transducer-related exercises on May 30th 2018 to be used as a support for a transducer workshop in Taipei. The link will be added here soon after.

Stay tuned!

UPDATE: I created some transducer exercises and their solutions.

Build Your Own Transducer and Impress Your Cat - Part 4

Vincent Cantin — Sun, 13 May 2018 08:24:09 +0000

This post is a part of a serie:

Introduction to transducers
Anatomy of a transducer
Stateful transducers
Early termination in transducers (this post)
Functions which are using transducers
Transducer exercises and solutions

Early termination and `reduced?` values in transducers

Suppose that you want to write a transducer that uses some of the elements in the input stream and then ignore anything after it. It would be a waste to have to iterate on the remaining values of the stream if we do not use them.

(defn tired-map-transducer [func energy tired-answer]
  (fn [rf]
    (let [state (volatile! energy)]
      (fn ([] (rf))
          ([result] (rf result))
          ([result input]
           (rf result
               (let [energy @state]
                 (if (pos? energy)
                   (do
                     (vreset! state (dec energy))
                     (func input))
                   tired-answer))))))))

(into []
      (tired-map-transducer inc 5 :whatever)
      (list 1 2 3 4 5 6 7 8 9 10))
; => [2 3 4 5 6 :whatever :whatever :whatever :whatever :whatever]

We certainly want to find a way to let the function calling the transducers to stop calling them.

We could do that in multiple ways, like sending a special value :enough after the last data. But what if that special data :enough appears in some input data stream? Sending it to the output would be misleadingly interpreted as the transducer's message to early terminate.

The Clojure core team came up with something that is very unlikely to appear in the input data stream by luck (or we could call it a bug and blame the user instead :-) ), and established it as a convention for transducers to inform their calling function about a value being the last one their would like to return.

That convention is: (reduced last-value)

(defn responsible-map-transducer [func energy]
  (fn [rf]
    (let [state (volatile! energy)]
      (fn ([] (rf))
          ([result] (rf result))
          ([result input]
           (let [energy @state]
             (vreset! state (dec energy))
             (cond-> (rf result (func input))
               (<= energy 1) reduced)))))))

(into []
      (responsible-map-transducer inc 5)
      (list 1 2 3 4 5 6 7 8 9 10))
; => [2 3 4 5 6]

reduced is simply returning a wrapped value. A value can be tested by the calling function as being wrapped or not by using the predicate reduced?.

(reduced? 7)
; => false

(reduced? (reduced 7))
; => true

Are we done, then?

There is one more thing to check before calling it done.

Let's test our transducer a little more. Is it still going to work in those cases?

(into []
      (comp
        (responsible-map-transducer inc 5)  ; Step 1
        (responsible-map-transducer inc 3)) ; Step 2
      (list 1 2 3 4 5 6 7 8 9 10))
; => [3 4 5]
; It works fine.

(into []
      (comp
        (responsible-map-transducer inc 3)  ; Step 1
        (responsible-map-transducer inc 5)) ; Step 2
      (list 1 2 3 4 5 6 7 8 9 10))
; => [3 4 5]
; It works fine.

It all works fine. So why did I ask? Because you have to know why it still works.

The implementation of responsible-map-transducer only took care of what it returns when it has no energy. Nothing special was done with the result of (rf result ...) in the normal case, it was simply returned as is. If it was a reduced? value, it means that the rf function wanted an early termination. Our transducer has to make sure that in this case the returned value is reduced.

It happens to be the case here because we simply returned what the rf function returned, so we are in luck. This may not always be the case, so always pay attention and watch in both ways:

Handle the case where your transducer wants an early termination,
Handle the case where rf wants an early termination.

The devil is in the details

Did you think about testing that?

(into []
      (comp
        (responsible-map-transducer inc 3)  ; Step 1
        (responsible-map-transducer inc 3)) ; Step 2
      (list 1 2 3 4 5 6 7 8 9 10))

You didn't? Too bad because you should have: It triggers a bug and you get an extremely unclear error message now.

; => ClassCastException clojure.lang.Reduced cannot be cast to clojure.lang.ITransientCollection  clojure.core/persistent! (core.clj:3240)

Something happened when we returned a value which was wrapped at the same time by both transducers: (reduced (reduced last-value))

The function which is calling the transducers (i.e. into) is supporting early termination by expecting either a value or a reduced value, in which case it is getting the unwrapped value via (unreduced reduced-value). But instead of getting the value, it still gets a reduced value.

(reduced? (unreduced (reduced (reduced 7))))
; => true

How to fix it? Either we ask the Clojure core team to change all the functions which are using transducers to support multi-wrapped values, or either we avoid wrapping the values more than once.

"There is a function for that" --Rich Hickey

We can use the function ensure-reduced from the standard library. Its implementation is very simple:

(defn ensure-reduced [x]
  (if (reduced? x) x (reduced x)))

Now let's correct our transducer.

(defn correct-map-transducer [func energy]
  (fn [rf]
    (let [state (volatile! energy)]
      (fn ([] (rf))
          ([result] (rf result))
          ([result input]
           (let [energy @state]
             (vreset! state (dec energy))
             (cond-> (rf result (func input))
               (<= energy 1) ensure-reduced))))))) ; <- The difference is here

(into []
      (comp
        (correct-map-transducer inc 3)  ; Step 1
        (correct-map-transducer inc 3)) ; Step 2
      (list 1 2 3 4 5 6 7 8 9 10))
; => [3 4 5]

; Idiomatic way:
; (into []
;       (comp
;         (take 3)   ; Step 1
;         (map inc)  ; Step 2
;         (map inc)) ; Step 3
;       (range 1 11))

What's next

You already know everything you need to implement your own transducers. I encourage you to try some ideas on your own. If you encounter blocking problems in your adventure, feel free to leave a comment and I will try to help you (when I have time).

In the next part, I talk about functions like into which are using the transducers and how to write one.

Build Your Own Transducer and Impress Your Cat - Part 3

Vincent Cantin — Sat, 12 May 2018 16:19:07 +0000

This post is a part of a serie:

Stateful transducers

This article describes briefly how to implement a stateful transducer.

When do we need them

We need them each time some output elements depend on multiple input elements.

Some information related to previous input values need to be stored until the transducer has enough of them to start outputting values.

The information stored could simply be the input values, or it could be a derived information (which usually takes less space in memory).

Stringifier Transducer

Suppose that we have a stream of chars representing zero terminated strings and we want to have a stream of strings.

(defn string-builder-transducer [separator]
  ; The local state *should not* be defined here.
  (fn [rf]
    ; The local state of the transducer comes here.
    (let [state (volatile! [])]
      (fn ([] (rf))
          ([result] (-> result
                        (rf (apply str @state))
                        (rf)))
          ([result input]
           (let [chars @state]
             (if (= separator input)
               (do (vreset! state [])
                   (rf result (apply str chars)))
               (do (vreset! state (conj chars input))
                   result))))))))

(into []
      (string-builder-transducer 0)
      (list \H \e \l \l \o 0 \C \l \o \j \u \r \e 0 \w \o \r \l \d \!))
; => ["Hello" "Clojure" "world!"]

Three notes:

The position where the local state should be introduced matters. If you introduce it at the wrong place, some local state will linger when the transducer is used in multiple pipelines and cause bugs.
volatile! and vreset! are used instead of atoms for efficiency.
In this example, the transducer simply stores the encountered chars until the end of each chunk and then used them all at once to create a string. It does not have to always be this way (e.g. the next paragraph).

Chunk Sum Transducer

Suppose that we have a stream of numbers separated by a special keyword :| and we want to compute the sum of each chunk of numbers.

(defn chunk-sum-transducer [separator]
  (fn [rf]
    (let [state (volatile! 0)]
      (fn ([] (rf))
          ([result] (-> result
                        (rf @state)
                        (rf)))
          ([result input]
           (let [acc @state]
             (if (= separator input)
               (do (vreset! state 0)
                   (rf result acc))
               (do (vreset! state (+ acc input))
                   result))))))))

(into []
      (chunk-sum-transducer :|)
      (list 1 2 3 4 :| 42 :| :| 3 5))
; => [10 42 0 8]

Note that our transducer is efficient in terms of memory as it only keep a sum of numbers in its local state instead of all the elements of the current chunk.

Packet Transducer

Another example a little more complex, this transducer groups messages together in packets of data so that the size of the packet does not exceed its maximum limit (if possible, otherwise it uses bigger packets).

Here we use a map containing multiple values as the local state.

(defn packet-transducer [max-size]
  (fn [rf]
    (let [state (volatile! {:packet []
                            :size 0})]
      (fn ([] (rf))
          ([result]
           (let [{:keys [packet size]} @state]
             (cond-> result
                     (pos? size) (rf packet) ; Flush the local state to output.
                     :always (rf))))         ; Transmit the flush signal.
          ([result input]
           (let [{:keys [packet size]} @state
                 input-size (count input)
                 new-size (+ size input-size)]
             (if (<= new-size max-size)
               (do (vreset! state {:packet (conj packet input)
                                   :size new-size})
                   result)
               (do (vreset! state {:packet [input]
                                   :size input-size})
                   (cond-> result
                           (pos? size) (rf packet))))))))))

(into []
      (packet-transducer 5)
      (list [1 1] [2 2] [3 3 3] [4 4] [5] [6 6 6 6 6]))
; => [[[1 1] [2 2]] [[3 3 3] [4 4]] [[5]] [[6 6 6 6 6]]]

What's next

In the next part of this blog serie, I talk about how to support early termination in a data pipeline by using reduced and reduced?.

Build Your Own Transducer and Impress Your Cat - Part 2

Vincent Cantin — Thu, 10 May 2018 13:32:27 +0000

This post is a part of a serie:

Anatomy of a transducer

This article describes briefly the structure of a transducer and how to implement one.

Simple one-one mapping

Let's suppose that we want to manually create a transducer that increments numbers. We could normally just use (map inc), but for the training we will do it from scratch.

(def inc-transducer
  (fn [rf]
    (fn ([] (rf))                                   ; 0-arity aka 'the useless'
        ([result] (rf result))                      ; 1-arity aka 'the flusher'
        ([result input] (rf result (inc input)))))) ; 2-arity aka 'the doer'

(into [] inc-transducer (list 4 5 6))
; => [5 6 7]

; idiomatic way:
; (into [] (map inc) (list 4 5 6))

The rf function is processing the output value of our transducer. It does ... 'something' to return a merged (or not) version of the result value with the processed data's value (inc input), and our transducer needs to return that new result.

The rf function could be just another transducer which we composed with, or it could be a terminal reducing function (hence the name rf).

The 0-arity function is (IHMO) a useless bogus convention as we cannot rely on it being called for sure by the functions which use transducers. Just transmit the call to the next transducer/rf, maybe it will do something with it in some specific context, who knows.

The 1-arity function is called by the function who uses the transducer when there is no more data to be processed. That's where transducers can flush their data if they had some in a local state (more on this possibility later).

The 2-arity is where the input data gets processed and passed to the next function in the pipeline.

One-one mapping with parameters

Now let's suppose that instead of incrementing the numbers we want to add them a given value, then we need a transducer with a parameter.

(defn add-transducer [n]
  (fn [rf]
    (fn ([] (rf))
        ([result] (rf result))
        ([result input] (rf result (+ input n))))))

(into [] (add-transducer 3) (list 4 5 6))
; => [7 8 9]

; idiomatic way:
; (into [] (map #(+ 3 %)) (list 4 5 6))

No Rabbit transducer (One-Some)

We want a transducer that makes the rabbits disappear, to illustrate the case where the transducer may not provide a new output value.

(defn magician-transducer [animal]
  (fn [rf]
    (fn ([] (rf))
        ([result] (rf result))
        ([result input]
          (if (= animal input)
              result             ; Just don't "merge" the input into the result.
              (rf result input))))))

(into [] (magician-transducer :rabbit) (list :dog :rabbit :lynel))
; => [:dog :lynel]

; idiomatic ways:
; (into [] (remove #(= :rabbit %)) (list :dog :rabbit :lynel))
; (into [] (filter #(not= :rabbit %)) (list :dog :rabbit :lynel))

No rabbit, no problem.

More cats transducer (One-Two)

And what if we want more cats now? (more data output than input)

(defn glitch-transducer [animal]
  (fn [rf]
    (fn ([] (rf))
        ([result] (rf result))
        ([result input]
         (if (= animal input)
             (-> result
                 (rf input)
                 (rf input)) ; Send the input twice to the output pipeline.
             (rf result input))))))

(into [] (glitch-transducer :cat) (list :dog :cat :lynel))
; => [:dog :cat :cat :lynel]

; idiomatic way:
; (into []
;       (mapcat #(if (= :cat %) (list % %) (list %)))
;       (list :dog :cat :lynel))

More cats. Neo would be happy.

RLE decompression (One-Many)

Suppose that we want to send a serie of values in one go to the output but we can't do it as in the previous example because the number of repeats is not fixed or is too big and we are lazy and sane. We can use reduce to output the values one by one (now you can see why rf is called like that, it can be seen as a reducing function).

(def rle-decoder-transducer
  (fn [rf]
    (fn ([] (rf))
        ([result] (rf result))
        ([result [count data]]
         (reduce rf result (repeat count data))))))

(into []
      rle-decoder-transducer
      (list [0 :a] [1 :b] [2 :c] [3 :d]))
; => [:b :c :c :d :d :d]

; idiomatic way:
; (into []
;       (mapcat (fn [[count data]] (repeat count data)))
;       (list [0 :a] [1 :b] [2 :c] [3 :d]))

What's next

All the transducers shown above are stateless: Their behavior is fully described by their inputs and their initial immutable parameters.

In the next part of this blog post, I cover the stateful transducers, those with a local mutable state.

Build Your Own Transducer and Impress Your Cat - Part 1

Vincent Cantin — Tue, 08 May 2018 12:19:56 +0000

This post is a part of a serie:

This article is a brief introduction to what transducers are and how to use them.

Hello Transduced World

In simple words:

A transducer is the equivalent of an operation on a stream of data elements.

That man is a kind of transducer, it takes data elements from its input and may send some on its output:

You can see it as a function which is called exactly once for each element of the input stream, and which can spit any number of elements to its output stream.

There is a special emphasis on the fact that:

the transducer is not taking anything from the input stream by itself, it is not his job or responsibility. It gets called (by something else) with each data element.
the transducer only knows that it has to call a designated (and obscure) function with each of it output elements and has to return its result. It has no idea where the data goes.

🤓 Note: If you want to play at being yourself a transducer in a funny fictional world with an intuitive and simple programming syntax, give this cool game a try.

Vincent, please focus

Oh okay, right.

Here is the simplest transducer:

(map identity)

It accepts some data elements as input and gives the exact same data elements to its output. Except that at the moment it has no friends, nobody gave him data and it was not provided an output. A transducer alone is like a stomach without food (hmm .. let's not talk too much about the output in that case, but notice that it still needs a place to go).

Let's use that transducer properly. Here the into function gives it some data elements from a list and collects its output elements into a vector.

(into [\b \a] (map identity) (list \n \a \n \a))
; => [\b \a \n \a \n \a]

Another example with a transducer that actually does something with its input, it transforms each char into its preceding char in the alphabet.

(into [\b \a]
      (map #(char (dec (int %))))
      (list \u \n \b \o))
; => [\b \a \t \m \a \n]

Notice that you can use any function f which takes 1 value as parameter and returns 1 value by using the form (map f). Simple and easy.

Now let's see some built-in transducers which do not have the same number of input and output elements.

This one outputs 1 or none output element for each input element:

(into []
      (filter #(<= (int \a) (int %) (int \f))
      (list \c \r \a \f \e \b \h \a \b \l \e)))
; => [\c \a \f \e \b \a \b \e]

This one gives 1 or more output elements for each input element.

(into []
      (mapcat #(if (<= 0 % 9)
                   (list % %)
                   (list %)))
      (list 10 5 16 7 13)))
; => [10 5 5 16 7 7 13]

Notes: The function provided to mapcat returns a collection of arbitrary size and mapcat returns a transducer which outputs an arbitrary number of elements for each input element.

Will it blend?

Multiple transducers can be piped together to give birth to more complex data processing pipelines. This is done via the comp function and the result of the composition is a transducer. The data elements flow one after another through the pipeline, no buffer is used for storing intermediary results between each of its steps - that's a streaming process.

(into []
      (comp
        (map inc)                 ; first step
        (filter odd?)             ; second step
        (mapcat #(if (<= 0 % 9)   ; third step
                     (list % %)
                     (list %))))
      (list 8 9 10 11 12)))
; => [9 9 11 13]

The built-in transducers

Clojure has a few transducers which are very popular because they are handy.

[TODO: insert a link to a post that my future self will write about it]

What's next

In the next post, I talk about the anatomy of a transducer and how to program your own.

DEV Community: Vincent Cantin

Building trees with and without zippers

From sequence to tree

The recursive algorithm

Improvements

The incremental algorithm

Tracking the node to edit

“I am your father”

The zipper solution

What’s next

Transducer Exercises

Fair notice

No Operation transducer

Prepare for battle

May I beg your pardon?

All your data are belong to me

A.D.D. transducer

A reducer inside a transducer

Congratulations if you made it that far!

Transducer Workshop Announcement

Where, When

Live broadcast

Telegram

Be prepared

Build Your Own Transducer and Impress Your Cat - Part 5

Transducers, getting into using them

Transducer users from the standard library

Transducer users from the clojure.core.async library

Other uses of transducers

Let's implement some!

The output function

{0 1 2}-Arity

Enough is enough (early termination)

Reduce function as a parameter

Easy made simple (by my cat)

The transduce function

What's next

Build Your Own Transducer and Impress Your Cat - Part 4

Early termination and reduced? values in transducers

Are we done, then?

The devil is in the details

"There is a function for that" --Rich Hickey

What's next

Build Your Own Transducer and Impress Your Cat - Part 3

Stateful transducers

When do we need them

Stringifier Transducer

Chunk Sum Transducer

Packet Transducer

What's next

Build Your Own Transducer and Impress Your Cat - Part 2

Anatomy of a transducer

Simple one-one mapping

One-one mapping with parameters

No Rabbit transducer (One-Some)

More cats transducer (One-Two)

RLE decompression (One-Many)

What's next

Build Your Own Transducer and Impress Your Cat - Part 1

Hello Transduced World

Vincent, please focus

Will it blend?

The built-in transducers

What's next

Transducers, getting `into` using them

Transducer users from the `clojure.core.async` library

The `transduce` function

Early termination and `reduced?` values in transducers