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

[julianhyde]

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.

[julianhyde]

suchthat should be lower case, not camel case (suchThat) as originally proposed. Other languages have keywords composed of multiple words: ML (andalso, infixl, infixr, orelse), Haskell (forall, newtype) Java (goto, instanceof, strictfp), Kotlin (typealias, typeof), Scala (forsome). Exceptions are Haskell's type family and type instance.