I've heard repeatedly about the interesting discovery that Boolean satisfiability is "hard in theory, but not in practice" because most constraint solving that we want to do inspired by real-world problems apparently has structure that software can identify.
But I also think this is an interesting challenge in its own right for thinking about polymorphism, even without getting into how to find opportunities to make the search non-exhaustive.
// Return an integer in the range [0, n) which
// causes execution to succeed.
unsigned amb(const unsigned n)
if (n == 0) _exit(42);
for (unsigned i = 0; i < n - 1; ++i)
const pid_t child = fork();
if (child < 0) abort();
if (child == 0) return i;
if (waitpid(child, &wstatus, 0) < 0) abort();
if (WIFEXITED(wstatus) && WEXITSTATUS(wstatus) == 0) _exit(0);
return n - 1;
You can make other fun time-traveling functions following the above pattern. My favorite I call the "Groundhog Day" function, or "Cause and Effect" for Star Trek fans: when first called, it returns zero; if the program later fails, it is restarted from that function call, which returns the exit code. (I'm not really sure how useful this is.)
I've been thinking about this a bunch. I put together a brain dump that I improve over time
It reminds me of riddles "what ends the first and starts the next for each"
As the page explains:
The goal of this task isn't to simply process the four lists of words with explicit, deterministic program flow such as nested iteration, to trivially demonstrate the correct output. The goal is to implement the Amb operator, or a facsimile thereof that is possible within the language limitations.
T Amb(params T l) => l;
var w1 = Amb("the", "that", "a");
The F# version... it's okay, I guess, but the fully-functional "declare all variables at the start, then filter" style is definitely easy mode. It's not really comparable to an 'Amb' that properly supports imperative code, letting you declare ambiguous variables, compute things with them, then use those computations to declare more ambiguous variables.
If I'm reading the page correctly, the task is to create a general Amb implementation and merely demonstrate it using the data provided, and not to create a solution that only works on data similar to the sample data.
So I don't believe any of the PureBasic, Rust, or F# solutions meet the requirements. Though since it's a wiki, someone might have gone in and edited/added to the solutions after I wrote this. :)
In comparison, the class-based C# solutions are a lot more verbose but appear to actually solve the problem that was defined.
Anyway, the F# code, IIUC, lets you do exactly what you want it to do, although you'd have to replace the ifs with guards.
The Purebasic solution depends on the operands being strings, and the F# solution depends on them being sequences. And the way that the 'Ambassert' works in both of them is hardcoded, too.
Since the problem was 'create an Amb implementation and demonstrate it using the data below' and not 'create an Amb-like thing that can only solve for cases where the operands are strings/sequence and the last item in operand 1 must match the first item in operand 2', I believe that the C# solutions actually solve the problem, while the Purebasic and F# solutions do not.