Module 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

Intuition: 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.

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

Author: Michael Hanus, Fabian Reck

Version: June 2017

Summary of exported operations:

set0 :: a -> Values a   
Combinator to transform a 0-ary function into a corresponding set function.
set0With :: (SearchTree a -> ValueSequence a) -> a -> Values a   
Combinator to transform a 0-ary function into a corresponding set function that uses a given strategy to compute its values.
set1 :: (a -> b) -> a -> Values b   
Combinator to transform a unary function into a corresponding set function.
set1With :: (SearchTree a -> ValueSequence a) -> (b -> a) -> b -> Values a   
Combinator to transform a unary function into a corresponding set function that uses a given strategy to compute its values.
set2 :: (a -> b -> c) -> a -> b -> Values c   
Combinator to transform a binary function into a corresponding set function.
set2With :: (SearchTree a -> ValueSequence a) -> (b -> c -> a) -> b -> c -> Values a   
Combinator to transform a binary function into a corresponding set function that uses a given strategy to compute its values.
set3 :: (a -> b -> c -> d) -> a -> b -> c -> Values d   
Combinator to transform a function of arity 3 into a corresponding set function.
set3With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> a) -> b -> c -> d -> Values a   
Combinator to transform a function of arity 3 into a corresponding set function that uses a given strategy to compute its values.
set4 :: (a -> b -> c -> d -> e) -> a -> b -> c -> d -> Values e   
Combinator to transform a function of arity 4 into a corresponding set function.
set4With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> a) -> b -> c -> d -> e -> Values a   
Combinator to transform a function of arity 4 into a corresponding set function that uses a given strategy to compute its values.
set5 :: (a -> b -> c -> d -> e -> f) -> a -> b -> c -> d -> e -> Values f   
Combinator to transform a function of arity 5 into a corresponding set function.
set5With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> a) -> b -> c -> d -> e -> f -> Values a   
Combinator to transform a function of arity 5 into a corresponding set function that uses a given strategy to compute its values.
set6 :: (a -> b -> c -> d -> e -> f -> g) -> a -> b -> c -> d -> e -> f -> Values g   
Combinator to transform a function of arity 6 into a corresponding set function.
set6With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> g -> a) -> b -> c -> d -> e -> f -> g -> Values a   
Combinator to transform a function of arity 6 into a corresponding set function that uses a given strategy to compute its values.
set7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> a -> b -> c -> d -> e -> f -> g -> Values h   
Combinator to transform a function of arity 7 into a corresponding set function.
set7With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> g -> h -> a) -> b -> c -> d -> e -> f -> g -> h -> Values a   
Combinator to transform a function of arity 7 into a corresponding set function that uses a given strategy to compute its values.
isEmpty :: Values a -> Bool   
Is a multiset of values empty?
notEmpty :: Values a -> Bool   
Is a multiset of values not empty?
valueOf :: a -> Values a -> Bool   
Is some value an element of a multiset of values?
choose :: Values a -> (a,Values a)   
Chooses (non-deterministically) some value in a multiset of values and returns the chosen value and the remaining multiset of values.
chooseValue :: Values a -> a   
Chooses (non-deterministically) some value in a multiset of values and returns the chosen value.
select :: Values a -> (a,Values a)   
Selects (indeterministically) some value in a multiset of values and returns the selected value and the remaining multiset of values.
selectValue :: Values a -> a   
Selects (indeterministically) some value in a multiset of values and returns the selected value.
mapValues :: (a -> b) -> Values a -> Values b   
Maps a function to all elements of a multiset of values.
foldValues :: (a -> a -> a) -> a -> Values a -> a   
Accumulates all elements of a multiset of values by applying a binary operation.
filterValues :: (a -> Bool) -> Values a -> Values a   
Keeps all elements of a multiset of values that satisfy a predicate.
minValue :: (a -> a -> Bool) -> Values a -> a   
Returns the minimal element of a non-empty multiset of values with respect to a given total ordering on the elements.
maxValue :: (a -> a -> Bool) -> Values a -> a   
Returns the maximal element of a non-empty multiset of value with respect to a given total ordering on the elements.
values2list :: Values a -> IO [a]   
Puts all elements of a multiset of values in a list.
printValues :: Values a -> IO ()   
Prints all elements of a multiset of values.
sortValues :: Values a -> [a]   
Transforms a multiset of values into a list sorted by the standard term ordering.
sortValuesBy :: (a -> a -> Bool) -> Values a -> [a]   
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   

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

set0With :: (SearchTree a -> ValueSequence a) -> a -> Values a   

Combinator to transform a 0-ary function into a corresponding set function that uses a given strategy to compute its values.

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

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

set1With :: (SearchTree a -> ValueSequence a) -> (b -> a) -> b -> Values a   

Combinator to transform a unary function into a corresponding set function that uses a given strategy to compute its values.

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

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

set2With :: (SearchTree a -> ValueSequence a) -> (b -> c -> a) -> b -> c -> Values a   

Combinator to transform a binary function into a corresponding set function that uses a given strategy to compute its values.

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

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

set3With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> a) -> b -> c -> d -> Values a   

Combinator to transform a function of arity 3 into a corresponding set function that uses a given strategy to compute its values.

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

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

set4With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> a) -> b -> c -> d -> e -> Values a   

Combinator to transform a function of arity 4 into a corresponding set function that uses a given strategy to compute its values.

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

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

set5With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> a) -> b -> c -> d -> e -> f -> Values a   

Combinator to transform a function of arity 5 into a corresponding set function that uses a given strategy to compute its values.

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

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

set6With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> g -> a) -> b -> c -> d -> e -> f -> g -> Values a   

Combinator to transform a function of arity 6 into a corresponding set function that uses a given strategy to compute its values.

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

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

set7With :: (SearchTree a -> ValueSequence a) -> (b -> c -> d -> e -> f -> g -> h -> a) -> b -> c -> d -> e -> f -> g -> h -> Values a   

Combinator to transform a function of arity 7 into a corresponding set function that uses a given strategy to compute its values.

isEmpty :: Values a -> Bool   

Is a multiset of values empty?

Further infos:
  • solution complete, i.e., able to compute all solutions

notEmpty :: Values a -> Bool   

Is a multiset of values not empty?

Further infos:
  • solution complete, i.e., able to compute all solutions

valueOf :: a -> Values a -> Bool   

Is some value an element of a multiset of values?

choose :: Values a -> (a,Values a)   

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 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.

chooseValue :: Values a -> a   

Chooses (non-deterministically) some value in a multiset of values and returns the chosen value. Thus, (set1 chooseValue) is the identity on value sets, i.e., (set1 chooseValue s) contains the same elements as the value set s.

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

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. 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.

Further infos:
  • partially defined
  • solution complete, i.e., able to compute all solutions

selectValue :: Values a -> a   

Selects (indeterministically) some value in a multiset of values and returns the selected value. Thus, selectValue has always at most one value. 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.

Further infos:
  • might behave indeterministically
  • solution complete, i.e., able to compute all solutions

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

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

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

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   

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

minValue :: (a -> a -> Bool) -> Values a -> a   

Returns the minimal element of a non-empty multiset of values with respect to a given total ordering on the elements.

maxValue :: (a -> a -> Bool) -> Values a -> a   

Returns the maximal element of a non-empty multiset of value with respect to a given total ordering on the elements.

values2list :: Values a -> IO [a]   

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.

Further infos:
  • solution complete, i.e., able to compute all solutions

printValues :: Values a -> IO ()   

Prints all elements of a multiset of values.

sortValues :: Values a -> [a]   

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]   

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.