Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Clojure's Transducers are as fundamental as function composition

thecomputersarewinning.com

Post reply on HN
Print view View original

11–20 of 49 posts

Re: Clojure's Transducers are as fundamental as function composition

#11

Post by moomin »

lkrubner wrote: post #3
moomin wrote: post #2

If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.

The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do some…

The thing is, it's something of a redefinition of what idiomatic clojure is. Overloading arity to do radically different things isn't idiomatic Clojure, but transducers do it at two levels. Equally, functions are expected to do explicit state passing e.g. old school drop, rather than implicit state e.g transducer drop.

Re: Clojure's Transducers are as fundamental as function composition

#12

Post by moomin »

tel wrote: post #5

What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded f…

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.

Re: Clojure's Transducers are as fundamental as function composition

#13

Post by jeremyjh »

seanmcdirmid wrote: post #6
Tuna-Fish wrote: post #4

Earlier quoted context omitted.

In languages with more leeway on execution order, this problem can be made to go away. For example, Haskell's stream fusion combines back-to-back calls to list processing functions into a single iteration over the list.

Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.

Uh, sure but does any other language have a compiler that actually implements stream fusion?

Re: Clojure's Transducers are as fundamental as function composition

#14

Post by tel »

moomin wrote: post #10
kazinator wrote: post #8

Earlier quoted context omitted.

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…

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...

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.

Re: Clojure's Transducers are as fundamental as function composition

#15

Post by tel »

moomin wrote: post #12
tel wrote: post #5

What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded f…

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.

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.

Re: Clojure's Transducers are as fundamental as function composition

#16

Post by DanWaterworth »

tel wrote: post #14
moomin wrote: post #10

Earlier quoted context omitted.

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...

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 y…

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 (:) []

Re: Clojure's Transducers are as fundamental as function composition

#17

Post by DanWaterworth »

jeremyjh wrote: post #13
seanmcdirmid wrote: post #6

Earlier quoted context omitted.

Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.

Uh, sure but does any other language have a compiler that actually implements stream fusion?

I don't believe GHC actually does implement stream fusion. I think stream fusion happens with rewrite rules.

Re: Clojure's Transducers are as fundamental as function composition

#19

Post by NotAtWork »

DanWaterworth wrote: post #16
tel wrote: post #14

Earlier quoted context omitted.

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 y…

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 (:) []

Thank you.

That step had me really confused.

Re: Clojure's Transducers are as fundamental as function composition

#20

Post by riffraff »

DanWaterworth wrote: post #17
jeremyjh wrote: post #13

Earlier quoted context omitted.

Uh, sure but does any other language have a compiler that actually implements stream fusion?

I don't believe GHC actually does implement stream fusion. I think stream fusion happens with rewrite rules.

pardon my ignorance, but what would be the difference between the two? Don't rewrite rules happen in GCH anyway?
Post reply on HN