Fork me on GitHub
Jim Newton10:08:17

I'd like to ask someone's help in converting a function to produce a lazy sequence of lazy sequences, rather than a list of lists. It is a recursive function which serializes a particular data structure. It does not use loop/recur because in some cases it needs to recur multiple times, so not always in tail position. Basically it is a depth first search through a dag (containing diamonds), and I need to examine every branch until finding the leaf nodes. for certain leaf nodes, I want to collect the lineage (path from root to leaf) and at some leaves I want to NOT collect. In some cases (depending on application logic) I want to skip certain paths at branch points. Can this be done lazily? Why do I want to do it lazily? Because the main purpose of serializing is to compare the serializations of two structures to see whether they are the same, and if it discovers early that the serializations are different, the equality search should abort, thus obviating the rest of the two serializations.

Jim Newton11:08:42

one possiblity might be that I seem to recall there's a function which generates a lazy breadth-first graph search. I'm not sure whether there's a lazy depth-first search function???


I have an issue with where using zip/edit appears to change the type of the underlying sequence. Here's a minimal example:

(-> (zip/zipper
     (fn [n] (and (vector? n) (= :a (first n))))
     identity (fn [_ c] c) [:a [:b 3]])
     (zip/edit (fn [node] (apply vector (map #(if (number? %) (+ 1 %) %) node))))
Which results in:
=> [(:a [:b 4]) nil]
I'm not really sure what I'm doing here that changes the sequence type. I'd appreciate it if someone could point me in the right direction!

Alex Miller (Clojure team)14:08:17

up returns a loc, not the root node

Alex Miller (Clojure team)14:08:30

I think if you throw a zip/root at the end that will help

Alex Miller (Clojure team)14:08:37

or are you concerned about the list around :a

Alex Miller (Clojure team)15:08:33

the reason you're seeing that is your make-node function (fn [_ c] c) - as the zip/zipper doc says, "make-node is a fn that, given an existing node and a seq of children, returns a new branch node with the supplied children." so c is a seq and you're returning it. if you want a vector, you'll need to make it one with something like (vec c) there

Jim Newton16:08:33

I have an object which might be an array indexed by integers, or it might be a map of integer to something. I want to check whether a certain integer is a valid index.

Jim Newton16:08:37

what's the correct way?

Jim Newton16:08:18

actually I want to find the smallest positive integer which I can non-destructively add to the array/map

Darin Douglass16:08:55

(let [smallest (first (drop-while (partial contains? m) (range)))] ...)

Darin Douglass16:08:09

Something like that should work in both cases methinks.

Jim Newton16:08:08

clojure-rte.dfa-test> (first (drop-while (partial contains? {0 'a 1 'b} (range))))
Execution error (IllegalArgumentException) at clojure-rte.dfa-test/eval30802 (form-init5713417271367683958.clj:29412).
Don't know how to create ISeq from: clojure.core$drop_while$fn__5920

Jim Newton16:08:49

Ahh I see (contains? my-seq index) returns true if index is a valid index

Jim Newton16:08:58

that's enough. thanks.

Darin Douglass16:08:15

I typed that on my phone, that range defeinitely should be outside the partial. But glad you found the answer :)

Adam Helins21:08:57

Does anyone actually use eduction? It sounds great in theory but when I benchmark it once in a while, it does not seem to provide much, even with reduce


I see eduction as a way of attaching some transducer to a collection, while not doing anything yet. You can compose this many times, until you actually want to transduce the thing.

user=> (def xform1 (map inc))
user=> (def e (eduction xform1 [1 2 3]))
user=> (into [] (map inc) e)
[3 4 5]


range returns something that's a sequence, but also implements IReduce. Similarly, eduction returns something seqable and reducible. Useful in situations where you have a multi-stage pipeline, and each stage can return an eduction, and the rest can treat the previous stuff as sequences (which is especially useful for REPL-interaction). This has the advantage of not having to write everything in transducers, while still getting the benefit when you do.


TIL that when you print an eduction, it actually realizes the thing?

$ clj -e '(prn (eduction (map inc) [1 2 3]))'
(2 3 4)

Adam Helins22:08:22

Granted it improves composability! I kinda forgot about that. I was rather thinking about performance. Given that they don't cache results, somewhat akin to iterators, you could expect they would generally be faster than sequences but I have a hard time proving that.