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

21–30 of 49 posts

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

#21

Post by gfodor »

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…

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

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

#22

Post by tel »

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

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)

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

#23

Post by presty »

judk wrote: post #9
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…

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…

*Clojure

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

#24

Post by dons »

Title shows author doesn't understand programming language design. No, a small set of higher-order functions[1] is not as fundamental as the concept of higher-order functions in the first place.

[1]: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...

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

#25

Post by ludwigvan »

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…

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.

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

#26

Post by DanWaterworth »

riffraff wrote: post #20
DanWaterworth wrote: post #17

Earlier quoted context omitted.

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?

Sorry, I should have been clearer. The rewriting happens in GHC, but it's the application programmer who creates the rules. So, stream fusion isn't implemented by the compiler AFAIK.

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

#27

Post by DanWaterworth »

tel wrote: post #22
DanWaterworth wrote: post #16

Earlier quoted context omitted.

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

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)

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

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

#28

Post by tel »

ludwigvan wrote: post #25
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…

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

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.

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

#29

Post by ithayer »

dons wrote: post #24

Title shows author doesn't understand programming language design. No, a small set of higher-order functions[1] is not as fundamental as the concept of higher-order functions in the first place. [1]: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...

Author here, thanks for the comment -- since that seemed to have been lost, I'm using "fundamental" because transducers let you describe your logic so that it that can be applied over sequences and non-sequences in a way that you cannot by just applying composed logic functions through existing clojure machinery.

EDIT: s/composed functions/composed logic functions/

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

#30

Post by tel »

DanWaterworth wrote: post #27
tel wrote: post #22

Earlier quoted context omitted.

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)

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

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))
Post reply on HN