chinese food 2

What is the main reduction rule of the semantic of the λ-calculus?

B-reduction

A list [1,2,3] in Haskell is syntactic sugar for…

1 : 2 : 3 : [] wwhich is equivalent to 1 : (2 : ( 3 : []))

Which kind of recursion is an important concept in functional programming?

tail recursion

What does it mean that Haskell is a pure functional programming language?

the evaluation of expressions has no side-effects

What language feature is not a feature of haskell?

mutable variables

Which technique can be used to transform a recursive function into an equivalent tail recursive function?

Accumulating parameters

In the haskell function definition

product [] = 1
product (x:xs) = x * product xs

pattern matching

Which haskell language feature is used wwhere other languages would use NULL pointers?

algebraic data types, in particular co-products

What makes a recursive function definition tail recursive?

it contains exactly one recursive call and its return value is immediately returned by the calling function

Which of the following expressions is not equivalent to the section (^2)

\x → 2^x

Evaluate the expression
a’b’c
where
a = “a”
b = (++)
c = “c”

“ac”

Evaluate the following haskell fold expression:

foldr (+) 0 [1, 2, 3]

6

Evaluate the following Haskell fold expression:

foldr (-) 0 [1, 2, 3]

2

Evaluate the following Haskell fold expression:

foldl (+) 0 [1, 2, 3]

6

Evaluate the following Haskell fold expression:

foldl(-) 0 [1, 2, 3]

-6

Evaluate the following Haskell fold expression:

foldr (+) 5 [1, 2, 3]

11

Evaluate the following Haskell fold expression:

foldl (-) 5 [1, 2, 3]

-1

What is the type of the following polymorphic Haskell function? max a b = if a <= b

max a b = if a <= b then b else a

max : : Ord a => a → a → a

What is the type of the following polymorphic Haskell function? head (x:xs) = x

head (x:xs) = x

head : : [a] → a

What is the type of the following polymorphic Haskell function?

length [] = 0
length (a:as) = 1 + length as

length : : Num n => [a] → n

What is the type of the following polymorphic Haskell function?
maximum = foldll max
where
max a b = if a <= b then b else a
and where foldll is the following function from Data.List:
foldll : : Foldable t => (a → a → a) → t a → a

maximum : : (Foldable t, Ord a) => t a → a

Consider the Haskell function definition
const x _ = x
Evaluate
const (1+) 10 100

101

Consider the Haskell function definition
const x _ = x

What is the type of const?

const : : a → b → a

Consider the Haskell function definition
const x_ = x

Evaluate the Haskell expression
foldr (const (1+)) 0 [2, 31, 1]

3

Consider the Haskell function definition
const x _ = x
Evaluate the Haskell expression
foldl (const (1+)) 0 [2, 3, 1]

2

Consider the haskell function definition
(++) [] ys = ys
(++) (x:xs) ys = x: (xs++ys)
Evaluate the Haskell expression “c” “++” “++”

“c++”

Consider the haskell function definition
(++) [] ys = ys
(++) (x:xs) ys = x: (xs++ys)

What is the type of (++)?

(++) : : [a] → [a] → [a]

Consider the haskell function definition
(++) [] ys = ys
(++) (x:xs) ys = x: (xs++ys)

What does the function foldr (++) [] do?

flatten a list of lists

Consider the Haskell function
flip f a b = f b a
Evaluate flip (-) 1 2

1

Consider the Haskell function
flip f a b = f b a
What type is flip?

flip : : (a→b→c) → (b→a→c)

Consider the Haskell function
flip f a b = f b a
Evaluate the expression
foldl (flip(:)) [] “drawer”

“reward”

Consider the Haskell data type and function definitions: data (a,b) = (a,b)

fst (a, _) = a
snd (_, b) = b
which kind of algebraic data type is (a, b)?

a product

Consider the Haskell data type and function definitions: data (a,b) = (a,b)

fst (a, _) = a
snd (_, b) = b
What kind of functions are fst and snd?

projections

Consider the Haskell data type and function definitions: data (a,b) = (a,b)

fst (a, _) = a
snd (_, b) = b

Evaluate the expression
let f p = fst p - snd p in f(1, 3)

-2

Consider the following Haskell function definitions:
foldr _ z [] = z

foldr f z (x:xs) = f x (foldr f z xs)

foldl _ z [] = z
fold f z (x:xs) foldl f (f z x) xs

Which of these functions are tail recursive?

foldl but not foldr

Consider the following Haskell function definitions:
foldr _ z [] = z

foldr f z (x:xs) = f x (foldr f z xs)

foldl _ z [] = z
fold f z (x:xs) foldl f (f z x) xs

What is the type of foldr?

foldr : : (a→b→b) →b → [a] → b

Consider the following Haskell function definitions:
foldr _ z [] = z

foldr f z (x:xs) = f x (foldr f z xs)

foldl _ z [] = z
fold f z (x:xs) foldl f (f z x) xs

What is the type of foldl?

foldl : : (b→a→b) → b → [a] → b

Consider the following Haskell data type definition: data Maybe a = Nothing | Just a

What can Maybe be used for?

optional values

Consider the following Haskell data type definition: data Maybe a = Nothing | Just a

instance Foldable Maybe
wwhere
foldr _ z Nothing = z

foldr f z (Just x) = f x z

and keep in mind that functions like
sum : : (Foldable t, Num a ) => t a → a
are defined in terms of foldr.

Evaluate the expression sum Nothing

0

Consider the following Haskell data type definition: data Maybe a = Nothing | Just a

instance Foldable Maybe
wwhere
foldr _ z Nothing = z

foldr f z (Just x) = f x z

and keep in mind that functions like
sum : : (Foldable t, Num a ) => t a → a
are defined in terms of foldr.

Evaluate the expression sum (Just 2)

2