3 ms·
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 n
by tel 12y ago
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 -> Maybe r)
ztake n f1 = run n where
run n result input =
let n' = n - 1
result = if n >= 0 then f1 result input else result
in if n' == 0 then Nothing else Just result
I wanted to post this mostly to note that `map` is mapping contravariantly here. Is there something I'm missing? I had that occurring when I was playing around with this idea before looking at the source as well... to fix it I had to consider the type `Red r a -> r` so that the `a` was covariant again.
- tel 12y agoAlso, 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) = (run n, z1) where run n result input = let n' = n - 1 result = if n >= 0 then f1 result input else result in if n' == 0 then z1 else result This has the theoretical niceness of having `Red r a` just be the signature functor for linked lists.
- tel 12y agoI'm also assuming transduce and sequence are something like this type RT r a b = Red r a -> Red r b sequence :: RT [a] a b -> [b] -> [a] sequence xform bs = transduce xform (flip (:)) [] bs transduce :: RT r a b -> (r -> a -> r) -> r -> [b] -> r transduce xform cons nil = let (cons', nil') = xform (cons, nil) in foldr (flip cons') nil' but I can't find the actual source yet. Again, there's a weird flipping going on induced by the contravariance. It makes me want to define RT-composition backwards.
- riwsky 12y agoDoesn'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.
- tel 12y agoYeah, I'm working through it in more depth now (I just fired this off last night quickly without a lot of thought). There's more to be said about take. My implementation here totally does not work.
- tel 12y agoHere's how to work it without even using the state monad: https://news.ycombinator.com/item?id=8149200 https://news.ycombinator.com/item?id=8149200 It's quite a bit different from this formulation.
- kenko 12y agoMay be worth linking back to this here: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/ http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...