Functional programming paradigm study guide

1. Read a function type precisely

Start with the arrow notation. In f: A → B, identify the domain A and the co-domain B before considering any example. The domain is the set from which inputs are chosen. The co-domain is the set from which outputs are chosen. The specification does not require that every co-domain value is returned, so an answer should say that the co-domain contains possible output values rather than claiming it is exactly the set of outputs.

A useful exam check is to ask: “What kind of object can be supplied, and what kind of object can be returned?” For f: integer → integer, one integer is supplied and one integer is returned. For integer × integer → integer, the input is a pair of integers and the result is one integer. This explains why add(3,4) can be described as taking two arguments informally while its type treats (3,4) as one pair-valued argument.

2. Explain first-class status using consequences

A function is first-class when it can be used in the ways described for first-class objects. It may appear in an expression, be assigned to a variable, be supplied as an argument, or be returned from a function call. When answering a question, do not merely state that functions are “special values”; connect the definition to one or more of these permitted uses. Partial application is an important example because supplying an argument can produce another function.

3. Trace partial application carefully

For a two-argument function such as add, use the sequence:

1. Begin with the curried view add: integer → (integer → integer).
2. Apply the first integer, for example add 4.
3. Recognise that the result is a function of type integer → integer.
4. Apply that returned function to another integer.
5. The final result is an integer, representing the second integer added to 4.

The brackets may be dropped, so the same type can be written integer → integer → integer. The important reasoning is that one argument is supplied after another; after the first application, the result is still a function.

4. Trace composition in the correct order

For f: A → B and g: B → C, the output type of f matches the input type of g. Therefore g ○ f is valid, has domain A and co-domain C, and applies f first. With f(x) = x + 2 and g(y) = y³, first calculate f(x), obtaining x + 2. Then use that result as the input to g, obtaining (x + 2)³. Reversing the order would describe a different operation and should not be written as the same composition.

5. Self-check questions

• In f: A → B, which set supplies inputs and which set supplies possible outputs?
• Why can a co-domain contain values that are never produced?
• What four uses demonstrate that a function is first-class?
• Why is the input to integer × integer → integer described as a pair?
• After applying the first argument in integer → integer → integer, what kind of object remains?
• In g ○ f, which function is applied first, and why must the intermediate types match?

A strong answer should use the notation, state the order of operations, and distinguish a returned function from a final data value.