undefined | Better HN

0 pointslmm9y ago0 comments

The problem is that applicative functors aren't powerful enough to allow computations that depend on previous results. I suspect what we want is something like free ArrowChoice, but I'm not aware of any work in that direction.

0 comments

jfoutz9y ago

I might be completely missing your point (my apologies if i am).

applicative is for specific elements of the structure. It's totally reasonable to want access to nearby values, but that requires being a little bit tricky. You could do something like a window of averages

    windows = map (take 5) tails $ [1,2,3,4,5,6]

and then do your fmap across that

    fmap sum windows

For access to prior values, you need something that looks a lot more like a fold. In that kind of case, i'd point at traversable.

    mapAccumL (\val accumulator -> val + accumulator) 0 [1,2,3,4,5]

which would gather up the sums, [1, 3, 6, 10, 15]

of course, accumulator can be as fancy as you want, hashmap, set, tree, or whatever. If you can formulate a dynamic programming solution, there's generally a way to stuff that into traversable.

This is sort of off the top of my head and my haskell is a bit rusty, so this probably won't compile. But i think it captures the essence.

lmmOP9y ago

The trouble is that applicative doesn't let you use the result of one effect to compute the next effect. (Indeed sometimes there is no there there: Const is a valid applicative). Monads have bind, but that's a little too powerful to implement efficiently. Like I said, I suspect ArrowChoice or the like might be the missing intermediate construct.

mbrock9y ago

You can still do a lot with applicatives, like parsing context-free languages... and even parsing context-sensitive languages.

https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...

But yeah.

ApplicativeDo might be useful. You would be able to see the static applicative structure as far as the next monadic bind, which lets you do interesting types of optimization, e.g. Haxl.

https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo

https://github.com/facebook/Haxl

lmmOP9y ago

The thing is we're used to thinking in monads, and used to thinking of certain constructs as equivalent, which ApplicativeDo would break. There's a real tension between being explicit about the performance - in which case many identities no longer hold - and not. I don't know what Haxl itself does, but Fetch (which claims to be a Scala port) is kind of unsatisfactory in that regard.

rtpg9y ago

AplicativeDo solves this a little bit through using Applicative until the results are necessary for the next instruction, then opting for Monad instances

lmmOP9y ago

Right, but at that point you're no longer Free. (Unless you declare the inefficient implementation and the efficient implementation to be equivalent, but if you do that then every refactor risks destroying your performance).

j / k navigate · click thread line to collapse

0 comments

jfoutz9y ago

I might be completely missing your point (my apologies if i am).

    windows = map (take 5) tails $ [1,2,3,4,5,6]

and then do your fmap across that

    fmap sum windows

For access to prior values, you need something that looks a lot more like a fold. In that kind of case, i'd point at traversable.

    mapAccumL (\val accumulator -> val + accumulator) 0 [1,2,3,4,5]

which would gather up the sums, [1, 3, 6, 10, 15]

of course, accumulator can be as fancy as you want, hashmap, set, tree, or whatever. If you can formulate a dynamic programming solution, there's generally a way to stuff that into traversable.

This is sort of off the top of my head and my haskell is a bit rusty, so this probably won't compile. But i think it captures the essence.

lmmOP9y ago

mbrock9y ago

You can still do a lot with applicatives, like parsing context-free languages... and even parsing context-sensitive languages.

https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...

But yeah.

ApplicativeDo might be useful. You would be able to see the static applicative structure as far as the next monadic bind, which lets you do interesting types of optimization, e.g. Haxl.

https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo

https://github.com/facebook/Haxl

lmmOP9y ago

rtpg9y ago

AplicativeDo solves this a little bit through using Applicative until the results are necessary for the next instruction, then opting for Monad instances

lmmOP9y ago

j / k navigate · click thread line to collapse