Fundamentals of Functional Programming

What Fundamentals of Functional Programming covers

Function types, domain and co-domain, composition and partial application, higher-order functions, and lists built from a head and a tail. Examined on Paper 2.

The 4 subtopics

Each one has its own page.

• Function Types, First-Class Objects and Function ApplicationRecall questions on function types, domain and co-domain, functions as first-class objects and why that matters, and function application and the type of a call such as add(3, 4).Open →
• Partial Function Application and CompositionRecall questions on partial function application and how its types are written and grouped, practical reasons to use it, and composing functions and working out g ○ f and f ○ g.Open →
• Writing functional programsRecall questions on map, filter and reduce, what each does to a list of n elements, and composing them to answer a question about a set of data.Open →
• Lists in functional programmingRecall questions on the head and tail of a list, the empty list, what happens when the head of an empty list is requested, and the seven basic list operations.Open →

What you need to know

Answer each one before you reveal it.

Take Fundamentals of Functional Programming further

The same content, four other ways.

Commonly confused

Pairs that lose marks when they are blurred together.

• Head vs Tail

  Head: the first single element of a non-empty list. Tail: the list remaining after its first element is removed.

• Map vs Filter

  Map: a higher-order operation transforming every list element. Filter: a higher-order operation retaining elements satisfying a condition.

• Domain vs Co-domain

  Domain: the set from which a function accepts inputs. Co-domain: the declared set in which a function produces outputs.

Questions from this topic

Each one with the model answer underneath.

1. 1

   What is a function type, and how is it written?

   Model answer

   A function type records what kind of thing a function consumes and what kind of thing it produces, and nothing whatever about how the work is done. An arrow separates the two. For a function f, the notation f: A → B declares its type; whatever stands to the left of the arrow, here A, is the argument type, and whatever stands to the right, here B, is the result type. So sqrt: real → real takes a real number and hands back a real number, while length: string → integer takes a string and hands back a whole number. The type alone is enough to catch a mistake such as applying length to a number.

2. 2

   In the function type f: A → B, what are A and B called?

   Model answer

   A is called the domain and B is called the co-domain.

3. 3

   Define domain and co-domain.

   Model answer

   Every function is defined against two sets. The domain is the one its inputs must be drawn from — anything outside it may not be fed in. The co-domain is the one its outputs are guaranteed to fall within. Written f: A → B, the domain is A and the co-domain is B, so each argument must belong to A and each result must belong to B. For length: string → integer the domain is the set of all strings and the co-domain the set of integers; note that the co-domain need not be used up, since no string has a negative length.

4. 4

   Loosely speaking, what is a function?

   Model answer

   Loosely, it is a rule of assignment: take any member of one set — the inputs — and the rule pairs it with exactly one member of a second set, the outputs, though it need not reach every member of that second set. Consider f: {Monday, Tuesday, ..., Sunday} → {1, 2, ..., 7} under the rule that gives each day its position in the week, sending Monday to 1, Tuesday to 2 and so on. Its domain is the set of weekday names and its co-domain the whole numbers from 1 to 7, and this particular rule does happen to use every one of them.

5. 5

   Is it necessary for every member of the co-domain to be an output of the function? Explain.

   Model answer

   No. Not all of the co-domain's members need be outputs. The co-domain simply states the set the outputs are drawn from; it does not promise that every member of it actually occurs. For example square: integer → integer has the whole set of integers as its co-domain, but no negative integer is ever produced, and neither is 2 or 3. The values that genuinely do occur — sometimes called the range or image — may be a proper subset of the co-domain. By contrast, every member of the domain must have an output, because a function assigns a result to each element of its domain.

6. 6

   What is always true about the domain and co-domain of a function?

   Model answer

   They are always subsets of objects in some data type. The domain and co-domain are not arbitrary collections: each is drawn from a data type such as integer, real, character, string or boolean, and may be the whole of that type or a restricted part of it. For example a function might have the integers from 1 to 12 as its domain, which is a subset of the objects of type integer.

What is inside Levo

Six ways to work the same material.

Fundamentals of Functional Programming revision questions

What does Fundamentals of Functional Programming cover in AQA A-Level Computer Science?

4 subtopics: function types, first-class objects and function application, partial function application and composition, writing functional programs and lists in functional programming. Each one has its own page with questions and model answers.

How is Fundamentals of Functional Programming organised?

By the AQA 7517 specification, subtopic by subtopic, so it matches the order you are taught it in.