7 ms·

What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function com

• kazinator 12y ago
  I think "as fundamental as function composition" means that the relationship between a function like map and a transducer (map f) is fundamental in some sense that resembles function composition. But it isn't composition: it's something that "wrangles" the "reduce kernel" out of the combination of map and f: when we map something using f, what function instead of f will do the same mapping under reduce? That function inherits logic from map, and from f, but it's not a composition of the two.
  • moomin 12y ago
    I think what the author ultimately means is "well behaved transducers are equivalent to functions of the form a->[b] (modulo state) and therefore form a category". True story: the transducer announcement has mostly made me read up on the Haskell fold and lens libraries...
    • tel 12y ago
      If you think of Transducers as type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r) (And I'm not claiming this is correct) then you can reasonably easily show that this is isomorphic to (a -> [b]) forall r . (b -> r -> r) -> (a -> r -> r) forall r . (r -> b -> r) -> (r -> a -> r) a -> (forall r . (r -> b -> r) -> r -> r) [non-obvious, but true] a -> [b] This is "obviously" the Kleisli category for [] so you get rich, rich structure here. If you want to include local state such as what's needed to implement `take` then you can do something like data Fold i o where Fold :: (i -> x -> x) -> x -> (x -> o) -> Fold i o type Transducer a b = forall r . Fold b r -> Fold a r If you're familiar with pure profunctor lenses then I can tell you that Fold is a Profunctor and thus these can be acted on by a lot of generalized lens combinators. This explains a lot of the richness.
      • DanWaterworth 12y ago
        Here's proof that the last two parts are isomorphic: to :: (a -> [b]) -> (a -> (forall r . (b -> r -> r) -> r -> r)) to f a = h (f a) where h :: [b] -> (forall r . (b -> r -> r) -> r -> r) h b cons nil = case b of (x:xs) -> cons x (h xs cons nil) [] -> nil from :: (a -> (forall r . (b -> r -> r) -> r -> r)) -> (a -> [b]) from f a = f a (:) []
        • NotAtWork 12y ago
          Thank you. That step had me really confused.
        • tel 12y ago
          The fast way is to say that [b] is the initial algebra of the functor (Maybe . (b,)) and then note that initial algebras are representable as newtype Mu f = Mu (forall r . (f r -> r) -> r)
          • DanWaterworth 12y ago
            Interesting. I'm not well versed in these things yet, but I've seen: forall r . (f r -> r) -> r before. Am I right in saying it's the type of a catamorphism? In which case, yes, it makes total sense that your `Mu` type is equivalent to the (possibly) more usual: newtype Mu f = Mu (f (Mu f))
            • tel 12y ago
              Yep! You can think of it as a "frozen catamorphism" or the "right half" of foldr when you specialize `f`. The really fascinating part is that my Mu is equivalent to your Mu in Haskell... because it's Turing complete. In a world where least and greatest fixed points differ, in a world where data and codata differ, then Mu has a cousin Nu data Mu f = Mu (forall r . (f r -> r) -> r) data Nu f = forall r . Nu (r -> f r) r where Mu generates the data and Nu generates the codata. You'll recognize Nu as a frozen anamorpism, of course. If you want a total language, replace generalized fixed points with these two pairs of fixed points. Mu only lets you construct things finitely and tear them down with catamorphisms and Nu only lets you destruct things finitely which you've built with anamorphisms. Even in Haskell you can treat certain uses of types as being data-like or codata-like by viewing them more preferentially through Mu or Nu---though you can always convert both to Fix newtype Fix f = Fix (f (Fix f))
• judk 12y ago
  This is typical of Closure, as a sort of anti-Haskell. It starts with empirical structures invented by folks without PL theory training, and then wriggles to find an explanation in terms of standard theory. You can see this here on HN when Rich talks to Haskell folks and people translate his writing into standard language. I would love a comparison in the form of Haskell, converted to Lisp syntax, and wired up to JVM.
  • presty 12y ago
    *Clojure
  • vorg 12y ago
    You relate Haskell to standard theory and Clojure to non-PL-theory structures. I think the real issue is that strongly-typed lazy functional code (Haskell) and dynamically-typed isomorphic code (Clojure, and Lisp) have an "impedance mismatch" such that they don't inter-translate very well. I think that's based on the different foundation of each language. Haskell is strongly typed and lazily evaluated, which easily enables functions to take only one argument at a time. Although a function could take a tuple parameter, it can be, and usually is, rewritten to take each component of the tuple as a separate parameter, which makes the strong typing and builtin currying simple, higher structures like monads possible, and the syntax can designed to suit this style. Lisp functions, on the other hand, must take many arguments at a time to cater to the isomorphicity of the language. It's therefore much more difficult for parameters to be typed, or to curry them. The syntax requires explicit visual nesting. Inter-translating between this style and the Haskell style therefore is difficult. I'd even suggest the Haskell and Lisp styles are two different peaks on the ladders of programming language abstraction, and the poster child of each, monads and macros, just don't interoperate very well, simply because of the different required foundations of each language.
    • tel 12y ago
      I don't find it difficult to intertranslate at all. Trivial actually: the currying is a complete non-issue. For pure, terminating code laziness/strictness hardly matters. And dear god do I wish people would stop abusing "isomorphic".
• moomin 12y ago
  Haskell beginner here: Re: the characterisation, the only thing I'd add is that they have explicit start and end calls. Start resets the state, end can clean up resources if necessary. I tried thinking about what output structure a generalised transducer would form, and came to the conclusion it was a foldable monoid i.e. pretty list-like.
  • tel 12y ago
    From what I've seen Transducers tend to use Clojure's ambient state mechanics to get local state to each "transduction step". If you want to do away with that then you can embed the state in a Fold (which is basically a Moore FSA) and then think of transducers as Fold transformers which aren't allowed to touch their output.
• gfodor 12y ago
  "fundamental as function composition" is obviously subjective, but I think the point is that it seems you can make a fairly strong argument that in lisps, there is a question of what does the form (map f) eval to, and transducers put forth an answer that seems to be logically correct and superior to any alternatives. Hence, it seems fundamental.
  • tel 12y ago
    I would suggest that there's a good chance that lenses (in particular, one subset of the general theory called Folds) are vastly more general.
• ludwigvan 12y ago
  I think the meaning is the following: Function composition usually operates at non-collection type inputs. If you compose f and g, that usually means f takes some input and then g takes as input the output of g. Transducers are a generalization of composition in the sense that it takes a collection of those inputs f would accepts. So, in that sense, function composition could be a specific instance of transducers with number of inputs = 1.
  • tel 12y ago
    It's much, much more of the opposite situation. Function composition can easily operate at collection type inputs---indeed, that is exactly how transducers operate. Transducers are a subset of functions. They cannot be generalizing them.