Copyright (C) 2009-2010, Trevor Davel <twylite AT crypt DOT co DOT za>

See the file "LICENSE.txt" (Tcl/Tk License) for information on usage and redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES.

## control::functional 1.x

### Overview

Enhanced support for functional programming in Tcl, with implementations of some common higher-order functions.

This module builds on existing Tcl functions and practices (such as `apply`

from TIP #194, and using command prefixes for callbacks).

### Related documents

- Introduction, Motivation and Goals for this module.
- The design of control::functional explains the definition of 'a function' and the rationale for the functions in this module.
- A review of FP and higher order functions in Tcl discusses alternatives that provide similar (or related) functionality.
- TIP: Higher-order functions in Tcl is a working document intended to result in a Tcl Improvement Proposal based on
`control::functional`

.

### Tcl definition of a 'function'

Higher-order functions take a function as input and/or return a function as output. To work with higher-order functions in Tcl we need an understanding of what 'a function' is and how to work with one.

A 'function' in Tcl is **defined here** as a command prefix:

- A list such that
`[lindex $function 0]`

is the command to be evaluated - The arguments to the command are
`{*}[lrange $function 1 end]`

.

A function may thus be built as `[list cmd arg1 arg2 ...]`

for any Tcl command *cmd*, and any function may be curried by `lappend`

ing one or more args to the function.

A function (command prefix) may be invoked:

- ... in the current scope as
`{*}$function ?arg1 arg2 ...?`

. - ... in the caller's scope as
`uplevel 1 $function ?[list arg1 arg2 ...]?`

.

### Higher-order functions

**General**

- The
*cmdprefix*is executed in the context of the caller of the higher-order function. - Altering the input list(s) during the operation (for example as a side-effect of the cmdprefix) does not change the result. The higher-order function effectively iterates over a read-only copy of the input list(s).
- If a TCL_ERROR (1) is encountered, the higher-order function will abort the operation and propagate the error to the caller.
- Interaction with
`continue`

and`break`

*is undefined*, and strictly a consequence of the implementation. Implementations may support these return codes, or promote them to TCL_ERROR (1) as if called outside a supporting construct; but it is not acceptable to ignore them! - Those higher-order functions that do not require processing in a particular order may process their input list(s) in
*any*order (perhaps even in parallel). Side-effects of cmdprefix should neither expect nor rely on a particular order of iteration. - Notwithstanding the previous point,
*this implementation is order preserving*and its behaviour is comparable to`foreach`

.

**foldl** *cmdprefix ?initial? list*

A left fold over a list (with or without initial value), returning the output of the last invocation ofcmdprefix.

The input function is called with two arguments:`cmdprefix accum input`

. Theaccumulator is the output of the previous invocation ofcmdprefix(or the initial value, or the first element of the input list), and input is the next element of the input list. The function must return a new value for the accumulator.

A left fold of the operation "-" (subtract) over the list`{1 2 3 4 5}`

is equivalent to`(((1 - 2) - 3) - 4) - 5`

, with the result -13.

**foldr** *cmdprefix ?initial? list*

A right fold over a list (with or without initial value).

The input function is called with two arguments:`cmdprefix input accum`

. Theaccumulator is the output of the previous invocation ofcmdprefix(or the initial value, or the last element of the input list), and input is the next element of the input list (from the right). The function must return a new value for the accumulator.

A right fold of the operation "-" (subtract) over the list`{1 2 3 4 5}`

is equivalent to`1 - (2 - (3 - (4 - 5)))`

, with the result 3.

**filter** *predicate list*

A filter over a list, returning a list of elements from the input set that match a predicate.

predicateis a cmdprefix that returns a boolean, and is called with a single argument:`cmdprefix input`

.inputis an element from the input list. If the function returnstruethen the elementinputwill be included in the output list.

`filter`

is notorder-preserving: the order of elements in the output list may not match their order in the input list. In addition filter may process its input list in any order. Any appearance of order preservation is strictly a consequence of the implementation.

A filter of the operator "> 2" (greater than 2) over the list`{5 2 3 4 1}`

will produce`{5 3 4}`

(or`{3 4 5}`

, etc.).

**map** *?rule? cmdprefix list1 ?list2 ... listN?*

A variadic map over N lists, returning a single list. For each index i in the input list(s) (taken in parallel),cmdprefixwill be invoked with N arguments (the i'th element of each input list). The result of invokingcmdprefixbecomes the i'th element of the output list.

ruleis required for 2 or more lists, and indicates how to handle lists of different lengths:

-shorteststops processing when the end of the shortest list is reached.-longestbehaves like`foreach`

, stopping when the end of the longest list is reached. Shorter lists are extended with empty string elements.-equalthrows an exception if the lists are of differing lengths. Lists lengths are checked beforecmdprefixis invoked.

`The input function is called with N arguments, as explained above: ``cmdprefix elem1 ?elem2 ... elemN?`

. The returned value becomes an element in the output list.

`map`

isorder preserving: the i'th element of the output list corresponds tocmdprefixexecuted over the i'th element(s) of the input list(s).However, map may process its input list(s) in any order. Any appearance of a predictable order of iteration over the input list(s) is strictly a consequence of the implementation.

### Helpers

**curry** *cmdprefix arg ?arg ...?*

Returns a function created by the partial application of arguments tocmdprefix. This is known as currying.

**lambda** *arglist body ?arg ...?*

Constructs and returns a lambda: an anonymous proc thatexecutes in the namespace in which it was constructed. A lambda is a command prefix (and thus a function).

arglistandbodyare as for`proc`

. Additional arguments (if present) curry the lambda.

**lambdaexpr** *arglist expr ?arg ...?*

Constructs and returns a lambda, the body of which is evaluated as an expression (as if by`expr`

). The lambdaexecutes in the namespace in which it was constructed.

arglistis as for`proc`

, andexpris evaluated with`expr`

. Additional arguments (if present) curry the lambda.

**compose** *f g ...*

Compose two functions z=f(y) and y=g(x), returning a new function h such that z = h(x) = f(g(x)).

`It is possible to compose more than two functions by calling ``compose`

with extra arguments. The functions are applied right-to-left, so the function given as the last argument is executed first, and its output is used as input to the second to last argument, and so on.

fandgare both cmdprefixes.

**range** *?from? to ?step?*

Constructs and returns a list of integers ranging fromfrom(default 0) toto(inclusive) in increments ofstep(default 1). All input arguments are numbers.