Yet another programming language (and only AQA), but it's OK because we'll be using Python as well as Haskell :) We are learning ...- About the meaning of the term function
- How to implement functions in a functional programming language
- Applications of functional programming
So that we can ...- State the format of a function as f : A → B
- A → B is the function type - A is called the argument type or domain - B is called the result type or co-domain - A and B are always subsets of objects - Functions map one set of values (domain) to another set of values (drawn from codomain)
- Describe a function as a first class object in functional programming
- State that a function application means a function applied to it's arguments
- State what is meant by partial function application for one, two and three argument functions
- State what is meant by composition of functions
- Show experience of constructing simple programs in a functional programming language
- Map - Filter - Reduce / fold - Higher order functions
- Be familiar with representing a list as a concatenation of a head and a tail
- The head is an element of a list - The tail is a list - The list can be empty - Operations (return head, return tail, test for empty list, return length of list, construct empty list, prepend an item to a list, append an item to a list) - Have experience writing programs for list operations in functional programming language - Application of functional programming to big data / distributed code
Up until now, we have mainly been learning procedural and object-oriented programming. We dabbled a little with a declarative programming language (SQL) but now, we learn the fundamentals of a fully blown declarative language!
We have met functions before. A function is a rule which relates an input to an output. It maps values in a
domain to values in a codomain. The values in the codomain to which our function maps are in the range of the function. We met this definition before when we learnt about vectors.
Function typeThe domain and the codomain are also related to the
function type. The type of a function states the data type of the argument the function requires (the value in the brackets) and the data type it will return. All elements in the domain must be of the same type as must all elements in the codomain.The type of function
f is written as f : A ⟼ B where A is the type of the domain and B is the type of the codomain.
Before you start,
forget everything you already know about programming (eek!) You don't think imperatively and you don't code imperatively. Everything in functional programming is a function, just like everything in object oriented programming is an object (although the methods you code are imperative!) You have to think of the world as functions. Clearly, applications of functional programming lean towards mathematical problems which require lots of calculations.In functional programming ...
- functions are
**pure**- they only modify their parameters and nothing else which prevents**side effects**; - functions with no arguments are called
**definitions**(we'd know them as assignment); - useful functions
**return**a value; - functions are
**predictable**- they always produce the*same outputs*given the*same inputs*; - there are
**no variables**! - there are
**no loops**so we have to use recursion (yuk!)
OK, OK, keep calm ... here comes the maths!
Function applicationIn mathematics,
function application is the act of applying a function to an argument(s) from the domain, A, so as to obtain the corresponding value from its range within the codomain, B. To define a function to
`double` a value, `x` , in Python we could type ...`def double(x): ` `return x*2` In a functional programming language, like Haskell, we write it like this ...
`double x = x * 2` In imperative languages function application is denoted using
parentheses whereas in functional languages it's denoted using a space. In each case, x, is an argument to the function. The function is called `double` ; its application is `double(x)` in Python and `double x` in Haskell.
Practical functional programmingTo learn some functional programming, we're going to use a very widely implemented platform called
Haskell.Click to visit the Haskell Website
You may wish to spend a little time on the tutorial that you can access by typing help in the 'Try It' section next to the lambda (
λ) symbol (derived from it's history in Lambda calculus) ... see how far you can get before you get confused! To progress further, you can either install Haskell yourself on your own computer or ask your teacher to install it on your lab computers at school.On Windows, Haskell comes with an interactive tool called
WinGHCi or the Glasgow Haskell Compiler (Interactive) into which you can issue Haskell commands interactively or load and execute scripts.The Glasgow Haskell Compiler (Interactive) running on Windows
First class objects / valuesA
first class object / value is any object / value that can ...- appear in an 'expression';
- be assigned to or named by a variable / identifier
- be stored in a list or a dictionary
- be passed as arguments to a function
- be returned from a function
... which pretty much covers everything in most modern programming languages. As you can imagine, by these definitions, all simple
scalar data types such as integer, float, bool and char are first class objects and so are data structures which contain them. In Python, objects are also first class as we have seen before when we have included objects assigned to variables, stored in lists, passed as parameters to functions or returned from functions.
Lambda functions
Getting Python functions to behave like first class objects is a little more tricky because we need functions to act as values. In Python, we can use
anonymous lambda functions (don't be scared). A lambda function is a 'throw-away' function that we define and use in context - it does not exist, nor can it be referenced, outside this context. We create lambda functions using the `lambda` keyword and we can assign them to variables, store them in lists, pass them to functions and return them from functions. Truly 'first class'!Try using Lambda to create an anonymous function.
`>>> lambda x : x*2` `<function <lambda> at 0x02FFCC00>` This is clearly a function (because it says so) but we have no way of 'holding' onto the lambda function - it is anonymous and has no identifier! So, let's give it one.
`>>> double = lambda x : x*2` `>>> double(4)` `8` We've created a function called double and we've assigned it straight to a variable (first class) so it acts like a value. We could have done this ...
`>>> def double(x):return x*2` `>>> double(4)` `8` ... so why bother with lambda? Mainly because it's easier and clearer but mainly because it is the only sensible way (not the only way) of
including a function inside another function. Seriously, you'll see the benefit of using lambda later on. We can pass a lambda function as a parameter to another function ...`>>> def fourtimes(function,parameter):` ` return function(parameter) * 2` `>>> fourtimes(lambda x: x*2, 4)` `16` Here, the function
`fourtimes` is behaving as a higher order function - one which takes another function as a parameter. The most common higher order functions are `map` , `filter` and `reduce` / `fold` . We'll meet these later. What about this?
`>>> def exponent(n): return lambda m : m**n` `>>> exponent(3)` `<function exponent.<locals>.<lambda> at 0x02FFCD20>` So, the function
`exponent` returns an actual function - this is clear (and totally first class). The function `exponent` is also behaving in a higher order fashion as it is returning a function. We certainly can't do this with normal functions (in Python at least).If you think about it, if
`exponent` returns a function rather than a value then the function has not been fully applied This is known, unsurprisingly, as partial function application - the function `exponent` has been partially applied and is waiting for it's missing argument.We can complete the application of the function by using it to create other functions, like this ...
`>>> cube = exponent(3)` `>>> cube(2)` `8` `>>> cube(3)` `27` Wow! Like, wow! The function
`cube` , completed the application of the function exponent by providing the final argument that it needs. Nice!Finally, let's create a
list of anonymous functions and access them like value to complete our proof of first classness!`>>> myfunctions = [lambda n:n*1,lambda n:n*2,lambda n:n*4]` `>>> myfunctions[0](2)` `2` `>>> myfunctions[1](2)` `4` `>>> myfunctions[2](2)` `8` Here, we've seen lambda functions behaving in a truly
first class fashion. Nice.So is mine!
Luckily, if we use Haskell, we don't generally have to use lambda functions for simple operations like this because in Haskell, the way that functions are defines is quite lambda like anyway. The safest way to conduct the next set of exercises is to use a
script rather than the interactive console. Often Haskell requires you to be more explicit about the function types that you are defining and you can't define function types in Haskell at the interactive prompt :(Using your favourite text editor, create the a script called
activity2.hs and save it in a suitable place. Make sure that the file extension is correct and close down your text editor. Now open up WinGHCi (if you haven't done already) and choose 'File > Load' and load in the script you have created. These are the two toolbar buttons you'll need next ...Once the file is loaded, hit the 'Run Text Editor' button and Notepad should appear, as if by magic. Use WinGHCi and the default text editor to carry out the following tasks. Edit the script in the text editor, click save and then click the 'Reload Script' button before executing the commands given at the interactive prompt. Here we go ...
We can define the same
`double` function in Haskell like this ...
In the text editor, you declare the function type explicitly so that Haskell knows what data type to expect and what data type it's meant to return. We can then use this double function in another function ...
This is a very simple example of a very common pattern you see in Haskell where basic functions are designed and combined to create more complex functions. Partial function application in Haskell is also straightforward. The exponent examples we saw before is easy but we need to make sure we declare a specific function type to allow us to perform all the operations we did with Python before.
Notice the the prime (') character after the
`exponent'` function name. The prime has no special meaning in this context (although it is used to prevent laziness in functions when doing fierce recursion) and hence we can use it in function names. There is already a function built into Haskell called `exponent` so adding the prime after our function denotes that it's a slightly modified version. This example won't work without it being there because Haskell will try to use the built in function.For the next section, unload the script by typing
`:m` at the prompt and pressing ENTER and you should have your prompt back again. Lambda functions in Haskell are declared similarly to the way they are in Python but since they are generally used 'on the fly', we'll define them at the interactive prompt rather than in a script. Lambdas are prefixed with a back slash (\) because it looks like a Greek letter lambda (λ).
`8`
`12`
`2.0` Don't worry too much if you aren't really following this (I wouldn't be surprised). Later on when we look at the main higher order functions
`map` , `filter` and `reduce` / `fold` , you'll see how these can be used in context.
The three most common functions which facilitate a functional approach to programming in Python are
map, filter and reduce. These three higher order functions form the backbone of most applications of functional programming in the field of big data, and they also make extensive use of the anonymous lambda functions we've just been learning about in the last activity (which is why we learnt about them!)MapThe map function takes a list of values from a
domain and applies a function to each value in the list, mapping the value to a range in the subdomain.The map function using a lambda function
The map function is built into the standard Python library so it's always available. The blueprint is ...
The
`map` object can be converted into list using the `list(object)` function. The function passed to `map` can be a built-in Python function. For instance, this `map` operation converts a string to a list of ASCII codes.`>>> list(map(ord,'Hello there!'))` `[72, 101, 108, 108, 111, 32, 116, 104, 101, 114, 101, 33]` ... and this one converts a list of numbers into a list of strings.
`>>> list(map(str,[1,2,3,4,5]))` `['1', '2', '3', '4', '5']` If the function takes more than one parameter, simply pass
`map` multiple lists. For instance, for the power function, `pow(x,y)` which takes two arguments (and is equivalent to `x**y` ) can be applied using a `map` function across two lists of values ...`>>> list(map(pow,[5,4,3,2,1],[1,2,3,4,5]))` `[5, 16, 27, 16, 1]` Consider this mathematical treat ...
`>>> import math` `>>> list(map(math.sin,[34,54,65]))` `[0.5290826861200238, -0.5587890488516163, 0.8268286794901034]` As you can imagine, you can also put lambda functions in the
`map` function to achieve more complex functional application. For example a simple `map` function which squares every value in a list ...`>>> list(map(lambda x:x**2, [1,2,3,4,5]))` `[1,4,9,16,25]` It's common to
separate the function from the map operation, which would be especially useful if the function was more complicated. For instance ...`>>> double = lambda x:x**2` `>>> list(map(double,[1,2,3,4,5]))` `[1,4,9,16,25]` We can also design a map function which capitalises every letter in a string.
`>>> ''.join(list(map(lambda x:chr(ord(x)-32),'hello')))` `'HELLO'` The list is endless ...
It's worth noting that the result of the map function can be achieved using list comprehensions. For instance, both these statements are equivalent ...`>>> list(map(lambda x:x+1,[1,2,3,4,5]))` `[2,3,4,5,6]` `>>> [x+1 for x in [1,2,3,4,5]]` `[2,3,4,5,6]` Neither!
In Haskell, the map function is structured like this ...
The function can be a simple partial application like
`(+1)` or a lambda function like `(\x -> x + 1)` . Both these functions are equivalent. Look ...
`[2,3,4,5,6]`
`[2,3,4,5,6]` Haskell has many built in functions which we can use in the map function. For instance ...
`[True,False,True,False,True]` Unfortunately, you can only provide one list as an argument to the Haskell map function, unlike Python, so you have to engage in some pretty
funky tricks to get it to handle more complex situations where you might want to give the function multiple parameters.
`[(5,1),(7,4),(6,5)]` The
`zip` function takes two lists and creates a single list of tuples (you'll recognised the difference between lists and tuples from Python, I'm sure). Then, we can throw our list of tuples into the map function to do some groovy things.
`[1,2,3]`
`[4,6,9]` The first example generates a list of the absolute difference between related values in the lists and the second example generates a list of the maximum related values from the lists. Nice.
Once again,
it's worth noting that the same can be achieved using list comprehensions. We haven't looked at list comprehensions in Haskell yet (and neither are we going to), however, you should be able to apply simple patterns using these examples. Notice the left facing '`<-` ' which means 'is drawn from'.
`[2,3,4,5,6]`
`[4,6,9]` You've already asked me that!
FilterThe
`filter` function takes a list of values and applies a conditional filter to it using a lambda function. The value from the list will be returned if, and only if, the result of the function is `True` .The filter function through the application of a lambda function
The filter function is also built into the Python standard library, so it's always available. The blueprint is ...
Where the function is a conditional statement which returns
`True` or `Fals` e. Common uses include, extracting even numbers from a list ...`>>> list(filter(lambda x:x%2==0,range(1,21))` `[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]` ... extracting odd numbers from a list ...
`>>> ` `list(filter(lambda x:x%2==1,range(1,21)))` `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]` You can truncate a list based in the value ...
>>>
` list(filter(lambda x:x>0,range(-5,5))]` `[1,2,3,4]` ... and even use string operations to search for matching values in a list or words.
`>>> names = ['Anne', 'Amy', 'Bob', 'David', 'Carrie', 'Barbara', 'Zach']` `>>> list(filter(lambda s: s.startswith('B'), names)` `['Bob', 'Barbara']` `>>> ` `list(filter(lambda s: 'a' in s.lower(), names)` `['Anne', 'Amy', 'David', 'Carrie', 'Barbara', 'Zach']`
It is worth noting that you can achieve pretty much the same outcomes using list comprehensions. For instance, we can generate our list of even and odd numbers like this ...`>>> [x for x in range(1,21) if x%2 == 0]` `[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]` `>>> [x for x in range(1,21) if x%2 == 1]` `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]` ... which some programmers find easier / clearer.
This is getting silly. Stop asking me!
In Haskell, we use the
`filter` function in a similar way. This is the blueprint ...
... where the
predicate is a conditional statements which returns `True` or `False` and is applied to each element of the list. If the predicate is `True` , the list value is returned, if it is `False` , it is not. The `filter` function returns a list of values which satisfy the predicate.We can filter out all odd values from a list like this ...
`[2,4]` Notice the result of the application of
`even` in this case is very different to that of its use in the `map` function. The predicate can look like part of a conditional statement, as in these examples ...
`[1,2,3,4,5]`
`[3]` ... but perfectly valid as long as the ranges are predictable!
Both these predicates are
statements not functions (technically, `>` and `==` are functions but we'll ignore that for now) and take parameters in a prefix fashion, i.e. before the operator. So `>0` is like `x>0` . So, these are equivalent to the following `filter` operations using lambda functions ...
`[1,2,3,4,5]`
`[3]` Once again, it's worth noting that we can use list comprehensions in Haskell to achieve the same outcome ...
`[1,2,3,4,5]`
`[3]` No, no no!
We could define a slightly more complicated (and totally pointless)
`even` number filter in three slightly different ways (just to prove some points and introduce some other points) ...a) Using the built in `even` function as the predicate. We've seen this before :)
`[2,4,6,8,10]` b) Using a lambda function. This uses the Haskell `mod` operator which prefixes it's arguments.
`[2,4,6,8,10]` c) Using a lambda function. I've modified the `mod` operator to an infix operator by surrounding it with backticks.
`[2,4,6,8,10]` d) Defining a separate function and using that as the predicate. Sometimes better, sometimes not.
`[2,4,6,8,10]` e) Using function composition. You should have met function composition in Task 1.1 - you might need to revise it!
`[2,4,6,8,10]` The predicate is evaluated from
right to left. For each value in the list, the result of the `mod` operation is passed to the `==0` statement. If the output of that is `True` , the value is added to the filtered list.` 1 : 1 `mod` 2 = 1 ` ` 2 : 2 `mod` 2 = 0 ` ` 3 : 3 `mod` 2 = 1 ` ` 4 : 4 `mod` 2 = 0 ` ` 5 : 5 `mod` 2 = 1 ` ` 6 : 6 `mod` 2 = 0 ` ` 7 : 7 `mod` 2 = 1 ` ` 8 : 8 `mod` 2 = 0 ` ` 9 : 9 `mod` 2 = 1 ` `10 : 10 `mod` 2 = 0 ` Even though we learnt that the open circle (∘) represents function composition, there is no open circle available to show this in Haskell (or any other language), so the dot is used. Sorry :(
Reduce / FoldFinally, the
`reduce` (or `fold` ) function completes our toolkit of standard functional programming, er, tools. Unfortunately, the `reduce` function is not built into the standard Python library so we need to import it ...`from functools import reduce` ... before we can use it. Basically, reduce takes a list and, through the application of a function, reduces the list to a single value.
The reduce operation using a lambda function
The
`reduce` function is not built into the Python standard library, so it requires importation. The blueprint is ...
The function takes
two arguments due to the way it operates on the list. Consider this simple `reduce` operation which adds up a list of numbers.`>>> reduce(lambda x,y:x+y,[1,2,3,4,5],0)` `15` The operation of
`reduce` is essentially `(((((0+1)+2)+3)+4)+5)` folding from the left side of the list (technically a left fold). The fold operation is recursive. Starting with the (optional) initialiser, the function adds this to the first item in the list, then adds the result of this addition to the second value in the list and so on until only one value is left which it returns.You can also use
`reduce` to work out the maximum number in a list of values.`>>> reduce(lambda a,b:a if a>b else b, [45,12,102,14,9])` `102` Reduce also works with strings.
`>>> names = ['British','Broadcasting','Corporation']` `>>> reduce(lambda a,b:a+b[0],names,'')` `'BBC'` Notice that the
initialiser for this operation is an empty string. Try it without that and see what happens.
There is no reduce function in Haskell; it's called
fold. In fact there are two different fold functions in Haskell, `foldl` (fold left) and `foldr` (fold right). They both operate recursively eating up values from the left hand side and the right hand side of the list respectively.The blueprint for the functions is ...
```
``` The initialiser gives a special variable called the
accumulator its initial value. The `foldl` function recursively adds the accumulator to each item in the list whereas the `foldr` function recursively adds each item in the list to the accumulator (i.e. the reverse).Here is a nice way of looking at both situations based on a common food chain.
Demonstrating a left fold
In a
left fold, the food chain is accumulated from the owl to the grass; from left to right. The owl eats the mouse, then the owl (which has eaten the mouse) eats the grasshopper and finally the owl (which has eaten the mouse and the grasshopper) eats the grass.Demonstrating a right fold
In a
right fold however, the food chain is accumulated from the grass to the owl; from right to left. The grasshopper eats the grass then the mouse eats the grasshopper (which has eaten the grass) then the owl eats the mouse (which has eaten the grasshopper which has eaten the grass). In any event, the owl is full up.Enough about food. Consider these two real examples ...
`15` In essence, the
`foldl` evaluates as `(((((0+1)+2)+3)+4)+5) = 15`
`15` In essence, the
`foldr` evaluates as `(1+(2+(3+(4+(5+0))))) = 15` In this instance, the order of the fold makes
no difference to the result since addition is commutative (order is unimportant). However, subtraction is not and the following two functions yield very different results.
`-15`
`3` Why does this happen? Let's evaluate the expression manually to find out ...
Do not attempt this section unless you are ready for a challenge!This situation gets even more complicated with function composition and we are really getting way out of our depth here! However, when we were using Python, we managed to generate an acronym for the British Broadcasting Corporation using a Lambda function. However, the same process in Haskell is slightly more confusing. The
`foldl` and `foldr` functions evaluate composed functions in the reverse order so, to get the same outcome, we have ...
`"BBC"`
`"BBC"` However, trying to use normal function composition causes problems ...
`"BCorporation"`
`"BBC"` The
`foldl` function evaluates like this :`(take 1 (take 1 (take 1 "" ++ "British") ++ "Broadcasting") ++ "Corporation)` `(take 1 (take 1 "British" ++ "Broadcasting") ++ "Corporation)` `(take 1 "BBroadcasting" ++ "Corporation)` `"BCorporation"` The
`foldr` function evaluates like this :`(take 1 "British" ++ (take 1 "Broadcasting" ++ (take 1 "Corporation")))` `(take 1 "British" ++ (take 1 "Broadcasting" ++ "C"))` `(take 1 "British" ++ "BC")` `"BBC"` ... which explains it all, quite clearly!
... and no task!
Back to Haskell for this last section and the fabulous 'Learn You a Haskell for Great Good' - my favourite book!
Hello little caterpillar!
How about these?
- Visit Haskell's documentation page to find a list of resources to help you learn Haskell.
- Read and enjoy 'Learn you a Haskell for Great Good!' - Holy Sh*t!
- Read this series of interesting articles on how to be a functional programmer.
END OF TOPIC ASSESSMENT |