3 ms·
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 l
by rfw 8y ago
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 :)
- Dylan16807 8y agoThat's not an amb function. That's a builtin type that's inherently amb-y. You still get credit for solving the basic problem but let's not be misleading. Also don't forget to call head.
- hopler 8y agoIn 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 data List a = Nil | Cons a (List a) if you want.
- Dylan16807 8y agoYes, 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.
- millstone 8y agoWhat 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).