Higher Order Functions

Question 1

what does map do?

Answer 1

applies a function to every element in a list.

map (+1) [ 1, 3, 5, 7]
[2, 4, 6, 8]

Question 2

what does filter do?

Answer 2

selects every element in a list that satisfies a predicate

filter :: (a -> Bool) -> [a] -> [a]

filter even [1..10]
[2, 4, 6, 8, 10]

Question 3

what is the pattern of recursion?

Answer 3

f[] = v

f(x : xs) = x ⊕ f xs

Question 4

give a recursive definition of sum and its foldr version

Answer 4

recursive:
sum[] = 0
sum(x : xs) = x + sum xs

foldr:
sum = foldr (+) 0

Question 5

give a recursive definition of and and its foldr version

Answer 5

recursive:
and[] = True
and (x : xs) = x && and xs

foldr:
and = foldr (&&) True

Question 6

give the foldr definition of length

Answer 6

length = foldr (_ n -> 1 + n) 0

Question 7

describe the difference between intesionality and extensionality in a sentence

Answer 7

\x.(1+x) is intensionally different from \x.(x+1) but extensionally equal

Question 8

what does . do?

Answer 8

returns the composition of 2 funstions as a single function

.) :: (b -> c) -> (a -> b) -> (a -> c
f.g = \x -> f(g x)

Question 9

use . to define odd

Answer 9

odd :: Int -> Bool

odd = not.even

Question 10

what does all do?

Answer 10

check whether every element satisfies a predicate

all even [2, 4, 6]
True

Question 11

what does any do?

Answer 11

check whether any element satisfies a predicate

any isSpace “ab c”
True

Question 12

what does takeWhile do?

Answer 12

selects elements while the predicate holds all elements

takeWhile isAlpha “ab cd”
“ab”

Question 13

what does dropWhile do?

Answer 13

teh opposite of takeWhile
dropWhile is Alpha “ab cd”
“ cd”

Question 14

express [fx | x

Answer 14

map f( filter p xs)

Question 15

what is ad-hoc polymorphism?

Answer 15

overloading

Question 16

What are the 2 types of type declaration?

Answer 16

abbreviation type and new type

Question 17

What is an abbreviation type?

Answer 17

an existing type with a new name.

Question 18

declare a new type Bool that can be shown and compared

Answer 18

data Bool = False | True

deriving (Show, Eq)

Question 19

give an example of a new type where the constructors have parameters

Answer 19

data Shape = Circle Float

| Rect Float Float

Question 20

define a new inductive type for natural numbers

Answer 20

data nat = Zero | Succ Nat

where
Zero :: Nat
Succ :: Nat -> Nat
Succ = +1

Question 21

define a binary tree type

Answer 21

data Tree = Leaf Int

| Node Tree Int Tree

Question 22

write a function that determines whether in Int occurs in a tree

Answer 22

occurs :: Int -> Tree -> Bool
occurs m (leaf n) = m == n
occurs m (Node l n r )  = m == n || occurs m l || occurs m r

Question 23

what does flatten do?

Answer 23

returns all of the Ints in a tree

Question 24

write a definition of flatten

Answer 24

flatten :: tree -> [Int]
flatten (Leaf n) = [n]
flatten (Node l n r) = flatten l ++ [n] ++ flatten r