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

Transducers are coming to Clojure

blog.cognitect.com

Post reply on HN
Print view View original

91–100 of 103 posts

Re: Transducers are coming to Clojure

#91

Post by malisper »

taliesinb wrote: post #48
jamii wrote: post #43

Earlier quoted context omitted.

So if I understand correctly, you would arrive at a symbolic expression like (->> (map f) (map g) x) and directly rewrite it to (->> (map (f . g)) x), rather than having to manipulate the resulting data-structures?

Yeah, it's pretty easy to turn Map[#^2&] /* Select[PrimeQ] /* Select[OddQ] into Select[OddQ[#] && PrimeQ[#]&] /* Map[#^2&] and so on via rules that look like: Select[s1_] /* Select[s2_] :> Select[s1[#] && s2[#]&] Map[f_ ? SideEffectFreeQ] /* s_Select :> s /* Map[f] Map[Extract[p_Integer | p_Key]] :> Extract[{All, p}] I'm already doing a bunch of that for Dataset. But in reality you need to move to a DSL for complex e…

I don't know about Clojure, but Common Lisp provides something called Compiler Macros[0]. They basically allow the programmer to define two versions of a procedure. One that is a macro, and one that is an actual procedure. The macro will expand only at compile time (it can also specify to call the procedure instead of expanding), and the procedure will be called only at run time. I suggest you look at [0] for some examples of how it is possible to optimize something as simple as squaring a number.

[0] http://clhs.lisp.se/Body/m_define.htm

Re: Transducers are coming to Clojure

#92

Post by kenko »

tel wrote: post #71
tel wrote: post #70

Earlier quoted context omitted.

