4 ms·

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 Haske

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/b01adb859c66322c5cff1ca9dc1ad98585f2cdc1/src/clj/clojure/core.clj#L2719-L2744 https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [2] https://github.com/clojure/clojure/blob/b01adb859c66322c5cff1ca9dc1ad98585f2cdc1/src/clj/clojure/core.clj#L2694-L2698 https://github.com/clojure/clojure/blob/b01adb859c66322c5cff... [3] https://www.youtube.com/watch?v=6mTbuzafcII https://www.youtube.com/watch?v=6mTbuzafcII

wyager 12y ago
>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.
- jules 12y ago
  You can do that, but it's more elegant if you define a functional stateful transducer analogous to scanl for lists.
  - deleted 12y ago
    [deleted]
  - davdar 12y ago
    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.
    - jules 12y ago
      By the same logic scanl should just have the type: (b -> IO a) -> [b] -> IO [a] instead of (a -> b -> a) -> a -> [b] -> [a] Just putting the whole thing in the IO/ST monad isn't the right solution when you need a very specific form of local state.
- tel 12y ago
  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`.
podsnap 12y ago
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/Hickey_Rich/Transducers.md https://github.com/matthiasn/talk-transcripts/blob/master/Hi...
- tel 12y ago
  See here for points (1) and (2): https://news.ycombinator.com/item?id=8532710 https://news.ycombinator.com/item?id=8532710

wyager 12y ago

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

jules 12y ago
You can do that, but it's more elegant if you define a functional stateful transducer analogous to scanl for lists.
- deleted 12y ago
  [deleted]
- davdar 12y ago
  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.
  - jules 12y ago
    By the same logic scanl should just have the type: (b -> IO a) -> [b] -> IO [a] instead of (a -> b -> a) -> a -> [b] -> [a] Just putting the whole thing in the IO/ST monad isn't the right solution when you need a very specific form of local state.
tel 12y ago
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`.

podsnap 12y ago

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/Hickey_Rich/Transducers.md https://github.com/matthiasn/talk-transcripts/blob/master/Hi...

tel 12y ago
See here for points (1) and (2): https://news.ycombinator.com/item?id=8532710 https://news.ycombinator.com/item?id=8532710