# Second Order Functions

SA Engine functions are internally represented as any other objects
and stored in the database. Object representing functions can be used
in functions and queries too. An object representing a function is
called a *functional* and is representyed as instances of type
`Function`

. *Second order functions* are functions that take
functionals as arguments or results.

For example, the second order system function `functionnamed()`

retrieves the functional `fno`

having a given name `fn`

:

` functionnamed(Charstring fn) -> Function fno`

Another example of a second order function is the system function `apply()`

:

` apply(Function fno, Vector argl) -> Bag of Vector`

`apply()`

calls the functional `fno`

with the vector `argl`

as
argument list. The result tuples are returned as a bag of vectors.

For example, this call adds the number 1 and 3.4:

`apply(functionnamed("plus"),[1,3.4])`

Notice how `apply()`

represents argument lists and result tuples as vectors.

When using second order functions one often needs to retrieve a
functional `fno`

given its name. The function `functionnamed()`

provides one way to achieve this. A simpler way is often to use
*functional constants*, for example:

`#'mod'`

A functional constant is translated into the functional with the name uniquely specified by the string constant.

The following
expression returns the vector `[1]`

.

`apply(#'mod',[4,3])`

**Notice** that an error is raised if the function name specified if a
functional constant does not uniquely identify the functional. This
happens if it is the generic name of an overloaded
function. For
example, the functional constant `#'plus'`

is illegal, since `plus()`

is overloaded. For overloaded functions the name of a
resolvent
has to be used instead.

For example, `apply(#'plus',[2,3.5])`

generates an error, while
`apply(#'number.number.plus->number', [2,3.5])`

returns the vector
`[5.5]`

.

You can use generic functions when applying non-unique resolvents, in which case apply will dynamically choose the correct resolvent based on the types in the argument vector.

For example, the following expression returns the vector ``[5,5]`

:

`apply(functionnamed("plus"),[2,3.5])`

This call will be slower than
`apply(#'number.number.plus->number',[2,3.5])`

since the resolvent is
selected using late
binding.

## Transitive closuresâ€‹

The *transitive closure* function `tclose()`

is a second order
function to explore graphs where the edges are expressed by a
*transition function* specified by argument `fno`

:

` tclose(Function fno, Object o) -> Bag of Object`

`tclose()`

applies the transition function `fno(o)`

, then
`fno(fno(o))`

, then `fno(fno(fno(o)))`

, etc. until `fno`

returns the
empty result. Because of the Daplex
semantics, if
the transition function `fno`

returns a bag of values for some
argument `o`

, the successive applications of `fno`

will be applied on
each element of the result bag. The result types of a transition
function must either be the same as the argument types or a bag of the
argument types. Such a function that has the same arguments and (bag
of) result types is called a *closed function*.

For example, assume the following definition of a circular graph
defined by the transition function `arcsto()`

:

` create function arcsto(Integer node)-> Bag of Integer n as stored;`

set arcsto(1) = bag(2,3);

set arcsto(2) = bag(4,5);

set arcsto(5) = bag(1)

The following query traverses the graph starting in node 1:

`tclose(#'arcsto', 1)`

In general the function `tclose()`

traverses a graph where the
vetextes (nodes) are defined as arguments to the the transition
function. The neigbours to an edge `e`

(i.e. the edges from `e`

) are
defined by the result bag from the transition function `fno(e)`

. The
graph may contain loops and therefore `tclose()`

will remember what
vertexes it has visited earlier and stop further traversals for
vertexes already visited. You can also query the inverse of
`tclose()`

, i.e. from which nodes `f`

can be reached.

For example:

`select f`

from Integer f

where 1 in tclose(#'arcsto',f)

A transition function may have extra arguments and results, as long as the function is closed. This allows to pass extra parameters to a transitive closure computation.

For example, to compute not only the transitive closure, but also the distance from the root of each visited graph node, use the following transition function:

`create function arcstod(Integer node, Integer d) -> Bag of (Integer,Integer)`

as select arcsto(node),1+d;

tclose(#'arcstod',1,0)

**Notice** that only the first argument and result in the transition
function define graph vertices's, while the remaining arguments and
results are extra parameters for passing information through the
traversal, as with `arcstod()`

. Notice that there may be no more than
three extra parameters in a transition function.

If you know that the graph to traverse is a tree or a directed acyclic graph (DAG) you can instead use the faster function:

` traverse(Function fno, Object o) -> Bag of Object`

As for `tclose()`

, the children in the tree to traverse is defined by
the transition function `fno`

. The tree is traversed in pre-order
depth first. Leaf nodes in the tree are nodes for which `fno`

returns
empty result. The function `traverse()`

will not terminate if the
graph is circular. Nodes are visited more than once for acyclic graphs
having common subtrees.

## Iterationâ€‹

The function `iterate()`

applies a function `fn()`

repeatedly.

Signature:

` iterate(Function fn, Number maxdepth, Object x) -> Object r`

The iteration is initialized by setting *x _{0}=x*. Then

*x*is repeatedly computed until one of the following conditions hold: 1. there is no change (

_{i+1}= fn(x_{i})*x*

_{i}*=*

*x*), or 2. `fn()` returns nil (

_{i+1}*x*

_{i+1 }*=nil*), or 3. an upper limit *maxdepth* of the number of iterations is reached for

*x*.

_{i}The function `iterate()`

is overloaded and accepts an extra parameter
`p`

passed into *fn(x _{i},p)* in the iterations.

Signature:

`iterate(Function fn, Number maxdepth, Object x0, Object p) -> Object r`

This enables termination of the iteration since `fn(x,p)`

can
return `nil`

based on both `x`

and `p`

.