Interesting. Continuing to try to analyze these in Haskell, I think this is a direct translation: -- z is just there to not clobber some standard prelude names type Red r a = r -> a -> r zmap :: (b -> a) -> Red r a -> Red r b zmap f f1 result input = f1 result (f input) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p f1 result input = if p input then f1 result input else result ztake :: Int -> Red r a -> (r -> a -…

Also, you can get rid of the sentinel value by packing along a termination continuation value as well: type Red r a = (r -> a -> r, r) zmap :: (b -> a) -> Red r a -> Red r b zmap f (f1, z1) = (\result input -> f1 result (f input), z1) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p (f1, z1) = (\result input -> if p input then f1 result input else result, z1) ztake :: Int -> Red r a -> Red r a ztake n (f1, z1) = (r…

May be worth linking back to this here: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...

Re: Transducers are coming to Clojure

#93

Post by avernet »

wyager wrote: post #53
tel wrote: post #13

This sort of reminds me of the Church-encoded form of a list. newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r) fold :: [a] -> Fold a fold xs = Fold (spin xs) where spin [] cons nil = nil spin (a:as) cons nil = cons a (spin as cons nil) refold :: Fold a -> [a] refold (Fold f) = f (:) [] Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a` map :: (a -> b…

For those curious a about this, look up Haskell's `build` and `destroy` functions. Those functions are for church-encoding lists and doing optimizations that way.

Here is a link:

http://www.haskell.org/haskellwiki/Correctness_of_short_cut_...

Re: Transducers are coming to Clojure

#94

Post by tel »

This is about as close as I could get in Haskell so far. It uses a slight twist on (x -> a -> x) called a Fold (which has a lot of great properties—it's a profunctor, an applicative, and a comonad).

Nicely, this construction lets us write `take` purely!

    {-# LANGUAGE GADTs         #-}
    {-# LANGUAGE RankNTypes    #-}
    {-# LANGUAGE TypeOperators #-}

    import           Control.Arrow
    import           Control.Category
    import qualified Prelude
    import           Prelude hiding (id, (.))

    data Fold a r where
      Fold :: (a -> x -> x) -> x -> (x -> r) -> Fold a r

    data Pair a b = Pair !a !b

    pfst :: Pair a b -> a
    pfst (Pair a b) = a

    psnd :: Pair a b -> b
    psnd (Pair a b) = b

    newtype (~>) a b = Arr (forall r . Fold b r -> Fold a r)

    instance Category (~>) where
      id = Arr id
      Arr f . Arr g = Arr (g . f)

    amap :: (a -> b) -> (a ~> b)
    amap f = Arr (\(Fold cons nil fin) -> Fold (cons . f) nil fin)

    afilter :: (a -> Bool) -> (a ~> a)
    afilter p = Arr $ \(Fold cons nil fin) ->
      let cons' = \a x -> if p a then cons a x else x
      in Fold cons' nil fin

    fold :: Fold a r -> [a] -> r
    fold (Fold cons nil fin) = fin . spin where
      spin []     = nil
      spin (a:as) = cons a (spin as)

    asequence :: (a ~> b) -> ([a] -> [b])
    asequence (Arr f) = fold (f (Fold (:) [] id))
    
    aflatmap :: (a -> [b]) -> (a ~> b)
    aflatmap f = Arr $ \(Fold cons nil fin) ->
      Fold (\a x -> foldr cons x (f a)) nil fin
    
    atake :: Int -> (a ~> a)
    atake n = Arr $ \(Fold cons nil fin) ->
      let cons' = \a x n -> if n > 0 then cons a (x (n-1)) else x n
      in Fold cons' (const nil) (\x -> fin (x n))

Re: Transducers are coming to Clojure

#95

Post by adambard »

oafitupa wrote: post #75

As someone who tried Clojure and failed, serious question: Does anyone actually use all these crazy features/patterns that keep getting added/discovered and talked about? I ask because even though I can imagine someone smart mastering these things and programming faster, I can't imagine a second person being able to understand his code, maintain it, and generally be productive. I imagine the second person losing a lo…

Something I've noticed about Clojure code is that people tend to have taken the effort to express a problem in a concise and logical way, even for very complex problems. I'm not sure if it's just because Clojure attracts people who value good code, or because Clojure provides the tools to do it, but it sure is nice. Better to spend an hour on a 5-line function than a 50-line one, if they accomplish the same thing in the end.

Re: Transducers are coming to Clojure

#96

Post by tel »

riwsky wrote: post #87
tel wrote: post #71

Earlier quoted context omitted.

Also, you can get rid of the sentinel value by packing along a termination continuation value as well: type Red r a = (r -> a -> r, r) zmap :: (b -> a) -> Red r a -> Red r b zmap f (f1, z1) = (\result input -> f1 result (f input), z1) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p (f1, z1) = (\result input -> if p input then f1 result input else result, z1) ztake :: Int -> Red r a -> Red r a ztake n (f1, z1) = (r…

Doesn't ztake need to live in State Int (or something similar)? As written, I don't see how it passes the 'n' onto the next call. It seems that the transducer returned by ztake n for any n > 1 will always pass on (f1 result, z1). Thank you for posting this though, helpful to see someone work through it.

Here's how to work it without even using the state monad: https://news.ycombinator.com/item?id=8149200

It's quite a bit different from this formulation.

Re: Transducers are coming to Clojure

#97

Post by oafitupa »

adambard wrote: post #95
oafitupa wrote: post #75

As someone who tried Clojure and failed, serious question: Does anyone actually use all these crazy features/patterns that keep getting added/discovered and talked about? I ask because even though I can imagine someone smart mastering these things and programming faster, I can't imagine a second person being able to understand his code, maintain it, and generally be productive. I imagine the second person losing a lo…

Something I've noticed about Clojure code is that people tend to have taken the effort to express a problem in a concise and logical way, even for very complex problems. I'm not sure if it's just because Clojure attracts people who value good code, or because Clojure provides the tools to do it, but it sure is nice. Better to spend an hour on a 5-line function than a 50-line one, if they accomplish the same thing in…

I don't think that 5-line function will be understandable by the next programmer who has to deal with it though. That's my point. It probably involves a Fibonacci or other math trickery that not everyone might have fresh in their minds.

Re: Transducers are coming to Clojure

#98

Post by FranklinChen »

richhickey wrote: post #16
graycat wrote: post #15

I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set…

a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)

More precisely:

  -- Left reduce
  type Reducer a r = r -> a -> r

  -- Here's where then rank-2 type is needed
  type Transducer a b = forall r . Reducer a r -> Reducer b r

Re: Transducers are coming to Clojure

#99

Post by davdar »

richhickey wrote: post #64
davdar wrote: post #61

Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.

I'm not yet seeing that, given: Signal a :: Time -> a SF a b :: Signal a -> Signal b thus (Time -> a) -> (Time -> b) not exactly: (x->a->x) -> (x->b->x) Can you point me to a paper that makes the connection clear?

In the non-continuous FRP literature[1], i.e. the kind you actually implement, SF a b = [a] -> [b], which is isomorphic to: Fold a -> Fold b, where Fold a = (exists s. (s, s -> (a, s))), which isomorphic to the type the author writes for transducer:

  ;;transducer signature
  (whatever, input -> whatever) -> (whatever, input -> whatever)
Signal functions are easy to program in Haskell using arrow syntax, and many libraries already exist for dealing with signal functions.

[1]: Nilsson, Courtney and Peterson. Functional Reactive Programming, Continued. Haskell '02. http://haskell.cs.yale.edu/wp-content/uploads/2011/02/worksh... (see section 4)

edit: formatting

Re: Transducers are coming to Clojure

#100

Post by bilus »

oafitupa wrote: post #97
adambard wrote: post #95

Earlier quoted context omitted.

Something I've noticed about Clojure code is that people tend to have taken the effort to express a problem in a concise and logical way, even for very complex problems. I'm not sure if it's just because Clojure attracts people who value good code, or because Clojure provides the tools to do it, but it sure is nice. Better to spend an hour on a 5-line function than a 50-line one, if they accomplish the same thing in…

I don't think that 5-line function will be understandable by the next programmer who has to deal with it though. That's my point. It probably involves a Fibonacci or other math trickery that not everyone might have fresh in their minds.

You may be mistaking patterns with 'clever hacks'. If the 5-liner is about writing the shortest possible code, then it certainly isn't beneficial to anyone (except for the original author who has all the fun of coming up with a 'clever' solution). But useful abstractions are a different matter whatsoever.

Just look at Go channels or at reactive programming patterns. If applied to the right problem (i.e. a problem they help solve), they allow you to solve the very problem in a very concise and expressive way.

Having such patterns as a part of the language just makes them more popular and reusable.

And as far as your point, don't you think it's easier to spot a 5-line pattern than a pattern that is spread out over several classes and 200 or so lines of code? It all boils down to this: being able to see patterns or abstractions if you know that and having a common language across the team. Functional 'patterns' are just (arguably) more succinct than object-oriented ones (and it comes from someone who has been programming in C++ and Ruby for nearly 20 years).

Post reply on HN