The Haskell Road to Logic, Maths and Programming. Second Edition (Texts in Computing) by Kees Doets & Jan van Eijck

Author:Kees Doets & Jan van Eijck
Language: eng
Format: azw3
Publisher: UNKNOWN
Published: 2018-04-14T16:00:00+00:00

6.1 Basic Notions

A function is something that transforms an object given to it into another one. The objects that can be given to a function are called its arguments, and the results of the transformation are called values. The set of arguments is called the domain of the function. We say that a function is defined on its domain.

If f is a function andx one of its arguments, then the corresponding value is denoted byf (x). A function valuey = f (x) is called the image ofx underf. Thatf (x) = y can also be indicated byf : x−→y. The domain off is denoted bydom (f ). Its range is ran(f ) ={f (x)|x∈ dom (f )}.

Example 6.1 A function can be given as a rule or a prescription how to carry out the transformation.

•

First square, next add one is the function that transforms a realx∈ R into x2 + 1.

Lettingf stand for this function, it is customary to describe it by the equation

f (x) = x2 + 1.

The Haskell implementation uses the same equation:

f x = x^2 + 1

• The function described by |

x| = x ifx 0

−x ifx < 0

transforms a real into its absolute value. The Haskell implementation given in Prelude.hs follows this definition to the letter:

absReal x | x >= 0 = x | otherwise = -x

• The identity function 1A defined onA does not “transform” at all in the usual sense of the word: given an argumentx∈A, it outputsx itself. A polymorphic identity function is predefined in Haskell as follows:

id :: a -> a id x = x

Set theory has the following simple definition of the concept of a function.

Definition 6.2 A function is a relationf that satisfies the following condition.

(x, y)∈f∧ (x, z)∈f =⇒ y = z.

That is: for everyx∈ dom (f ) there is exactly oney∈ ran(f ) such that (x, y)∈f.

Ifx∈ dom (f ), thenf (x) is by definition the unique objecty∈ ran(f ) for which (x, y)∈f. Note that we use dom here in the sense defined for relations, but that the relation and the function-sense of the notion coincide: the domaindom (f ) of the function f is{x| ∃y((x, y)∈f )}; exactly as in the relation-case (cf. Definition 5.1 p. 162).

Similarly, the range off coincides with the range off as a relation. The set-theoretic and the computational view on functions are worlds apart, for computationally a function is an algorithm for computing values. However, in cases of functions with finite domains it is easy to switch back and forth between the two perspectives, as the following conversions demonstrate.

list2fct :: Eq a => [(a,b)] -> a -> b

list2fct [] _ = error "function not total" list2fct ((u,v):uvs) x | x == u = v

| otherwise = list2fct uvs x

fct2list :: (a -> b) -> [a] -> [(a,b)] fct2list f xs = [ (x, f x) | x <- xs ]

The range of a function, implemented as a list of pairs, is given by:

ranPairs :: Eq b => [(a,b)] -> [b] ranPairs

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.