Expand failure tracking in NonDet

[michaelpj]

NonDets ability to track where you hit empty is quite nice, and helps with a classic problem of non-deterministic searches: knowing why you failed to find a solution.

However, the current approach only gives you call stacks. It would be nice in many cases to give a human-readable message or error.

I'm not really sure what the right design here is. The current version requires altering the calls to empty, which is a bit awkward and requires writing custom versions of Alternative functions. I wonder if we could do something like:

• Add extra failure context to Empty.
• empty sets empty failure context
• Users can use interpose to add failure context to any failures within a lexical scope

[arybczak]

A somewhat simpler approach: since call stacks from empty are more or less useless and you have to use emptyEff, perhaps it would be enough if emptyEff (and hence Empty) took a String as an argument and runNonDet returned Either (CallStack, String) a?

I guess hardcoded Stringas a type could be limiting.

[michaelpj]

Yeah, I guess it would be neat if you effectively had an "error" type associated with it that got "thrown" from empty. That's what's happening under the hood anyway.

I guess the thing that would be neat would be if there was a mapError equivalent, so empty could throw some default member of the error type and then you could modify it outside, e.g.

g <- mapError (const "Failed to pick a thing") $ afromList things

[ocharles]

Which starts looking a lot like <?> from parser combinators 😄

[arybczak]

Somewhat related: haskell/core-libraries-committee#301