Re: New egg: CHICKEN Transducers

[siiky]

Hiya,

> This wouldn't work very well with the current API in Scheme, because the 
> fold is passed to transduce explicitly.  And given that, either a 
> restriction must be imposed on the input data structures (they must all 
> be of the same type); or the folder of each input data structure must be 
> given. If the latter something like this would be kinda awkward (though 
> not impossible, I guess):
>
> (transduce
>     list-fold vector-fold
>     (map *)
>     collect-list
>     lst vec)
>
> And accepting the optional sentinel with this new API would also be 
> awkward to implement[^1]...
>
>
> [^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... ^^'

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.

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:


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

;=> (0 6 28 72 144)


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:


(transduce
  (zipped-iterator-fold list->iterator vector->iterator range->iterator)
  (map (cute apply * <>))
  (collect-list)
  '(0 1 2 3 4) #(5 6 7 8 9) 5)


This small PoC can be found at [2] (just a bunch of SRFI 41 
renames[^2]). The pros/cons of this approach, the way I see it, are:

A new iterator-fold is needed to use the transducers egg with iterators. 
However, if you don't want/need iterators, you don't have to implement 
type->iterator for your data type(s), just use type-fold and there's no 
performance penalty (IIRC the main selling point of one of the 
generators SRFI was performance compared with streams?).  OTOH if you do 
want/need iterators, you have to implement type->iterator too (I say 
"too" but one doesn't strictly need both type-fold and type->iterator).

Nevertheless, from my understanding, using transducers on streams should 
still be better performance-wise than composing stream-map/filter/...



[^0]: it can be started/stopped at will

[^1]: I also realized why using lists as the intermediate sequence type 
is not such a big problem in Haskell and other lazy-by-default 
languages: they're actually streams!

[^2]: I also experimented with a hand-written stream-like type. Maybe 
it's possible to do better than streams but I dropped it for now.


[0]: https://git.sr.ht/~siiky/chicken-transducers/log/multiple-iterables
[1]: 
https://git.sr.ht/~siiky/chicken-transducers/commit/68f9d6d3faaf80e1b57c7bda5dec888b34c670dd
[2]: 
https://git.sr.ht/~siiky/experiments/tree/main/item/iterators/transducers-example.scm


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


siiky