1/112
Looks like no tags are added yet.
The binding of the keyword double to the data type "double" was done at...
Language design time
What does it mean that Haskell is a Pure Functional Programming Language?
The evaluation of expressions has no pure side effects
Which Language features is not a feature of Haskell
Mutable Variables
The average case time complexity to access a random element is
O(1) array and O(n) for lists
The average case time complexity to insert/delete an element is
O(n) for array and O(1) for lists
Which technique can be used to transform a recursive function definition into an equivalent tail recursive function definition?
accumulating parameters
product [ ] = 1
product (x : xs) = x + product xs
pattern matching
max ab = a
max::ord a => a -> a -> a
head (x:xs) = x
head :: [a] -> a
Which Haskell language feature is used where other languages would use NULL pointers?
algebraic data types, in particular sum/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
foldr(+) 0 [1,2,3]
6
foldl(-) 0[1,2,3]
2
foldr(-) 0[1,2,3]
-6
foldr(+) 5[1,2,3]
11
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 const?
const :: a -> b -> c
Consider the Haskell function definition
const x __ = x
Evaluate
foldr (const(1+)) 0[2,1,3]
3
Consider the Haskell function definition
const x __ = x
Evaluate
fold1(const(1+)) 0 [2,1,3]
4
foldr (++) [ ] [ x, y, z]
what is the data type?
[[a]] -> [a]
Consider the Haskell Function definition
(++) [ ] ys = ys
(++) (x:xs) ys = x : (xs++ys)
Evaluate
"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
A list [1, 2, 3] in Haskell is syntactic sugar for
1: (2: (3: [ ]))
Consider the following Haskell function definitions:
foldr _ z [ ] = z
folder f z (x :xs) = f x (foldr f z xs)
foldl _ z [ ] = z
foldl f z (x:xs) = foldl f (f z x) xs
Which of these functions are tail recursive?
foldl but not not foldr
Consider the following Haskell function definitions:
foldr _ z [ ] = z
folder f z (x :xs) = f x (foldr f z xs)
foldl _ z [ ] = z
foldl 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
folder f z (x :xs) = f x (foldr f z xs)
foldl _ z [ ] = z
foldl 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 and function definitions:
data (a,b) = (a,b)
fst (a, _ ) = a
snd ( _ , b) = b
Evaluate the expression
let f pp = snd p - fst p in f(1, 3)
2
Consider the following Haskell data type and function definitions:
data (a,b) = (a,b)
fst (a, _ ) = a
snd ( _ , b) = b
What algebraic data type is (a,b)?
product
Consider the following 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 following Haskell data type definitions:
data Maybe a = Nothing | Just a
What can Maybe be used for?
optional values
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression sum Nothing
0
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression sum ( Just 2 )
2
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression product Nothing
1
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression product ( Just 2 )
2
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression length ( Just "abc")
1
Consider the following Haskell data type definitions:
data Maybe a = Nothing | Just a
instance Foldable Maybe
where
foldr _ z Nothing = z
foldr f z (Just x) - f x z
Evaluate the expression length nothing
0
Const int x = 5
functional or imperative?
functional
void swap (int *a, int *b) {
int h = *a ;
*a = *b;
*b = h;
functional or imperative?
imperative
int f (int x) {
return 2 *x+1;
}
functional or imperative?
functional
x + x + 5
functional or imperative?
imperative
Which of the following is an example of a sum/co-product type in Haskell?
data shape = Circle Float
| Rectangle Float Float
In Haskell, which keyword is used to define algebraic data types?
data
What is the purpose of deriving clause in Haskell data type declarations?
automatically generates instance definitions for certain type classes
What is a recursive data type?
data type that refers to itself and definition
type def purpose?
?
Static void swap ( int *a , int i, int j ){
int h = a[ i ]
}
a[ i ] = a[ j ]
Record (also called structure of struct)
Product
Enumerated type
sum/co-product
Tuple
Product
Tagged union
sum/co-product
qsort [ ] = [ ]
qsort (x : xs) = sortp xs [ ] [ ]
where
sortp [ ] us vs = qsort us ++ x : qsort vs
sortp (y :ys) us vs = ?
if y < x then sort p ys ( y : us) us
else sort p ys (y : us)
How many times will each element in the input list xs?
2
qgsort [ ] = [ ]
qsort (x : xs) = sortp xs [ ] [ ]
where
sortp [ ] us vs = qsort us ++ x : qsort vs
sortp (y :ys) us vs = ?
if y < x then sort p ys ( y : us) us
else sort p ys (y : us)
how many times will each element in the input list x?
1
qsort [ ] = [ ]
qsort (x : xs) = sortp xs [ ] [ ]
where
sortp [ ] us vs = qsort us ++ x : qsort vs
sortp (y :ys) us vs = ?
if y < x then sort p ys ( y : us) us
else sort p ys (y : us) gsort [ ] = [ ]
Which of the following is true?
sortp is tail recursive but qsort is not
Lecture note Tree
data Tree a = node a (Tree a) (Tree a) | Leaf
countNodes Leaf = 0
(Nodes_left right) = 1 + countNodes left + countNodes right
how many nodes?
3 nodes
?
x : merge xs (y:ys)
int main ( ) {
Node n1 = {1, Null};
Node n2 = {2, &n1};
Node n3 = {3, &n2};
printList (&n3);
return 0;
}
3 2 1
?
countLeaves = 4
Which of the these languages does not have a static type system by default?
Python
What Characterizes a static type system?
The types of values have to be determined at compile time/before runtime
What does the sizeof operator in C return?
The size of a data type in bytes
Runtime stacks enable
All of the above
- Recursion
- Unique Sets of parameters per subroutine activation
- Unique Sets of variables per subroutine activation
In C, we first declare an int* then assign it via malloc, then without explicitly deallocating it, assign it another value from malloc. What did we create?
A memory leak
A generator implemented using the yield keyword in C# or Python behaves similar to which Haskell feature?
Lazy Lists
Generic Functions in c++ are specifically using which keyword?
Templates
What is the main reduction rule of the operational semantic of lamda-calculus?
Beta Reduction
Runtime stacks enable
All of the above
- Recursion
- Unique Sets of parameters per subroutine activation
- Unique Sets of variables per subroutine activation
Consider the following C program:
01 #include
02 #include
03
04 int main() {
05 int *p;
06
07 p = malloc(sizeof(int));
08
09 if (p == 0) {
10 fputs("ERROR: Out of memory\n", stderr);
11 return 1;
12 }
13
14 *p = 42;
15 printf("%d\n", *p);
16
17 free(p);
18
19 return 0;
20 }
In which lines of this program will heap memory be allocated and/or deallocated?
7 and 17
Consider the following C program:
01 #include
02 #include
03
04 int main() {
05 int *p;
06
07 p = malloc(sizeof(int));
08
09 if (p == 0) {
10 fputs("ERROR: Out of memory\n", stderr);
11 return 1;
12 }
13
14 *p = 42;
15 printf("%d\n", *p);
16
17 free(p);
18
19 return 0;
20 }
In which lines of this program are we referring to static memory?
10 and 15
Consider the following C program:
01 #include
02 #include
03
04 int main() {
05 int *p;
06
07 p = malloc(sizeof(int));
08
09 if (p == 0) {
10 fputs("ERROR: Out of memory\n", stderr);
11 return 1;
12 }
13
14 *p = 42;
15 printf("%d\n", *p);
16
17 free(p);
18
19 return 0;
20 }
Is the heap memory really necessary in the above program?
No, since we're only allocation memory for one int, we could have used the stack for that
Consider the following C program:
01 #include
02 #include
03
04 int main() {
05 int *p;
06
07 p = malloc(sizeof(int));
08
09 if (p == 0) {
10 fputs("ERROR: Out of memory\n", stderr);
11 return 1;
12 }
13
14 *p = 42;
15 printf("%d\n", *p);
16
17 free(p);
18
19 return 0;
20 }
How would the program's behavior change if we remove line 17?
The behavior wouldn't change, since the heap memory allocated in line 7 would be freed in line 19 when the process terminates
A list [ 1, 2, 3 ] in Haskell is syntactic sugar for....
1:2:3: [ ]which is equivalent to 1: (2: (3: [ ]))
What is the main advantage of generic programming?
It improves source code re-usability
What is the type of the following polymorphic Haskell function?
head (x:xs) = x
head :: [a] -> a
What is the type of the following polymorphic Haskell function?
tail (x:xs) = xs
tail :: [a] -> [a]
What is the type of the following polymorphic Haskell function?
max a b = if a
maximum :: (Foldable t, Ord a) => t a -> a
Which C#/LINQ keywords are used to implement generators?
select & yield
Which of the following statements about the stack and the heap is incorrect?
The stack is usually larger than the heap
Translate the C# generator Quux into Haskell Function
quux :: [Int] -> [Int]
Using Lazy Lists:
quux xs = 1 : map (3*) xs
How many times will this yield return
var ns = Quux(Quux( new int [ ]{2,5})
7
What is the output of the following code?
var ns = Quux(Quux(new int[ ] {1, 3}));
foreach (var n in ns)
Console.WriteLine(n);
1
3
18
45
Consider the following generator written in C#:
IEnumerable
{
yield return 1;
foreach (var n in seg yield return 3 * n;
}
Translate the C# generator Quux into Python.
def quux(seq):
yield 1
for n in seq:
yield 3 * n
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in normal order i.e. leftmost, outermost redux first:
What is the first step?
(1 + 2) (1 + 2)
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in normal order i.e. leftmost, outermost redux first:
What is the second step?
3 * (1 + 2)
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in normal order i.e. leftmost, outermost redux first:
What is the third redux?
3 * 3
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in normal order i.e. leftmost, outermost redux first:
What is the fourth redux?
9
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in applicative order i.e. leftmost, outermost redux first:
What is the first step?
(/x -> x * x) 3
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in applicative order i.e. leftmost, outermost redux first:
what is the second step?
3 * 3
Evaluate the Haskell lambda-expression:
(\x -> x * x) (1 + 2)
step-by-step in applicative order i.e. leftmost, outermost redux first:
what is the third step?
9
Match the language typically executed:
C
Compiled to native code
Match the language typically executed:
C++
Compiled to native code
Match the language typically executed:
C#
Compiled (to managed code that is then executed by the .NET runtime)
Match the language typically executed:
Python
Interpreted (after being compiled to byte code)
int a = 5;
int b [1000]
int c (int d) {return a * b[d];}
Match the symbol with the memory segment (where money will be allocated to store its value).
a
static, Data Segment
Match the language typically executed:
Haskell
Compiled to native code or interpreted
int a = 5;
int b [1000]
int c (int d) {return a * b[d];}
Match the symbol with the memory segment (where money will be allocated to store its value).
*b
static, BSS Segment
int a = 5;
int b [1000]
int c (int d) {return a * b[d];}
Match the symbol with the memory segment (where money will be allocated to store its value).
*c
static, text segment
int a = 5;
int b [1000]
int c (int d) {return a * b[d];}
Match the symbol with the memory segment (where money will be allocated to store its value).
d
Automatic(static)
Match the generic programming features to the languages
Polymorphic types and type classes
Haskell
Match the generic programming features to the languages
Mainly void*
C