Functional Programming and Applications

Question 1

What is a programming paradigm?

Answer 1

A programming paradigm is a way to categorise programming languages based on their features.

Question 2

What is imperative programming?

Answer 2

Instruction sequences for a von Neumann computer

Question 3

How are functions coded in imperative programming?

Answer 3

Functions are implicitly coded in every step required to solve a problem.

Question 4

What is functional programming?

Answer 4

A programming paradigm without mutable variables, assignments, loops and other imperative control measures.

Question 5

How does functional programming create maintainable software?

Answer 5

It uses pure functions to create maintainable software

Question 6

How do you compare imperative and functional programming paradigms?

Answer 6

Imperative:
Program: a sequence of instructions for a von Neumann m/c.
Computation by instruction execution.
Iteration.
Modifiable or updatable variables. (Mutable data structures)
Does not support independent understanding - harder to reason about.
Low level specification (HOW)

Functional:
Program: a collection of function definitions (m/c independent).
Computation by term rewriting.
Recursion.
Constants. (Immutable data structures)
Supports independent understanding.
High level specification (WHAT)

Question 7

Show that, for any number x, sum [x] = x.

Answer 7

The only elements of [x] are x.
Sum sums the elements inside of the list such as sum []
essentially this is x + 0 = x
so sum [x] = x

sum [x]
= x + sum [] (applying sum)
= x + 0 (applying sum)
= x (applying +)

Question 8

Define a function product that produces the product of a list of numbers, and show using your definition that product [2,3,4] = 24

Answer 8

product [] = 1
product (n:ns) = n * product ns

eg.
product [2,3,4]
= 2 *(product [3,4])
= 2 ( 3 (product [4]))
= 2 ( 3 ( 4 *(product [])))
= 2 ( 3 (4 * (1)))
= 24

Question 9

How should the definition of qsort be modified so that it returns a list in its descending order?

Answer 9

Swap smaller and larger

qsort [] = []
qsort (x:xs) = qsort larger ++ [x] ++ qsort smaller
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]

Question 10

What is a type?

Answer 10

A type is a name for a collection of related values.

Question 11

What is type inference?

Answer 11

The process during which every well formed function’s types can be calculated during compile-time.

Question 12

What is a list?

Answer 12

A sequence of values with the same type. Any length.

Question 13

What is a tuple?

Answer 13

A sequence of values of different types. Fixed length.

Question 14

What is a function?

Answer 14

A mapping of values from one type to values from another type.
eg. Char -> Char, Char -> Bool

Question 15

What is a curried function?

Answer 15

A curried function is a function that takes multiple arguments one at a time, and returns a function as a result.

Question 16

Give an example of a curried function?

Answer 16

add :: Int -> (Int, Int)
add x y = x+y

Question 17

How can functions with more than two arguments be curried? Give an example.

Answer 17

Functions with more than two arguments can be curried by returning nested functions.

example:

mult :: Int -> (Int -> (Int -> Int))
mult x y z = xyz

Question 18

Why are curried functions useful?

Answer 18

Curried functions are more flexible than functions on tuples,
because useful functions can often be made by applying a curried function.

example:
add’ 1 :: Int -> Int
take 5 :: [Int] -> [Int]
drop 4 :: [Int] -> [Int]

Question 19

What are the two conventions of curried functions?

Answer 19

Convention 1: arrows associate to the right: Int -> Int -> Int -> Int means Int -> (Int -> (Int ->. Int))
Convention 2: function application associates to the left: mult x y z means ((mult x)y)z

if these conventions were not there, we would have got Int -> (Int -> (Int ->. Int)) and ((mult x)y)z

Question 20

What is polymorphism?

Answer 20

A function is polymorphic (of many forms) if its type contains one or more type variables.

example:

length :: [a] -> Int

❖ head [] – exception raised
❖ zip [1] [1,2] = [(1,1)]
❖ take 10 [1,2,3] = [1,2,3]

Question 21

What is ad hoc polymorphism / overloading?

Answer 21

Ad hoc polymorphism, also called overloading, is when a function’s type contains one or more class constraints.

Question 22

Give an example of ad hoc polymorphism / overloading.

Answer 22

sum :: Num a => [a] -> a

For any numeric type a (ie, a type that is an “instance” of the class Num), sum takes a list of values of type a and returns a value of type a.

Num a is a “class constraint”, whose general form is C a, where C is the name of a class and a is a type variable.

Constrained type variables can be instantiated to any types that satisfy the constraints:
> sum [1,2,3]
6
a = Int

