Notes - Functional Programming MT22, Misc

When are two functions equal?

When they provide the same outputs for all the same inputs.

If one definition of a function is strict, and the other is non-strict, are the two functions the same?

No.

Given a function merge that merges two lists in strictly increasing order into one list of their distinct elements in strictly increasing order, how could you define the Hamming ham numbers, defined as so:

The list is in strictly increasing order.
The list begins with the number one.
If the list contains $x$, then it contains $2x$, $3x$ and $5x$.

ham = merge (map (2*) ham) (merge (map (3*) ham) (map (5*) ham))

How are the foldr1 and foldl1 functions different from the normal fold functions?

They take no nil value and instead use the function applied to the first or last two elements of the list.

Guess the Haskell function:

mystery [1,2,3,4,5] = 1

head

Guess the Haskell function:

mystery [1,2,3,4,5] = [2,3,4,5]

tail

Guess the Haskell function:

mystery [1,2,3,4,5] = [1,2,3,4]

init

Guess the Haskell function:

mystery [1,2,3,4,5] = 5

last

Guess the Haskell function:

mystery 3 [1,2,3,4,5] = [4,5]
mystery 1 [1,2,3,4,5] = [2,3,4,5]

drop

Guess the Haskell function:

mystery 2 [1,2,3,4,5] = [1,2]
mystery 4 [1,2,3,4,5] = [1,2,3,4]

take

What’s the Haskell type signature for foldr?

\[\text{foldr $\colon\colon$ (a -> b -> b) -> b -> [a] -> b}\]

What’s the Haskell type signature for foldl?

\[\text{foldl $\colon\colon$ (b -> a -> b) -> b -> [a] -> b}\]

What’s important to remember about the type signatures of foldr vs foldl?

The function is (a -> b -> b) for foldr and (b -> a -> b) for foldl, i.e. the nil value goes on the same side as the fold type.

What’s the Haskell type signature for scanl, defined as:

scanl f e = map (foldl f e) . inits

\[\text{scanl $\colon\colon$ (b -> a -> b) -> b -> [a] -> [b]}\]

Can you “expand”

foldr f nil [a, b, c, d]

?

f a (f b (f c (f d nil)))

Can you “expand”

foldl f nil [a, b, c, d]

?

f (f (f (f nil a) b) c) d

Can you give a definition for foldr on lists, in terms of nil and cons?

foldr cons nil [] = nil
foldr cons nil (x:xs) = cons x (foldr cons nil xs)

Can you give a definition for foldl on lists, in terms of nil and cons?

foldl cons nil [] = nil
foldl cons nil (x:xs) = foldl cons (cons nil x) xs

When proving something about partial lists in Haskell, what should you put before every proof?

“The proof is between two Haskell expressions, which are chain-complete.”

Can you define unfold without using Maybe?

unfold ;; (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
unfold null head tail = u
	where u x = if null x then [] else head x : u (tail xan)

Can you define unfold using Maybe?

unfold ;; (a -> Maybe (b, a)) -> a -> [b]
unfold uncons x = case uncons x of
	Nothing -> []
	Just (b, a) -> b : unfold uncons a

When defining unfold without Maybe, what would the type be?

unfold ;; (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]

When defining unfold with Maybe, what would the type be?

unfold ;; (b -> Maybe (a, b)) -> b -> [a]

What might the unfold for trees defined by

data Tree a = (Tree a) `Fork` (Tree a) | Leaf a

look like?

unfoldT ;; (b -> Bool) -> (b -> a) -> (b -> b) -> (b -> b) -> b -> Tree a
unfoldT base nil left right xs
  | base xs = Leaf (nil xs)
  | otherwise = Fork
    (unfoldT base nil left right (left xs))
    (unfoldT base nil left right (right xs))

I want to convert a function that takes two arguments into a function that takes a tuple. What function should I use?

uncurry

I want to convert a function that takes a tuple into a function that takes two arguments. What function should I use?

curry

Say you have a new data type Beans in Haskell and you want to make it a member of the Eq typeclass. How can you do this?

instance Eq Beans where
	eq b1 b2 = -- ...

Say you want to create a new type class for things that are reversable in Haskell. How can you do this?

class Reversable a where
	rev ;; a -> a

When making sure a new data type (e.g. Beans) in Haskell implements Ord, what function do you need to define so that this is true?

instance Ord Beans where
	(<=) b1 b2 = -- ...

Notes - Functional Programming MT22, Misc

Flashcards

Related posts