amb without side-effects can also be expressed in terms of the List monad, e.g.:
do x <- [1, 2, 3]
y <- [4, 5, 6]
if x * y == 8 then pure (x, y)
else []
which can be equivalently reworded as the list comprehension:
[(x, y) | x <- [1, 2, 3], y <- [4, 5, 6], x * y == 8]
i.e., the underlying structure of amb without side-effects can also be understood as just a search of the input space for values that fulfill some criteria, rather than as backtracking via continuations.
This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this.
`amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so the the error return does not need to be expressed explicitly. You may think that is good or bad but it is not the same as the Haskell solution.
We can implement it with a single `amb` function, too (I took some shortcuts that might have hidden some of the nature of the implementation)!
-- Lifts a list into Amb.
amb :: [a] -> Amb a
If we assume Amb is just List, then:
amb = id
If we write the example in the original article in desugared style, we get:
amb [1, 2, 3] >>= \x ->
amb [4, 5, 6] >>= \y ->
if x * y /= 8 then amb [] else pure () >>
pure (x, y)
(we are forced to use an awkward condition with `pure ()` on the else branch when calling `amb` because Haskell requires us to return values on all branches. We can rewrite it equivalently in terms of `when` to hide that detail:
amb [1, 2, 3] >>= \x ->
amb [4, 5, 6] >>= \y ->
when (x * y /= 8) (amb []) >>
pure (x, y)
It now looks more similar to the original example.)
It ends up looking like continuation-passing style: conceptually, if we encounter `amb []` in the nested function, the nested computation ends and we start examining the next value in the list values being assigned to `x`: the implementation given in the original post does end up using callcc, so with some imagination you might be able to derive some kind of equivalence here :)
What is magical and mind-bending about `amb` is that it rewinds through arbitrary complicated call stacks, similar to an exception. This is why it's necessarily a special form.
The Haskell version requires each callee to be annotated with the `Amb` return type. It cannot be used to escape unless the caller is prepared for it to escape. That's a significant limitation (but all we're really saying is that Haskell doesn't support call/cc).
In Haskell monads, you define a monadic type and then "bind" is the function that does something specific for that type. "It's a type" because Haskell uses static types and polymorphism to factor out common logic used by different functions.
Of course Haskell list is a built-in type, but it's not magical except for the special bracket syntax. You can make a sugar-free user-defined type
Yes, I know all of that. I wasn't saying it was magical, I was saying that in that particular code "amb expressed in terms of the List monad" is an accurate description, but "amb function" isn't really true. The monad is doing 100% of the ambiguous operation and the "amb function" does 0%.
As an analogy let's say I define "(" to do write to stdout, and "print" as id. Even though "print(4)" works as expected, my "print function" is a lie.
Or in C source code where adjacent strings get merged, I could [#define CONCAT ] so that ["ab" CONCAT "cd"] gets preprocessed to ["ab" "cd"] and parsed as ["abcd"]. But I didn't actually write a concatenation operator. The concatenation happens because of something else, it would happen even if you didn't use CONCAT, and you can sprinkle CONCAT all over your source code with no effect.
Hmmm, I think there is some subtlety here in terms of the way an empty list is used in Haskell. This paper by Wadler from the 80s (predating monads) discusses the functional lore of the combinator approach to parsing, and it significantly leverages the properties of [] to represent failure. It's a "semipredicate" type of situation, where the return value is either a list or failure; conveniently, the empty list isn't one of the possible success values. So if I understand the Haskell idiom correctly, it's a bit of a hack which is inherent in the heritage of the list monad. (NB there's nothing about raw lists per se that means they form a nondeterministic choice monad—that's a culturally contingent Haskell thing.)
It's an arbitrary choice in the Prelude, yes. If you don't like it you can definitely your own Cons type (or wrap a list in a new type) and define any monad instance (semantics) you choose.
Cons/lists don't have to be involved at all: a Set type could be made to work for many applications.
I've observed several smart people struggling at the outset with the connection between recursively defined lists and nondeterminism in Haskell. It's not uncommon for people to assume that there is some essential connection between the two, because that's what "list monad" seems to suggest. In fact any collection type would do.
