3 Main Features of Curry

3.5 Functions

3.5.1 Basic Concepts

A program function abstracts a function in the mathematical sense. A function is a device that takes arguments and returns a result. The result is obtained by evaluating an expression which generally involves the function’s arguments. The following function computes the square of a number.

square x = x * x

The symbols “square” is the name or identifier of the function. The symbol “x” is the function’s argument. The above declaration is referred to as a rewrite rule, or simply a rule, defining a function. The portion of the declaration to the left of the symbol “=” is the rule’s left-hand side. The expression “x * x” is the rule’s right-hand side.

When the “square” symbol is applied to an expression, e.g., “2 + 3”, this expression is bound to the argument “x”. The result of the application is “(2 + 3) * (2 + 3)”, i.e., the body in which the argument is replaced by its binding. Thus:


Prelude> square (2+3)
25

Functions can be anonymous, i.e., without a name. An anonymous function is useful when a function is referenced only once. In this case, the reference to the function can be replaced by the expression defining the function. In the following example:

result = (\x -> x * x) (2+3)

the value of result is 25. It is obtained by applying the expression (\x -> x * x), an anonymous function, to (2+3), its argument. An anonymous function definition has the following structure:


\args -> right-hand side

A more motivating example of anonymous function is presented in Section 3.11

The evaluation of any expression, in particular of a function application, is lazy. This means that the computation of any expression, including the subexpressions of a larger expression, is delayed until the expression’s value is actually needed. The exact meaning of “actually needed” is quite technical, but the intuitive meaning suffices for our purposes. Many programming languages, such as C and Java, adopt this evaluation strategy, under the name of short circuit, only for Boolean expressions.

We will discuss this issue in more detail later. Although the lazy evaluation strategy is conceptually simpler than any other strategy, many traditional programming languages evaluate the arguments of a function call eagerly, i.e., before applying a function to its arguments. This fact is sometimes a source of confusion for the beginner.

3.5.2 Pattern Matching

The definition of a function can be broken into several rules. A single rule would suffice in many cases. However, several rules allows a definition style, called pattern matching, which is easier to code and understand. This feature allows a function to dispatch the expression to be returned depending on the values of its arguments. The following example shows the definition of the Boolean negation function “not”:

not True = False
not False = True

The above definition is equivalent to the following one which does not use pattern matching but relies on a conditional expression:

not x = if x == True then False else True

Pattern matching is particularly convenient for functions that operate on algebraic datatypes. We will further discuss this aspect after discussing data declarations.

3.5.3 Conditions

Each rule defining a function can include one or more conditions. For Boolean conditions, a rule has the following general structure:

functIdarg_1arg_m|cond_1=expr_1|=|cond_n=expr_n

A condition is tested after binding the arguments of a call to the corresponding arguments in the left-hand side of the rule. The function is applied to the arguments only if the condition holds. Each condition cond_i is an expression of type Bool. The conditions are tested in their textual order. Thus, the first right-hand side with a condition evaluable to True is taken. Furthermore, the last condition can be “otherwise” which is equivalent to True, i.e., it holds regardless of any value of the arguments. The following example shows a plausible definition of the maximum of two numbers:

max x y | x < y     = y
        | otherwise = x

3.5.4 Non-determinism

Operations can be non-deterministic. Non-deterministic operations are not functions in the mathematical sense because they can return different values for the same input. For example, a hospital’s information system defines which days a doctor is on-call with a non-deterministic function:

oncall Joan    = Monday
oncall Joan    = Wednesday
oncall Richard = Monday
oncall Luc     = Tuesday
...

The value of “oncall Joan” can be either “Monday” or “Wednesday”. The programmer cannot select which of the two values will be computed. Non-deterministic operations support a programming style similar to that of logic programs, while preserving some advantages of functional programs such as expression nesting and lazy evaluation. In particular, some strong properties concerning the evaluation of ordinary functions hold also for non-deterministic operations [7]. For example, suppose that “today” holds which day of the week is today. A predicate, “available”, telling whether its argument, a doctor, is available at the current time is coded as:

