Implement Amb and Require
Scala, 406/377 Bytes
I offer two golfed versions of my implementation, one that chooses the value randomly and one that (somehow) abuses the task description and always returns the first legal value. It's up to you, with one to consider (the latter one is shorter, obviously):
trait A[X]{def g=scala.util.Random.shuffle(l).head;def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e<-a.l;f<-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=>Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}
trait A[X]{def g=l(0);def l:Seq[X];def -(d:X)};class M{def a[X](e:Seq[X])=new A[X]{var s=e;def l=s;def -(d:X)=s=s.filter(_!=d)};def r(v:A[Boolean])=v-false;def p[X,Y](a:A[X],b:A[Y])=new A[(X,Y)]{var x=List[Any]();def l=(for(e<-a.l;f<-b.l)yield(e,f)).diff(x);def -(d:(X,Y))=x::=d};def o[X,Y](v:A[X],f:X=>Y)=new A[Y]{def l=v.l.map(f);def -(d:Y)=v.l.filter(f(_)==d).foreach(v.-)}}
This versions are more or less just golfed versions of my initial submission (some implementations have changed slightly, but the interfaces were quite stable). Therefore I will not explain it any further but refer to my initial post. Just have in mind that everything that was "for convenience" now disappeared. And a lot of renaming happened. The only difference is that pairs are now a bit like new amb-values: If you define conditions on top of pairs this will never effect the underlying values (nevertheless, manipulating the underlying values will still affect the pairs).
To give you a hint on how to use this versions, here is a short testing code I used while golfing:
val m = new M
val a1 = m.a(List(1, 2, 3, 4, 5))
val a2 = m.a(List(4, 5, 6))
val a12 = m.p(a1, a2)
m.r(m.o(a12, (p:(Int, Int)) => p._1 > p._2))
m.r(m.o(a1, (e: Int) => e%2==1))
println(a1.l)
println(a2.l)
println(a12.l)
println(a12.g)
As you can see, the offered functions are now instance-methods, hence, you need an instance of M to interact with my library (this saved me one glorious byte).
Note that my ungolfed version (which I will not update any more) now includes natural syntax for the most common Int- and Boolean-operations.
(my initial submission)
Right before posting this answer the Mathematica answer was stated and it looks as if my solution is based on similar assumptions. Nevertheless, I will offer my solution, too, because I didn't copied the former answer as it wasn't there when I started.
I didn't tried to recreate a natural syntax (like: (amb(1, 2, 3) + 3) * 5, etc), but this would be possible if you like to implement the necessary implicit conversions. I chose the functional way as you will see later.
Let's start with the two keywords:
import ambiguous.AmbOps.op
object Amb {
def amb[A](args: A*): AmbType[A] =
new BasicAmb[A](args.toList)
def require(amb: AmbType[Boolean]): Unit =
amb.del(false)
def require[A](amb: AmbType[A], predicate: A => Boolean): Unit =
require(op(amb, predicate))
def require[A, B](amb: AmbType[(A, B)], predicate: (A, B) => Boolean): Unit =
require(op(amb, predicate))
}
The amb-method is quite straight forward, you provide some values and get some container, that may return a value back (more on that later). I offer three require methods but they are all based on the first one, so the others are just for convenience. Let me explain the first one (the others will become clear as you read on): If you have some boolean amb-Container and call require, all false values are eliminated.
But how is an amb-value of arbitrary type converted into a boolean value? By offering a conversion-policy:
object AmbOps {
def op[A, B](amb: AmbType[A], op: A => B): AmbType[B] =
new OpAmb[B, A](amb, op)
def op[A, B, C](amb: AmbType[(A, B)], op: (A, B) => C): AmbType[C] =
new OpAmb[C, (A, B)](amb, p => op(p._1, p._2))
def pair[A, B](ambA: AmbType[A], ambB: AmbType[B]): AmbType[(A, B)] =
new AmbPair[A, B](ambA, ambB)
}
Assume we have some numerical amb-value and want to square each element, then just call op with a corresponding function: op(amb(1, 2, 4), (e: Int) => e * e) // returns a value equivalent to amb(1, 4, 16) Following the same scheme you can convert the elements to boolean values for example with op(amb(1, 2, 4), (e: Int) => e%2 == 0)
If you have several amb-values and you want to define conditions between them, it isn't that easy to do with my approach when only using amb, require and op. Therefore I defined the method pair. With pair you can create tuples/pairs out of two amb-values (or any number if you again pair pairs with other values or pairs). If you then define conditions on top of this tuples, the illegal pairs will be eliminated. But the original values aren't always manipulated. Only if this process leads to the situation that one element from one of the initial amb-values is no longer legal in any tuple, than this value is completely eliminated from the initial amb-value. If now some other amb-value (or pair) is based on this manipulated amb-value, the dependent value will also miss the deleted element.
That means that if you need a pair of values fulfilling a condition, you have to get an element from the pair-value and you cannot always rely on the original values, but I think this is a acceptable limitation.
Just for convenience there is an additional op-method for tuples.
Now we have to dig deeper into the technical details of the amb-containers:
import scala.util.Random
trait AmbType[A] {
def get: A = {
if (list.isEmpty)
throw new IllegalStateException("no value left")
else list(Random.nextInt(list.length))}
private[ambiguous] def list: List[A]
private[ambiguous] def del(a: A): Unit
}
class BasicAmb[A](private var args: List[A]) extends AmbType[A] {
override private[ambiguous] def list: List[A] = args
override private[ambiguous] def del(a: A): Unit = { args = args.filterNot(_ == a)}
}
class OpAmb[A, B](amb: AmbType[B], op: B => A) extends AmbType[A] {
override private[ambiguous] def list: List[A] = amb.list.map(op)
override private[ambiguous] def del(a: A): Unit = amb.list.filter(op(_) == a).foreach(amb.del)
}
class AmbPair[A, B](ambA: AmbType[A], ambB: AmbType[B]) extends AmbType[(A, B)] {
private var deleted: List[(A, B)] = List()
override private[ambiguous] def list: List[(A, B)] =
ambA.list.flatMap(a => ambB.list.map(b => (a, b))).diff(deleted)
override private[ambiguous] def del(a: (A, B)): Unit = {
deleted ::= a
ambA.list.filter(a => !list.exists(_._1 == a)).foreach(a => {ambA.del(a); deleted = deleted.filterNot(_._1 == a)})
ambB.list.filter(b => !list.exists(_._2 == b)).foreach(b => {ambB.del(b); deleted = deleted.filterNot(_._2 == b)})
}
}
I don't want to say too much about the classes but one thing is worth mentioning: If you create pairs of two amb-values and define some conditions on top of them and afterwards define some further conditions on top of one of the original values, the pair-class misses to check if an element of the not-changed original value may be deleted as it doesn't appear as part of one pair any more. So some further observer-pattern would be great.
Now let's take a look on how to use this:
// create amb-values by invoking amb
val a = amb(1, 2, 3, 4)
// do some maths on a value
val b = op(a, (e: Int) => e + 2)
// define some conditions
require(b, (e: Int) => e%3 == 0)
// or first apply the condition to the value and afterwards pass the value to require
val filtered = op(b, (e: Int) => e%3 == 0)
require(filtered)
// pair values
val paired = pair(a, amb("hello", "welcome"))
// note that the amb-value a now only contains the elements 1 and 4 as the former requirement eliminated the other two
// state a condition on pairs
require(paired, (a: Int, b: String) => b.length % a == 0)
// now the amb-value a only contains the element 1 as there was no string with length divisible by 4
// query a value from our pairs (by calling get)
val selected = paired.get
// at this point only two pairs are left, so selected will always be either (1, "hello") or (1, "welcome")
val number = selected._1
val greetings = selected._2