Module Control.Search.SetFunctions

This module contains an implementation of set functions. The general idea of set functions is described in:

S. Antoy, M. Hanus: Set Functions for Functional Logic Programming Proc. 11th International Conference on Principles and Practice of Declarative Programming (PPDP'09), pp. 73-82, ACM Press, 2009

The general concept of set functions is as follows. If f is an n-ary function, then (setn f) is a set-valued function that collects all non-determinism caused by f (but not the non-determinism caused by evaluating arguments!) in a set. Thus, (setn f a1 ... an) returns the set of all values of (f b1 ... bn) where b1,...,bn are values of the arguments a1,...,an (i.e., the arguments are evaluated "outside" this capsule so that the non-determinism caused by evaluating these arguments is not captured in this capsule but yields several results for (setn...). Similarly, logical variables occuring in a1,...,an are not bound inside this capsule (in PAKCS they cause a suspension until they are bound).

Remark: Since there is no special syntax for set functions, one has to write (setn f) for the set function of the n-ary top-level function f. The correct usage of set functions is currently not checked by the compiler, i.e., one can also write unintended uses like set0 ((+1) (1 ? 2)). In order to check the correct use of set functions, it is recommended to apply the tool CurryCheck on Curry programs which reports illegal uses of set functions (among other properties).

The set of values returned by a set function is represented by an abstract type Values on which several operations are defined in this module. Actually, it is a multiset of values, i.e., duplicates are not removed.

The handling of failures and nested occurrences of set functions is not specified in the previous paper. Thus, a detailed description of the semantics of set functions as implemented in this library can be found in the paper

J. Christiansen, M. Hanus, F. Reck, D. Seidel: A Semantics for Weakly Encapsulated Search in Functional Logic Programs Proc. 15th International Conference on Principles and Practice of Declarative Programming (PPDP'13), pp. 49-60, ACM Press, 2013

Note that the implementation of this library uses multisets instead of sets. Thus, the result of a set function might contain multiple values. From a declarative point of view, this is not relevant. It has the advantage that equality is not required on values, i.e., encapsulated values can also be functional.

The PAKCS implementation of set functions has several restrictions, in particular:

  1. The multiset of values is completely evaluated when demanded. Thus, if it is infinite, its evaluation will not terminate even if only some elements (e.g., for a containment test) are demanded. However, for the emptiness test, at most one value will be computed
  2. The arguments of a set function are strictly evaluated before the set functions itself will be evaluated.
  3. If the multiset of values contains unbound variables, the evaluation suspends.

Author: Michael Hanus, Fabian Reck

Version: November 2022

Summary of exported operations:

set0 :: a -> Values a  Deterministic 
Combinator to transform a 0-ary function into a corresponding set function.
set1 :: (a -> b) -> a -> Values b  Deterministic 
Combinator to transform a unary function into a corresponding set function.
set2 :: (a -> b -> c) -> a -> b -> Values c  Deterministic 
Combinator to transform a binary function into a corresponding set function.
set3 :: (a -> b -> c -> d) -> a -> b -> c -> Values d  Deterministic 
Combinator to transform a function of arity 3 into a corresponding set function.
set4 :: (a -> b -> c -> d -> e) -> a -> b -> c -> d -> Values e  Deterministic 
Combinator to transform a function of arity 4 into a corresponding set function.
set5 :: (a -> b -> c -> d -> e -> f) -> a -> b -> c -> d -> e -> Values f  Deterministic 
Combinator to transform a function of arity 5 into a corresponding set function.
set6 :: (a -> b -> c -> d -> e -> f -> g) -> a -> b -> c -> d -> e -> f -> Values g  Deterministic 
Combinator to transform a function of arity 6 into a corresponding set function.
set7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> a -> b -> c -> d -> e -> f -> g -> Values h  Deterministic 
Combinator to transform a function of arity 7 into a corresponding set function.
isEmpty :: Values a -> Bool  Deterministic 
Is a multiset of values empty?
notEmpty :: Values a -> Bool  Deterministic 
Is a multiset of values not empty?
valueOf :: Eq a => a -> Values a -> Bool  Deterministic 
Is some value an element of a multiset of values?
chooseValue :: Eq a => Values a -> a  Non-deterministic 
Chooses (non-deterministically) some value in a multiset of values and returns the chosen value.
choose :: Eq a => Values a -> (a,Values a)  Non-deterministic 
Chooses (non-deterministically) some value in a multiset of values and returns the chosen value and the remaining multiset of values.
selectValue :: Values a -> a  Deterministic 
Selects (indeterministically) some value in a multiset of values and returns the selected value.
select :: Values a -> (a,Values a)  Deterministic 
Selects (indeterministically) some value in a multiset of values and returns the selected value and the remaining multiset of values.
getSomeValue :: Values a -> IO (Maybe a)  Deterministic 
Returns (indeterministically) some value in a multiset of values.
getSome :: Values a -> IO (Maybe (a,Values a))  Deterministic 
Selects (indeterministically) some value in a multiset of values and returns the selected value and the remaining multiset of values.
mapValues :: (a -> b) -> Values a -> Values b  Deterministic 
Maps a function to all elements of a multiset of values.
foldValues :: (a -> a -> a) -> a -> Values a -> a  Deterministic 
Accumulates all elements of a multiset of values by applying a binary operation.
filterValues :: (a -> Bool) -> Values a -> Values a  Deterministic 
Keeps all elements of a multiset of values that satisfy a predicate.
minValue :: Ord a => Values a -> a  Deterministic 
Returns the minimum of a non-empty multiset of values according to the given comparison function on the elements.
minValueBy :: (a -> a -> Ordering) -> Values a -> a  Deterministic 
Returns the minimum of a non-empty multiset of values according to the given comparison function on the elements.
maxValue :: Ord a => Values a -> a  Deterministic 
Returns the maximum of a non-empty multiset of values according to the given comparison function on the elements.
maxValueBy :: (a -> a -> Ordering) -> Values a -> a  Deterministic 
Returns the maximum of a non-empty multiset of values according to the given comparison function on the elements.
values2list :: Values a -> IO [a]  Deterministic 
Puts all elements of a multiset of values in a list.
printValues :: Show a => Values a -> IO ()  Deterministic 
Prints all elements of a multiset of values.
sortValues :: Ord a => Values a -> [a]  Deterministic 
Transforms a multiset of values into a list sorted by the standard term ordering.
sortValuesBy :: (a -> a -> Bool) -> Values a -> [a]  Deterministic 
Transforms a multiset of values into a list sorted by a given ordering on the values.

Exported datatypes:

Values

Abstract type representing multisets of values.

Constructors:

Exported operations:

set0 :: a -> Values a  Deterministic 

Combinator to transform a 0-ary function into a corresponding set function.

set1 :: (a -> b) -> a -> Values b  Deterministic 

Combinator to transform a unary function into a corresponding set function.

set2 :: (a -> b -> c) -> a -> b -> Values c  Deterministic 

Combinator to transform a binary function into a corresponding set function.

set3 :: (a -> b -> c -> d) -> a -> b -> c -> Values d  Deterministic 

Combinator to transform a function of arity 3 into a corresponding set function.

set4 :: (a -> b -> c -> d -> e) -> a -> b -> c -> d -> Values e  Deterministic 

Combinator to transform a function of arity 4 into a corresponding set function.

set5 :: (a -> b -> c -> d -> e -> f) -> a -> b -> c -> d -> e -> Values f  Deterministic 

Combinator to transform a function of arity 5 into a corresponding set function.

set6 :: (a -> b -> c -> d -> e -> f -> g) -> a -> b -> c -> d -> e -> f -> Values g  Deterministic 

Combinator to transform a function of arity 6 into a corresponding set function.

set7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> a -> b -> c -> d -> e -> f -> g -> Values h  Deterministic 

Combinator to transform a function of arity 7 into a corresponding set function.

isEmpty :: Values a -> Bool  Deterministic 

Is a multiset of values empty?

notEmpty :: Values a -> Bool  Deterministic 

Is a multiset of values not empty?

valueOf :: Eq a => a -> Values a -> Bool  Deterministic 

Is some value an element of a multiset of values?

chooseValue :: Eq a => Values a -> a  Non-deterministic 

Chooses (non-deterministically) some value in a multiset of values and returns the chosen value. For instance, the expression 

chooseValue (set1 anyOf [1,2,3])

non-deterministically evaluates to the values 1, 2, and 3. Thus, (set1 chooseValue) is the identity on value sets, i.e., (set1 chooseValue s) contains the same elements as the value set s.

choose :: Eq a => Values a -> (a,Values a)  Non-deterministic 

Chooses (non-deterministically) some value in a multiset of values and returns the chosen value and the remaining multiset of values. Thus, if we consider the operation chooseValue defined by 

chooseValue x = fst (choose x)

then (set1 chooseValue) is the identity on value sets, i.e., (set1 chooseValue s) contains the same elements as the value set s.

selectValue :: Values a -> a  Deterministic 

Selects (indeterministically) some value in a multiset of values and returns the selected value. Thus, selectValue has always at most one value, i.e., it is a deterministic operation. It fails if the value set is empty.

NOTE: The usage of this operation is only safe (i.e., does not destroy completeness) if all values in the argument set are identical.

select :: Values a -> (a,Values a)  Deterministic 

Selects (indeterministically) some value in a multiset of values and returns the selected value and the remaining multiset of values. Thus, select has always at most one value, i.e., it is a deterministic operation. It fails if the value set is empty.

NOTE: The usage of this operation is only safe (i.e., does not destroy completeness) if all values in the argument set are identical.

getSomeValue :: Values a -> IO (Maybe a)  Deterministic 

Returns (indeterministically) some value in a multiset of values. If the value set is empty, Nothing is returned.

getSome :: Values a -> IO (Maybe (a,Values a))  Deterministic 

Selects (indeterministically) some value in a multiset of values and returns the selected value and the remaining multiset of values. Thus, select has always at most one value. If the value set is empty, Nothing is returned.

mapValues :: (a -> b) -> Values a -> Values b  Deterministic 

Maps a function to all elements of a multiset of values.

foldValues :: (a -> a -> a) -> a -> Values a -> a  Deterministic 

Accumulates all elements of a multiset of values by applying a binary operation. This is similarly to fold on lists, but the binary operation must be commutative so that the result is independent of the order of applying this operation to all elements in the multiset.

filterValues :: (a -> Bool) -> Values a -> Values a  Deterministic 

Keeps all elements of a multiset of values that satisfy a predicate.

minValue :: Ord a => Values a -> a  Deterministic 

Returns the minimum of a non-empty multiset of values according to the given comparison function on the elements.

minValueBy :: (a -> a -> Ordering) -> Values a -> a  Deterministic 

Returns the minimum of a non-empty multiset of values according to the given comparison function on the elements.

maxValue :: Ord a => Values a -> a  Deterministic 

Returns the maximum of a non-empty multiset of values according to the given comparison function on the elements.

maxValueBy :: (a -> a -> Ordering) -> Values a -> a  Deterministic 

Returns the maximum of a non-empty multiset of values according to the given comparison function on the elements.

values2list :: Values a -> IO [a]  Deterministic 

Puts all elements of a multiset of values in a list. Since the order of the elements in the list might depend on the time of the computation, this operation is an I/O action.

printValues :: Show a => Values a -> IO ()  Deterministic 

Prints all elements of a multiset of values.

sortValues :: Ord a => Values a -> [a]  Deterministic 

Transforms a multiset of values into a list sorted by the standard term ordering. As a consequence, the multiset of values is completely evaluated.

sortValuesBy :: (a -> a -> Bool) -> Values a -> [a]  Deterministic 

Transforms a multiset of values into a list sorted by a given ordering on the values. As a consequence, the multiset of values is completely evaluated. In order to ensure that the result of this operation is independent of the evaluation order, the given ordering must be a total order.