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

Type-safe Transducers in Clojure, Scala, and Haskell

blog.podsnap.com

Post reply on HN
Print view View original

1–10 of 13 posts

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#2

Post by brandonbloom »

This is interesting, but it's still missing some very important features of transducers. As you alluded, stateful operations [1] won't work at all in your Haskell model. Also, you've missed early termination [2], which Rich's talk [3] covered well.

[1] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff...

[2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff...

[3] https://www.youtube.com/watch?v=6mTbuzafcII

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#4

Post by wyager »

brandonbloom wrote: post #2

This is interesting, but it's still missing some very important features of transducers. As you alluded, stateful operations [1] won't work at all in your Haskell model. Also, you've missed early termination [2], which Rich's talk [3] covered well. [1] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [3] https://www.youtube.com/watch?v…

>As you alluded, stateful operations [1] won't work at all in your Haskell model.

Couldn't you just parametrize over IO/ST/etc.? E.g. something like

    IO r -> a -> IO r
I don't have a great mental model of transducers yet, so I'm not confident about that.

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#5

Post by jules »

wyager wrote: post #4
brandonbloom wrote: post #2

This is interesting, but it's still missing some very important features of transducers. As you alluded, stateful operations [1] won't work at all in your Haskell model. Also, you've missed early termination [2], which Rich's talk [3] covered well. [1] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [3] https://www.youtube.com/watch?v…

>As you alluded, stateful operations [1] won't work at all in your Haskell model. Couldn't you just parametrize over IO/ST/etc.? E.g. something like IO r -> a -> IO r I don't have a great mental model of transducers yet, so I'm not confident about that.

You can do that, but it's more elegant if you define a functional stateful transducer analogous to scanl for lists.

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#6

Post by frowaway001 »

kentosi wrote: post #3

This line made me laugh out loud: "... whenever something is even slightly ugly in Scala, you introduce an implicit to make it confusing instead."

Odersky wrote a simple implementation, and it looks a lot nicer. It also doesn't use any casts or implicit conversaions: https://gist.github.com/odersky/6b7c0eb4731058803dfd

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#7

Post by [deleted] »

jules wrote: post #5
wyager wrote: post #4

Earlier quoted context omitted.

>As you alluded, stateful operations [1] won't work at all in your Haskell model. Couldn't you just parametrize over IO/ST/etc.? E.g. something like IO r -> a -> IO r I don't have a great mental model of transducers yet, so I'm not confident about that.

You can do that, but it's more elegant if you define a functional stateful transducer analogous to scanl for lists.

[deleted]

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#8

Post by davdar »

jules wrote: post #5
wyager wrote: post #4

Earlier quoted context omitted.

>As you alluded, stateful operations [1] won't work at all in your Haskell model. Couldn't you just parametrize over IO/ST/etc.? E.g. something like IO r -> a -> IO r I don't have a great mental model of transducers yet, so I'm not confident about that.

You can do that, but it's more elegant if you define a functional stateful transducer analogous to scanl for lists.

That's like saying "your program is more elegant if it has no monads". It's an incorrect statement. The monadic version is perfectly elegant. Even better: it's the right one.

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#9

Post by podsnap »

brandonbloom wrote: post #2

This is interesting, but it's still missing some very important features of transducers. As you alluded, stateful operations [1] won't work at all in your Haskell model. Also, you've missed early termination [2], which Rich's talk [3] covered well. [1] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [3] https://www.youtube.com/watch?v…

There's more missing than that, but, in the spirit of early termination, I had to stop somewhere! Specifically to your points: 1. To preempt the faithful: Stateful transducers don't work (for a broad definition of work) in Clojure or Scala either. It's just that there's no tradition of acknowledging state via type in those languages. 2. Early termination is weird. In Clojure it's a property of the accumulated reduction value, i.e. not the transducer, the reducing function or the reducer/collection. I'm not sure yet whether to try modeling this via type or to try sticking it somewhere else. 3. Rich's talk is great. Also, it's been transcribed: https://github.com/matthiasn/talk-transcripts/blob/master/Hi...

Re: Type-safe Transducers in Clojure, Scala, and Haskell

#10

Post by tel »

wyager wrote: post #4
brandonbloom wrote: post #2

This is interesting, but it's still missing some very important features of transducers. As you alluded, stateful operations [1] won't work at all in your Haskell model. Also, you've missed early termination [2], which Rich's talk [3] covered well. [1] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [3] https://www.youtube.com/watch?v…

>As you alluded, stateful operations [1] won't work at all in your Haskell model. Couldn't you just parametrize over IO/ST/etc.? E.g. something like IO r -> a -> IO r I don't have a great mental model of transducers yet, so I'm not confident about that.

You can just include local state.

    data Fold i o = forall st . Fold
      { merge :: st -> i -> st
      , this  :: st
      , view  :: st -> o
      }

    type (i ~> o)  = forall r . Fold o r      -> Fold i r
    -- compare
    type Trans i o = forall r . (r -> o -> r) -> (r -> i -> r)
Now each "step" has local pure state and no other step can break abstraction barriers and view it. This also gives you all of the effects of the indexed state passing Rich called untypeable.

Fold is equivalent to an infinite state Moore machine, so a stack of composed transducers applied to a base Moore machine which produces whatever result you want can be compiled a really efficient form.

Early termination can be done by changing `merge` to `merge :: st -> i -> Either o st`.

Post reply on HN