runCut creates exponential right-nested branches about fused-effects HOT 8 CLOSED

For lots of related strategies, see “Heuristics Entwined with Handlers Combined. Tom Schrijvers and Nicolas Wu and Benoit Desouter and Bart Demoen.”

from fused-effects.

Unfortunately, I think this means that we have to couple Cut carriers with search strategies. In particular, while it’s possible to use runCut with runNonDetOnce without accruing this cost (because the right-nested branches are never explored), it isn’t possible to compose it with runNonDet without paying this penalty.

An alternative carrier for Cut which explores all branches is possible, and can then be reinterpreted into some other Alternative instance, but you can’t compose this with runNonDetOnce to limit the search; since it has to explore the branches, their effects end up being performed:

λ runM (runTraceByPrinting (runNonDetOnce (runCutAll (pure 'a' <|> trace "hello" *> pure 'b'))))
hello
"a"

from fused-effects.

I was mistaken—we just need to represent actual branches in Branch.

from fused-effects.

@zenzike: Thank you! I’m really enjoying that paper ❤️

from fused-effects.

I usually distinguish between cut and call, where cut signals that siblings that proceed it under a call need to be removed, and cull, which picks only the first child in p

from fused-effects.

@zenzike: That’s super interesting. I kind of think that suggests we should hold off on releasing 0.1.2.0 until we’ve explored that.

from fused-effects.

Right. You can only do that sort of thing if alternation is a deep embedding. I usually define:

data Nondet k = Or k k

specifically for that purpose.

from fused-effects.

I’ve filed #68 to capture exploring that 👍

from fused-effects.