Define relations via constrained iterations, and introduce a `suchthat` keyword to use them

Today when you write a list comprehension (from expression) the relations are defined by set expressions, but with this proposal you could also define a relation using a boolean function.

Suppose we have functions empsInDept and empWorksIn:

val empsInDept = fn:
  {deptno: int, dname: string} -> list {empno: int, ename: string}
val empWorksIn = fn:
 {empno: int, ename: string} * {deptno: int, dname: string} -> bool

Today you can write

from d in depts,
    e in deptEmps d
  yield e.ename ^ " works in " ^ d.dname

and it calls deptEmps for each d value to generate a list of e values. But with this proposal, you would be able to go the other way:

from d in depts,
    e suchthat empWorksIn (e, d)
  yield e.ename ^ " works in " ^ d.dname

To a mathematician, both are valid ways to define a set. But to a computer scientist the bool function is trickier to work with, because you have to work backwards and 'solve for e'.

In some cases it's not possible to work backwards. For example, given a function isEven,

fun isEven n =
  n mod 2 = 0;

we don't allow iterating over all even numbers:

from i suchthat isEven i

With this change, however, we will allow the use of such functions if some other part of the from expression provides a finite list of values:

from e in emps,
  i suchthat i = e.deptno andalso isEven i

Defining relations by means of predicates, and executing queries by 'solving' to find all possible values of variables for which the predicates evaluate to true, is what Datalog does. This change will bring Datalog-style computations into Morel. See #106.

hydromatic / morel

Define relations via constrained iterations, and introduce a `suchthat` keyword to use them #129