[bjoli]

I stand by what I said (even though I am partial to transducers): there is no reason for lazy sequences overhead to be much more than a procedure call, which is exactly what a step in the reduction in the case of transducers is. At least when implemented as in clojure or srfi-171.

I understand that there might be some overhead to creating new sequence objects, but removing intermediate sequence object creation should be simple, at least for built in map-filter-take-et-al.

Edit: I seem to be wrong. People are recommending transducers over clojure's lazy map-filter-take-et-al because of overhead, which to me seems off, but there might be something about clojure's lazy sequences that I haven't grooked.

[lilactown]

I probably didn't make it any more clear in my reply. Transducers don't win based on allocations IME but because it removes the number of iterations required.

Take the case: (->> (for ,,,) (map ,,,) (filter ,,,))

`for`, `map` and `filter` will all create lazy sequences, holding a reference to the previous one. The problem here is when the `filter` seq gets realized, it will first realize the `map` seq, which will realize the `for` seq. Each sequence will wait for the next one to realize before iterating over it. So in this case it will iterate twice; once for the `map`, and then again for the `filter`.

As you know, transducers combine these steps together so that you only iterate over the initial collection once.

My other comment was making the point that the author has conflated "laziness" with "immutable data" AFAICT. The lazy seqs in the first example they give will be slower w/o transducers, but the other problem is that the overhead from all the allocations required for creating a bunch of immutable hash maps that are then destroyed immediately after is also non-negligible, and seems to be a source of the authors performance problems.

[dwohnitmok]

I think what bjoli is getting at is that in an ideal world with lazy sequences you don't have any iteration over any of the intermediate "collections" until some step occurs that requires the entire collection. I put collections in quotes because they aren't really collections, they're generators that produce an element on demand.

So you never really iterate over more than one collection; you only have one iteration where you successively ask each generator to produce a single element and then apply a function to it. For example, if you only asked for the first element of a lazy sequence formed by a series of maps, you would (in theory, in practice see my note about chunks) never iterate over any of the intermediate sequences and only ever examine the first element of each of them.

However, the act of asking a generator to produce an element (that is unwrapping a thunk) has overhead of its own and that's the overhead that a transducer would be removing (not iteration itself in the case of lazy sequences). This can have far more overhead than a procedure call because of bad cache locality (in the absence of fusion optimizations you're pointer chasing and potentially generating garbage for each thunk). Clojure tries to get around that by often (but not always) chunking its thunks, in which case we do have multiple rounds of iteration on smaller chunks, but never the entire sequence (unless the entire sequence is smaller than a chunk).

[bjoli]

What I am saying is that lazy sequences in my world should mean you don't have to realize any intermediate collections. In the case of the srfi-158 generator (gmap square (gfilter odd? (list-generator big-list))) the overhead for getting one element from the generator would be 3 procedure calls. Without any intermediate steps. The same transducer would have one procedure call less, but would be in the same vicinity.

Does clojure's sequences not work similarly? That seems like a very lax definiti

[lilactown]

Sounds like I was mistaken. What I was seeing in my tests was due to chunking, not realizing the whole seq.