3 ms·

So by what you wrote, it sounds like they're related, but a completely separate concept. Where can I find an intro to transducers that's readable for beginners?

• tel 12y ago
  If you know what monads are then you may know of join :: Monad m => m (m a) -> m a Since list is a monad then we know that join can be specialized to join :: [[a]] -> [a] which is just `concat` then. Now Transducers are a bit of an elaboration over functions like Transducer in out === in -> [out] and so we might compose them a little like comp t1 t2 in = concat (map t2 (t1 in)) which if you follow in types ends up working out. Finally, that concat/map business is just monadic bind in the list monad. We could also write comp t1 t2 in = t1 in >>= t2 = (concatMap t1 t2) = bind t2 (t1 in) depending on what syntax is most familiar. That's why they're (an elaboration of) "monad composition", i.e. a Kleisli category. The only thing left is just that Hickey did a transformation called "Church Encoding" or "Continuation Passing Style" to the regular list functions. This eliminates the need to generate concrete lists and turns this fancy composition into reverse normal function composition. It's a clever trick.