Hey! These are some interesting changes, let me go through them bit-by-bit:

On 1/9/23 11:45, siiky wrote:
[^1]: This can be easily remied if the sentinel is given to the collect
instead of the transduce, in which case the current def of transduce is
a single case-lambda case instead of two:

(transduce fold (map *) (collect 'sentinel-value) data)

I was "forced" to procrastinate yesterday by this incredible force... ^^'

Before jumping into the remaining bits, I saw that there was a commit in your fork of the repo regarding this. It's an interesting idea and I'm inclined to actually merge this in proper, but there is a trade-off (as there always is).

Namely, as transducers currently are one can use variable argument procedures as "collectors." I somewhat weighed on this back and forth when writing 0.1.0: is it worth having separate sum / product procedures or should I allow for collectors to be any procedure that is defined with 0-arity to 2-arity?

    (transduce list-fold
               (list 1 2 3 4 5))

See, if you want to be consistent and make it so that collectors always define their sentinel (which makes the API a bit more consistent), then you cannot do the above, since there's no way to call |(+ 100)| as a collector. You need a separate "sum" or "collect-sum" to function for you here.

I left it as-is because the broader Clojure community uses a similar strategy for their transducers. I think a difference here isn't necessarily /bad/ but it may mean that certain combinations collector + sentinel aren't as easy to express (without doing your own case-lambda, which means writing collectors yourself).

Thoughts? I don't think giving every collector an optional argument is necessarily wrong in terms of API but the trade-off does exist. Given that there's little code written with transducers today I'm not sure I have any argument-from-inertia to say which way is better or more useful but I think this is a good question to solve before a 1.0 release.

I've been thinking for the past couple of days about this and couldn't
come up with any way to make a generic "zip" work with transducers other
than (a) rewriting the basic algorithm of the egg (which is simple and I
prefer that way), or (b) introducing the concept of an "iterator" (which
is, I think, how Rust does it, and is equivalent to C++ Ranges (cf.
"Functional Programming in C++", Ivan Čukić)). The problem is that
type-fold does all the work from start to finish and can't be
"suspended" to look to the side for a second.

I personally think a fully generic zip / chain / interleave / flatten aren't that appealing. You (should) almost always know the type of something, and if you're doing a partial application, e.g.:

    (define my-process
        (zip-list (list 'a 'b 'c))
        (map ...)
        (filter ...)))

to later call |my-process| in a transducer, then the "zip" is well-defined by this point in most scenarios (in my experience, although that might be me conflating how I write code based on the API restrictions I have presented for myself). You have to monomorphize your function at some point, else you're using an intermediate type (which is just monomorphizing by indirection).

Because (a) goes against extending this egg, replacing its
implementation instead, and because it's a lot more work than (and not
as obvious as) (b), I went with (b).

An iterator is some object that keeps internal state about a collection
and how to access it, that can be used to incrementally[^0] traverse
this collection's elements in some (iterator-defined) order. Just like
streams![^1] So after a few hours hacking at it, it's as simple as this:

I do like your process of discovery; In fact, I actually started writing this egg with this exact thinking in mind: why not try to define a common iterator type for everything and then only provide one |iterable-fold| to rule them all? Well, it ended up being pretty slow, which forced me to re-think my assumptions about performance and how I should think about types in Scheme. Trying too hard to avoid any type-specification ends up being a problem in its own right if you take it too far.

Nevertheless, Rust's iterators are lazy (and very similar to streams). SRFI-41 streams have some performance questions compared to e.g. generators though, which is why I opted to make sure that reader-fold works with generators off the bat.

Generators are the more appropriate solution to laziness in most cases. Delay and Force seem to come with too much performance baggage for my taste, although I could absolutely see providing (transducers streams) and doing basically what you've done with "iterators" within transducers in a future version of the library.

After all, if you had (transducers streams) you could use the base and streams sub-modules and write whatever extension you wanted extant to that. This to me is why I came to settle on transducers in the first place - it allows this extension without requiring it in the core library itself. ;)

You actually do reference this later in your reply, but I wanted to underscore it here. It's an important point!

By implementing iterator-fold and the type->iterator functions
everything works OOB with the transducers egg. With some small changes
to the egg[0] (especially [1]), it can be improved (IMO) to this:

So I looked at the changes required here - regardless of the point on collect & sentinel vs. (collect #!optional sentinel), I am unsure that I want to change |transduce| too much.

I think the transduce you've provided, i.e.:

    (define (transduce folder xform collector iterable . iterables)
      (let* ((xf (xform collector))
             (sentinel (collector))
             (result (if (null? iterables)
                       (folder xf sentinel iterable)
                       (apply folder
                              (cons iterable iterables)))))
        (xf result)))

is probably better implemented as syntax (to avoid the apply, as was mentioned in the TODO comment), and probably best to call |transduce*|. That section for (if (null? iterables) ...) can easily distinguish between single collection and multi-collection variants, assuming they all use the same folder.

From an API perspective that to me seems more uniform / less special-case-y. I have to experiment with this though, because I'm biased towards believing that such code isn't really worth the extra complexity. With |chain| and |zip| transducers being available I think you can accomplish this in a more generic way (not requiring that all collections have the same folder), and I seldom find myself writing code where I need to collate / work across multiple collections.

I know Scheme is dynamic and that enables this, but 99% of my code will always tend towards using a single collection kind. In CHICKEN's type terminology, that's usually (list-of T) or (vector-of T). The example of:

    (transduce iterator-fold
               (map (cute apply * <>))
               (iterator-zip (list->iterator '(0 1 2 3 4))
                             (vector->iterator #(5 6 7 8 9))
                             (range->iterator 5))))
    ;=> (0 6 28 72 144)

seems a bit strange to me. I cannot rightly remember a time where I'd do something like this across a lot of types. Even thinking of code I've written in Rust -- it would be strange to do it this way. I struggle to think of a scenario where I'd have 3 different collection types that needed to be all zipped together like this. Enumeration is an obvious use-case, but |enumerate| is already a transducer.

I'm not fully convinced that this code is what I'd steer people towards, but I do appreciate that you've gone through the trouble / learning process on this one though. It has definitely helped me think about it more deeply. I still have to give it more consideration but there may be something here for a future version of the library.

[0]: https://git.sr.ht/~siiky/chicken-transducers/log/multiple-iterables

If it's alright with you, I will probably go ahead and grab at least the (test-exit) patch from above and apply it to transducers today. I can't believe I forgot that.

PS: great work on the docs, Jeremy, they look very comprehensive!

Thank you. This is probably the best compliment I could have received.

Jeremy Steward

Reply via email to