Laziness / non-strictness

Question 1

What is the general process of evaluation of a functional program?

Answer 1

Evaluation process of a functional program is process of application of functions to their argements and process of reduction of expressions until all the applications are reduced.

There are different ways to do the reductions.

Question 2

Define:

Outermost reduction.

Answer 2

Outermost reduction is the expression reduction strategy where outermost function is reduced first and only then are arguments reduced.

This leads to a possibly better time properties because it reduces only the arguments which are needed and not all of them before the outermost function is applied.

Question 3

Define:

Reduction graph.

Answer 3

In order to prevent multiple reductions of the same expression, expression structure is represented as a graph where shareable expressions are represented as only one node and reused after they are reduced once.

Question 4

Define:

Reducible expression (redex)

Answer 4

Reducible expression or redex a subexpression in a graph which is reducible to its reduced form.

Question 5

Outermost graph reduction.

Answer 5

Outermost graph reduction is the outermost reduction strategy applied to graph reduction. This combination yields the least number of reductions possible and never reduce expressions which are not needed during program execution.

Question 6

Define:

Normal form

Answer 6

When reduction graph/subgraph has no subexpressions to reduce, we say that it is in its normal form.

• graph has to be finite to be in normal form
• graph has to have no cycles to be in normal form.

Question 7

Explain:

Data constructors and normal form.

Answer 7

Data constructors do not have the right side to reduce to, so they are in normal form. There are no reduction rules for them and they get reduced only when deconstructed and then values used.

Question 8

Define:

When is an expression in WHNF (weak head normal form)

Answer 8

Expression is in Weak Head Normal Form WHNF when its outermost redex is data constructor and it contains as arguments unevaluated expressions or thunks.

Unevaluated expressions or thunks are expressions which are not in the WHNF.

Question 9

Explain:

Space leak in the lazy evaluation strategy.

Answer 9

Lazy evaluation can lead to space leaks if it starts growing expression graph due to postponing the reduction of the expression.

Example:

• spaceLeakSum (x:xs) = x + spaceLeakSum xs

This one will just build up the expression structure before reduced.

Question 10

Explain:

fixity

Answer 10

Fixity definition is the way to add the binding precedence to operators.

• infix, infixl, infixr - defines how the associativity works
• [0..9] - defines the precedence. 0 the least strong
• function application takes always the highest precedence
• operators missing fixity are “infixl 9” by default

Question 11

Explain:

Enforcing strictness with seq (example of foldl’)

Answer 11

foldl can be implemented in a strict way in order to prevent memory leak by enforcing evaluation of the sum application before diving into recursion. That way we’ll not build up the growing sum thunk.

strictFold :: (a -> a -> a) -> a -> [a] -> a
strictFold _ z [] = z
strictFold f z (x:xs) = let a’ = f z x
in seq a’ (strictFold f a’ xs)

Question 12

Explain:

Concept of infinite lists.

Answer 12

In Haskell, due to lazy evaluation, it is possible to work with infinite lists. These lists are defined by the rules for generation of the next element.

• iterate f x = x : iterate f (f x)
  
  • generates a list which applies function over and over how lists builds.
• [0..] - infinite list of integers

In general, the infinite list is a provider of values and the caller has to impose the condition for exit.

Question 13

Explain:

Benefit of lazy evaluation for implementation of user defined control flow functions.

Answer 13

– benefit of lazy evaluation is that we can implement control flows
– which avoid execution of the invalid code path.
– This is not easy in the programming language which doesn’t have lazy
– evaluation because all the code paths have to be evaluated before the control
– flow function would be reduced.
myIf :: Bool -> a -> a -> a
myIf True x y = x
myIf False x y = y

let x = 0
myIf (x /= 0) (100 / x) 0

Question 14

Define and explain:

type keyword

Answer 14

type keyword allows for defining type aliases in the code making different names for the already existing types.

type AddressBook = Array Adress