available x | oncall x == today = True
            | otherwise         = False

Without non-determinism, coding “oncall” would require some data structure, e.g., the list of days in which each doctor is on-call, and defining “available” would become more complicated.

Non-determinism is a powerful feature. In programming, as in other aspects of life, power must be exercised with some care. A non-deterministic program is appropriate only if all its possible outputs are equally desirable. If some outputs are more desirable than others, the program should be (more) deterministic. In this case, non-determinism could be conveniently used internally by the program to generate plausible results which can then be selected according to desirability.

Exercise 2

In a manufacturing plant two specialized tasks, cut and polish, are executed only by specialized workers, Alex, Bert and Chuck. Not every worker can execute every task. Only Alex and Bert are able to Cut, whereas only Bert and Chuck are able to Polish. Code a non-deterministic operation, assign, that assigns to a task a worker that can execute it. [Browse Answer][Download Answer]

3.5.5 Functional Patterns

Pattern matching, see Sect. 3.5.2, is a feature that provides in a compact and readable form both case distinction and (sub)argument selection. The arguments in a rule defined by pattern matching are expressions consisting of variables and/or data constructor symbols. Curry amplifies this feature with functional patterns. In a functional pattern some argument in a rule defining a function is an expression containing a function symbol. For example, the function computing the last element of a non-empty list can be defined as:

last (_++[e]) = e

where “++” is an infix operator that concatenates two lists, see function conc in Sect. 3.7. The intuition is that if a list l can be seen as the concatenation of some uninteresting list and a list containing the single element e, then e is the last element of l.

The meaning of the above rule is the same as the infinite set of rules:

last [e] = e
last [_,e] = e
last [_,_,e] = e
...

Code employing functional patterns should be preferred to similar code using conditions (see below) because it is more readable and more efficient:

last xs | xs =:= _++[e] = e  where e free
Exercise 3

Define a function that takes a list a of integers and computes a sublist l of a such that the last element of l is twice the first element. E.g., given the list [3,6,2,1,4,5] the sublists satisfying the required constraint are [3,6] and [2,1,4]. [Browse Answer][Download Answer]

3.5.6 Default Rule

The Curry language specifies that the textual order of the rules defining a function is irrelevant in the sense that every rule that is applicable to an expression should be applied. In practice, the situation is more delicate. For example, in PAKCS when multiple rules are applicable some rule is going to be applied before some other and if the application of the first rule does not terminate the second rule is never applied.

When defining a function, Curry allows the programmer to define a rule, called a default rule [5] that is applied only if all the other rules, that in this context we call standard, cannot be applied. The processing of default rules require the Curry preprocessor. It is not part of PAKCS but the preprocessor can easily be installed by the Curry package manager with the following commands (see also Section 5.2):

> cypm update
> cypm install currypp

After the installation of the Curry preprocessor,44The executable currypp of the preprocessor is stored in $HOME/.cpm/bin so that one should have this directory in the load path. one can use default rules in a program by placing the following line at the beginning of the source program.

{-# OPTIONS_CYMAKE -F --pgmF=currypp --optF=defaultrules #-}

We recall that a standard rule r is applicable to an expression e iff e and the left-hand side of r unify and the condition of r, if any exists, is satisfied by the instantiation of e. For example, the operation zip is defined with a default rule as follows:

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip'default _ _ = []

Since the standard rule is applicable to zip [1] [2], the default rule is ignored so that this expression is solely reduced to (1,2):zip [] []. Since the standard rule is not applicable to zip [] [], the default rule is applied and yields the value []. Altogether, the only value of zip [1] [2] is [(1,2)]. However, if some argument has more than one value, we use the evaluation principle above for each combination. Thus, the call zip ([1] ? []) [2] yields the two values [(1,2)] and [].

Default rules are useful to regain control after a failed search. For example, consider looking up the value of a key in a key-value pair list.

  lookup (key, _ ++ [(key,value)] ++ _) = Just value
  lookup'default _ = Nothing

If the key of a search is not in a list l, the call lookup l, returns Nothing instead of failing.