Basics of functional programming

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 2 - ⇑ Fundamentals of functional programming ⇑

← What is functional programming Basics of functional programming List processing →


Function - a rule that assigns a specific output for every given input


Domain - the set of data that comprises the inputs of a function


Co-domain - the set of values that from which the outputs of a function are chosen


A function is a rule that connects inputs in the form of set A, to a set of outputs chosen from set B. It is not necessary that every member of set B will be mapped to an input from set A. In the example below, SetA describes all the positive integers (), the function is the doubling of all positive integers, SetB is the set of all positive integers, but note that not all elements of SetB are mapped from SetA, e.g. no doubling of a positive integer will ever map to the number 3.

CPT functional basics.svg

Another name for the input set is the domain, the set from which the possible output set is chosen is called the co-domain. The type of the domain and the co-domain do not have to be the same. For example we could have a function that told us whether a given positive integer input was prime number. In this cas the domain would be positive integers, and the co-domain the boolean values True and False, as shown below:

CPT function basics different domain types.svg

We describe functions as having a function type. For function f, the function type can be written A → B, or more fully f: A → B.


doubleNumber: integer -> integer

isPrime: integer -> boolean

isCorrectPassword: string -> boolean

MD5HashingAlgorithm: string -> string

First-class objects[edit]

In a functional programming language functions are first-class objects. This means that they can be used in the following ways:

  • be assigned to a variable
  • be assigned as arguments
  • be returned in function calls
  • appear in expressions

The equivalent in procedural programming languages would be a variable, which can

Let's see this in action,

.> byThePowerOf x y = x^y -- assigning to a variable
.> 3 * byThePowerOf 2 2 -- 
12

Haskell declarations[edit]

In Haskell when you want to declare a value and attach it to a name you can use the = command like most other languages. For example, if we wanted to declare our own version of pi, we could write:

.> myPi = 3.14
.> myPi * 3
9.42

But, as I hope you remember, functional programming is immutable, and we shouldn't be able to edit the value of myPi once we have declared it in a program:

varyingTrouble.hs
myPi = 3.14

myPi = 4

Attempting to compile this code from the command line gives an error, Haskell won't let you declare the same thing twice. In other words it won't let you change the value fo something once it has been declared:

.> :l varyingTrouble.hs
main.hs:2:1: error:
    Multiple declarations of myPi
    Declared at: main.hs:1:1
                 main.hs:2:1
  |
2 | myPi = 4
  | ^^^^
Extension: Let and Where

This chapter gives a very simple introduction to Haskell declarations that resembles the construction of a variable or constant in other languages. The let and where commands offer better functionality, learn more about them over at learn you a haskell.

Exercise: Functional programming foundations

Label the domain and the co-domain

Answer:


Which is these statements is true

  1. the output of a function doesn't always have to match every value of the co-domain
  2. the domain the co-domain are always the same type
  3. the co-domain is always smaller than the domain
  4. the domain specifies the values of the output of a function

Answer:

1.

which would be the correct domain and codomain for the following functions: ConvertMonthNumbertoName

Answer:

ConvertMonthNumbertoName: integer -> String

let myList = [3,4,5,3,4,6]
head(tail(tail(myList)))

What functions might be present here

Answer:


Higher order functions[edit]

Now that we have learnt how to write simple functional programs using Haskell's inbuilt functions. Now we will learn how to define our own functions. To do this we write the name of the function along with any arguments it might take, then set the return value as a calculation. For example:

.> byThePowerOf x y = x^y
.>
.> byThePowerOf 2 3
8
.> isMagic x = if x == 3 then True else False
.>
.> isMagic 6
False
.> isMagic 6.5
False
.> isMagic 3
True

Haskell uses static typing, the type of every parameter and return value is known at compile time, unlike languages such as Python which are dynamically typed. When we write functions we can declare the types that should be used for the arguments and the output, meaning that we will have better control over how the compiler creates the functions we define.

There are several base types in Haskell (which are always written starting with a capital letter) including: Int, Integer, Float, Double, Bool, Char

For example we might create a function that tells us if a number is magic, where three is the magic number. Before we write the code to define the type of the input (Int) and the type of the output (Bool). This means when we load this code it will only accept integer inputs, anything else will bring an error.

definingDataTypes.hs
isMagic :: Int -> Bool

isMagic x = if x == 3

             then True
             else False

This means when we load this code it will only accept integer inputs, anything else will bring an error.

.> :l definingDataTypes
[1 of 1] Compiling definingDataTypes    ( definingDataTypes.hs, interpreted )
Ok, one module loaded.
.> isMagic 3
True
.> isMagic 7
False
.> isMagic 7.5
Error

As you can see, the output type is always the last datatype specified in in the -> list. All the other datatypes define the inputs.

Other examples .> factorial :: Int -> Integer .> factorial 0 = 1 .> factorial n = n * factorial (n - 1)

.> abc :: Char -> String .> abc 'a' = "Apple" .> abc 'b' = "Boat" .> abc 'c' = "Cat"

.> byThePowerOf :: Int -> Int -> Int .> byThePowerOf x y = x^y </syntaxhighlight>


a is also a type of type variable, that means it can stand in for any type.


Partial function application[edit]

Currying

.> min 2 3
2
.> (min 2) 3
3


addFour :: Int -> Int -> Int -> Int -> Int addFour 2 3 4 5

addFour 2

takes one parameter and returns a function that takes three more parameters. This is called a partially applied function.


then 3 is applied to that When we see the arrow (->) we are seeing the left hand side as the parameter passed to the function, and the right hand side as what it returns

parameter -> (what it returns)

a -> (a -> (a -> a))



In functional programming, a value that is passed to a function is known as an argument. For example, in the expression a = f(x) and b = f(2, 4), x, 2 and 4 are arguments.

Partial function application[edit]

Partial function application - the process of applying a function by creating an intermediate function some of the arguments to the function.


It is possible to pass any number of arguments into a function. Where this is the case partial function application can be used to fix the number of arguments that will be passed. The idea of this is that when you have one function that takes lots of arguments, by partially applying the function you effectively create a new function that performs just part of the calculation. The partial application of a function can produce results that are useful in their own rights in addition to the full application of the function.

For example, consider the two notations for a function that adds two integers together by taking two arguments: add: int x int → int add: int → int → int

  • The first is a full application of the function which takes two integers as arguments and adds them together to create a result that is also an integer. Both values are passed as arguments at the same time.
  • The second is a partial application that shows a new function being created, which always adds the first argument value onto a number. This new function is then applied to the second argument to produce the overall result.

Function composition[edit]

Function composition - combining two or more functions together to create more complex functions.


Function composition is the process of creating a new function by combining two existing functions together. This is one of the key principles of functional programming as the concept is to have complex functions that in turn are made up of simpler functions. As each component function produces its result, this is passed as an argument result to the calling function. This process continues for each of the component functions until a result is produced for the complex function as a whole.

Exam Questions

What is a functional programming language?

Answer:

A functional programming language is one which has each line of code made up of calls to a function which may be made up of other functions or result in a value.

Describe the difference between a first-class object and a high-order function

Answer:

A first class object is an object which can be passed as an argument or returned by a function. A higher order function can accept another function as an argument.