> sum [1.1,2.2,3.3]
6.6
a = Float

> sum [’a’,’b’,’c’]
ERROR
Char is not a numeric type

Question 23

What is a higher order function?

Answer 23

A higher order function is a function that can be arguments of other functions, and/or can be returned as results of other functions.

Question 24

Give an example of a higher order function.

Answer 24

twice :: (a → a) → a → a
twice f x = f (f x)

Question 25

Give three ways why higher order functions are useful.

Answer 25

Way 1: Common programming idioms can be encoded as functions within the language itself.

Way 2: Domain specific language can be defined as collections of higher order functions.

data Expr = Value Int | Add Expr Expr
eval :: Expr → Int
– Use higher-order functions to define eval.
– Reasoning is made easier when using higher-
order functions.

Way 3: Algebraic properties of higher order functions can be used to reason about programs.

Question 26

What is polyglot programming?

Answer 26

Polyglot programming refers to programming with multiple programming languages.
You also program in a polyglot environment.

Question 27

What are some potential problems of polyglot environments?

Answer 27

❖ Once claimed:
necessary path forward
task-specific frameworks ➔ different PLs

❖ But problems – e.g., different developers use
different languages create communication
problems …

Question 28

What is a multiparadigm programming language?

Answer 28

A multiparadigm programming language is a programming language with multiple programming paradigms.

Programming in a variety of styles, freely intermixing constructs from different paradigms.

Question 29

Give one claim and one caveat of multiparadigm programming languages.

Answer 29

❖ Claim: better productivity etc (different people talk in the same language!)

❖ Caveat: theoretical foundation unclear

Typing in multiparadigm PLs
❖ Unclear how to get a complete/correct typing system, if it
exists
❖ Problems, eg, with side-effects
❖ eg, Scala’s “closure” whose application value depends on the value of
the free variables in its expressions/bodies.

(An argument for multiparadigm PLs:
“Research results from the psychology of programming indicate that
expertise in programming is far more strongly related to the number of
different programming styles understood by an individual than it is the
number of years of experience in programming.”
The “goal of multiparadigm computing is to provide … a number of
different problem-solving styles” so that a programmer can “select a
solution technique that best matches the characteristics of the problem”
.
(T. Budd, the designer of Leda, a multiparadigm PL))

Question 30

What is mutual recursion?

Answer 30

Two functions are said to be mutually recursive if the first calls the second, and in turn the second calls the first.

Question 31

Define two Haskell functions by means of mutual recursion and use this as an example to explain your answer.

Answer 31

function 1:

evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs

function 2:

odds:: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs

Suppose there is a list [1,2,3,4,5,6,7,8].
When evens encounters a non-empty list, it processes the first element and delegates the rest of the work to odds.
When odds encounters a non-empty list, it skips the first element and delegates the rest of the work to evens.
This alternating pattern continues until the list is exhausted.

Question 32

What is lazy evaluation?

Answer 32

Expressions are evaluated as much as required to produce the final result.

Lazy evaluation = outermost reduction + sharing
Lazy evaluation does not require more reduction steps than the innermost evaluation. Lazy evaluation is used in Haskell.

Question 33

Give an example of lazy evaluation.

Answer 33

a = [1…]
take 30 a

Question 34

What is innermost reduction?

Answer 34

❖ Always selecting an innermost reducible expression to reduce
❖ Call by value

Question 35

What is outermost reduction?

Answer 35

❖ Always selecting an outermost reducible expression to reduce
❖ Call by name

Question 36

How do innermost and outermost reduction compare?

Answer 36

Consider a non-terminating expression
⊥ = tail ⊥
Eg, evaluating fst(1,⊥)
❖ Innermost: fst(1,⊥) = fst(1,tail ⊥) = fst(1,tail (tail⊥)) = …
❖ Outermost: fst(1,⊥) = 1

Termination
❖ Outermost reduction may give a result when the innermost
reduction fails to terminate.
❖ Also, for any expression, if there exists any reduction sequence
that terminates, then the outermost reduction also terminates and
gives the same result.

Number of reduction steps
❖ Efficiency in evaluation
❖ Outermost reduction may require more steps than the innermost
reduction

Consider square(3+4):
❖ 3+4 is evaluated twice in outermost reduction but only once in innermost one.
❖ Sharing – using pointers to indicate sharing of expressions during evaluation
square(3+4) = * * * (where * is 3+4) = * * * (where * is 7) = 49.