4 ms·

Transducers really sound like monads. Are they the same thing?

• lgas 12y ago
  No.
• tel 12y ago
  In almost every meaning of that sentence—no. One simplified model of transducer happens to be similar to half of a particular monad. It's very disingenuous to say that "transducers are monads" or even "transducers are a particular form of monad", however.
  • iamwil 12y ago
    :( it was an honest question. I really didn't know. I watched the talk. I didn't get everything that was said, so I came here to ask a question. Man, HN is use to too much snark.
    • tel 12y ago
      Oh! Sorry, I may have written that poorly. I meant that technically: "in almost every sense, no". There is one sense in which "yes" they kind of are: a simplified model can be seen as Transducer a b ~ (a -> [b]) where the right side is a pretty fundamental type when talking about the list monad. In fact, composition of transducers is exactly "monad-arrow composition" or "composition in the list monad Kleisli category". So in that sense, they are a particular form of monad. But it's a bit of a stretch. Thus, I really meant it in "almost every way", not every way entirely.
      • iamwil 12y ago
        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? I don't know what "list monad Kleisli category" means. Searching for "transducers" came up with a physical transducer.
        • 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.
    • tome 12y ago
      Your question was perfectly fine and reasonable. tel wasn't trying to criticise it, but as he said he "may have written [his reply] poorly".