CPSC449 Midterm Questions

What is a Program?

Must be Executable by a computer

What kind of Programming Language is C?

C is an imperative language.

In imperative programming languages, what is the scope of variables

Variables are local to block/function/subroutine

What is functional programming?

Evaluation of expressions rather than running commands

Do pure functional languages include loops?

NO. keyword is PURE. they use recusion or higher-order functions

Can you convert Imperative functions into Haskell?

Yes, using recursion and higher order functions

what does the “.” operator do in Haskell? How many parameters does it take?

The dot operator is the composition function. (f((g)x). It takes 3 parameters: the input, the function f, and the function g.

What kind of evaluation does Haskell do? What does it do?

Haskell does “lazy” evaluation. It evaluates the same as PEMDAS/BEDMAS, doing the smallest operation that it needs to do.

What happens to your programs in GHCi if you quit the program?

it disappears, making you lose your functions

What format should modules and filenames be?

ALWAYS starts with a capital letter. Correct Declaration:
MyModule.hs
import MyModule

What format should subdirectories be?

Also must start with a capital letter:
import myModule

import ModSub.SubModule

What do literals evaluate to (ex. ghci> True)

itself! Literals evaluate to themself. In Haskell, literals have types determined by context (5 can be any type, instance of Num)

if-then-else statements in imperative languages can be represented in Haskell using…?

Guards!

in ASCII, digits 0 to 9 occupy a code block of numbers __ to __

48 to 57

to “infix” a function, what do you do? (ex: 1 plus 1)

backticks! 

How do you make a Ternary Operator (z ? x : y) into an if-else?

`if z, do x. else, y.

write the function between, if intended usage is to find the “middle” element

between :: Int -> Int -> Int -> Bool
between x y z
	| x >= y && y >= z = True
	| x <= y && y <= z = True
	| otherwise        = False

What is Mutual Recursion?

When two programs call each other recursively
Example:

isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n - 1)

isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n - 1)

In haskell, how are lists stored in code?

a linked list! unlike contiguous memory in C/C++/Java, Haskell has poor data locality (worst case O(n) time)

What do the list functions (head, tail, take, drop) do?

head (returns the first element)

head [2, 3, 4, 5] —- returns 2

tail (returns all elements except head)

tail [2, 3, 4, 5] - - returns [3, 4. 5]

take (returns with the first n elements)

take 3 [2, 3, 4, 5] -- returns [2, 3, 4]

drop (returns the list after removing first n elements)

drop 3 [2, 3, 4, 5] -- returns [5]

what do the list functions length, : , ++ , and !! do?

length (returns number of element)

length [1, 2, 3, 4, 5] -- returns 5

: (adds a single element to the front)

3:[2,3] -- returns [3, 2, 3]

++ (join two lists CONCAT)

[1, 2, 3]++[4,5,6] -- returns [1, 2, 3, 4, 5, 6]

!! (gets the nth element (starting from 0). O(n) time)

[14, 7, 3] !! 1 -- returns 7

what does reverse, zip, unzip, zipWith, and sum do?

reverse (reverses order of list)

reverse [3, 2, 1] -- returns [1, 2, 3]

zip (takes pair of lists into list of pairs)

zip [1, 2, 3] [4, 5, 6] -- returns [(1, 4), (2, 5), (3, 6)]

unzip (undoes a zip)

no example needed hopefully

zipWith (does an operation between corresponding elements in a list)
zipWith (+) [1, 2, 3] [4, 5, 6] -- returns [4, 4, 4]

sum (sums elements of a list

sum [4, 5, 6] -- returns 15

can lists be used as parameters?

yes!!

isEmpty :: [a] -> Bool
isEmpty a = 
	case a of
	[] -> True
	_ -> False

What is the general form of a list comprehension? what part is the generator? what part is the predicate (condition that filters elements)

[ Expression involving a variable | var <- old list, condition, condition]

generator would be the var <- old list 
predicate would be the conditions

what is where?

creates local bindings. Ensure proper indentation for correct compilation

lstFactors n :: [x | x<- [1..n], isFactor x n]
	where
	isFactor x n = n `mod` x == 0

What is considered a “Higher Order Function”?

When it takes 1 (or more) functions as a parameter, and returns a function.

What is a Lambda Function?

A local function defined in brackets with form:
<arg-1> .. <arg-n> -> <expression>

example:
\x y -> x + y

the arrow separates parameters from the function body

can lambda functions include other functions inside it?

YES
y = filter (\x -> (mod) x 2 == 0) [1..10]

When using polymorphic functions, what do you need to ensure?

That the expression has a valid type

What is “Folding”?

It reduces a list to a single value by applying a function between values

foldr (with empty list, returns inital value). Takes 3 parameters, a function f, a value z, and a list xs.

foldr (+) [1..5] -- is (1 + (2 + (3 + (4))))

foldl (folds from left)
foldl (-) [1..5] -- is ((((1) - 2) - 3) - 4)

foldr1 (folds right, but errors when applied to an empty list)

foldr (+) [] -- throws error

map uses fold to compute its output!

What are the differences in type between foldr and foldr1?

foldr1 type:
foldr1 :: (a -> a -> a) -> [a] -> a

foldr type:

foldr :: (a -> b -> b) -> b -> [a] -> b

NOTE THE DIFFERENT TYPES a and b!!!! means accumulator and final result can be different type than list elements.

How do you change foldr1 to foldr?

add an additional argument to foldr1, and return that if empty. 

Recall that snoc appends an element to the end of a list

snoc x xs = [xs] ++ [x].
why does it put brackets around the x?

you can’t concatenate a list with an element!

how can foldr be used to sort a list? (specifically, insertion sort!)

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
	| x > y     = insert x ys
	| otherwise = x : y : ys
iSort :: [Int] -> [Int]
iSort xs = foldr insert [] xs

Recall that flip will flip the arguments. Does the following function myFlip represent a composite function?

myDouble :: Int -> Int -> Int
myDouble m n = 2*m*n

myFlip :: (a -> b -> c) -> (b -> a -> c)
myFlip f = \y x -> f x y

main = do
	print ((myFlip myDouble) 1 2)

No. the lambda function returns a different function, it doesn’t combine two functions. It is a higher order function.

what other word exists (in other programming languages) for fold?

reduce . Works like foldl1.

There exists list comprehension functions from Python (filter, map, reduce)

convert the following Python code into Haskell":

squared = [x * x for x in [1, 2, 3, 4, 5]

squared :: Int -> [Int] -> [Int]
squared a xs = map (\x -> x*x) xs

many other ways to solve it, this is just 1.