Quiz, Cheatsheet and more exercises

Quiz

What’s the type of this function? both p q x = p x && q x

a -> Bool -> a -> Bool -> a -> Bool
(a -> Bool) -> (a -> Bool) -> a -> Bool
(a -> Bool) -> (b -> Bool) -> c -> Bool

What’s the (most general) type of this function? applyInOut f g x = f (g (f x))

(a -> b) -> (b -> a) -> a -> b
(a -> b) -> (b -> c) -> a -> c
(a -> a) -> (a -> a) -> a -> a

Which one of the following functions adds its first argument to the second?

f x x = x + x
f x = \y -> x + y
f = \x y -> x + x

Which one of the following functions does not satisfy f 1 ==> 1?

f x = (\y -> y) x
f x = \y -> y
f x = (\y -> x) x

Which one of the following functions is correctly typed?

f x y = not x; f :: (Bool -> Bool) -> Bool
f x = x ++ "a"; f :: Char -> String
f x = 'a' : x; f :: String -> String

How many arguments does drop 2 take?

Zero
One
Two

What does this function do? f (_: x:_) = x

Returns the first element of a list
Returns an arbitrary element of a list
Returns all except the first and last elements of a list
Returns the second element of a list

What is the result of reverse $ take 5 . tail $ "This is a test"?

"i sih"
"set a"
A type error

If f :: a -> b, then what is the type of map (.f)?

[b -> c] -> [a -> c]
[c -> a] -> [c -> b]
(b -> c) -> [a -> c]
[a] -> [b]

What is the type of the leftmost id in id id?

unspecified
a
a -> a
(a -> a) -> (a -> a)

What is the type of const const?

unspecified
(c -> a -> b) -> a
c -> (a -> b -> a)
a -> b -> c -> a

Cheatsheet

Thanks again to our TA Daan Wichmann for the following cheatsheet


-- Higher order functions (functions in functions :o)

higherOrder :: (Int -> Int) -> Int
higherOrder f = f 1

doTwice :: (a -> a) -> a -> a
doTwice f x = f (f x)

-- Higer order functions on lists & Lambdas

addOne :: Int -> Int
addOne x = x + 1

mapped = map addOne [1, 2, 3] -- [2, 3, 4]
mappedLambda = map (\x -> x + 1) [1, 2, 3] -- (\x -> x + 1) is a lambda function

isEven :: Int -> Bool
isEven x = mod x 2 == 0

filtered = filter isEven [1, 2, 3] -- [2]
filteredLambda = filter (\x -> mod x 2 == 0) [1, 2, 3] -- (\x -> mod x 2 == 0) is a lambda function

-- Partial application
add :: Int -> Int -> Int
add x y = x + y

curried = add 3  -- Int -> Int

six = curried 2  -- 5

-- Infix to prefix

code = (+) 120 7  -- 127

zipped = zipWith (+) [0,2,5] [1,3,3]  -- [1,5,8]

-- Prefix to infix

even = 2 `mod` 2 == 0  -- True

-- $ and . operator

reversed = head (reverse "abcd")
reversedWithOperator = head $ reverse "abcd"  -- Same but using $ operator, if we are lazy / it looks better!

composition f g x = (f . g) x  -- This is the same as f (g x)

-- List comprehensions

double = [2*i | i<-[1,2,3]]
-- Output: [2,4,6]
-- Python equivalent: [i for i in range(1,8) if i % 2 == 0]

evens = [i | i <- [1..7], even i]
-- Output: [2,4,6]
-- Python equivalent: [i for i in range(1,8) if i % 2 == 0]

-- takeWhile & dropWhile

firstEvens = takeWhile even [2,4,1,2,3] -- Output: [2, 4]

lastOdds = dropWhile even [1,2,3] -- Output: [1, 2, 3]

containsTwo = elem 2 [1, 2, 7] -- Output: True

-- You can iterate over multiple lists

multipleLists = [ first ++ " " ++ last | first <- ["Bryan", "Emma"], last <- ["(Course Coordinator)","(Lecturer)"] ]
-- Output: ["Byan (Course Coordinator)","Bryan (Lecturer)","Emma (Course Coordinator)","Emma (Lecturer)"]

-- You can add local definitions

localDefs = [ reversed | word <- ["ammE","nayrB","iamaD","naaD", "allE", "aluaP", "zsuetaM"], let reversed = reverse word ]
-- Output: ["Emma", "Bryan", "Damai", "Daan", "Ella", "Paula", "Mateusz"]

-- You can also pattern match in list comprehensions (wowwwww)
patternMatch = [ char | (char:_) <- words "Concepts Of Programming Languages" ] -- Output: "COPL"

-- Custom operators :o

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

-- Remember typed holes when you get stuck with type errors when working on the exercises!
-- Try replacing a function or variable with a typed hole (_ after the =).
-- It might help you figure out what you need.

Exercises

All exercises can be found in Set3a and Set3b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 3b:

Exercise 3b.6

-- Ex 6: compute the partial sums of the given list like this:
--
--   sumsOf [a,b,c]  ==>  [a,a+b,a+b+c]
--   sumsOf [a,b]    ==>  [a,a+b]
--   sumsOf []       ==>  []
--
-- Use pattern matching and recursion (and the list constructors : and [])

sumsOf :: [Int] -> [Int]
sumsOf xs = todo

Exercise 3b.7

-- Ex 7: implement the function merge that merges two sorted lists of
-- Ints into a sorted list
--
-- Use only pattern matching and recursion (and the list constructors : and [])
--
-- Examples:
--   merge [1,3,5] [2,4,6] ==> [1,2,3,4,5,6]
--   merge [1,1,6] [1,2]   ==> [1,1,1,2,6]

merge :: [Int] -> [Int] -> [Int]
merge xs ys = todo

Exercise 3b.8

-- Ex 8: compute the biggest element, using a comparison function
-- passed as an argument.
--
-- That is, implement the function mymaximum that takes
--
-- * a function `bigger` :: a -> a -> Bool
-- * a value `initial` of type a
-- * a list `xs` of values of type a
--
-- and returns the biggest value it sees, considering both `initial`
-- and all element in `xs`.
--
-- Examples:
--   mymaximum (>) 3 [] ==> 3
--   mymaximum (>) 0 [1,3,2] ==> 3
--   mymaximum (>) 4 [1,3,2] ==> 4    -- initial value was biggest
--   mymaximum (<) 4 [1,3,2] ==> 1    -- note changed biggerThan
--   mymaximum (\(a,b) (c,d) -> b > d) ("",0) [("Banana",7),("Mouse",8)]
--     ==> ("Mouse",8)

mymaximum :: (a -> a -> Bool) -> a -> [a] -> a
mymaximum bigger initial xs = todo

Exercise 3b.9

-- Ex 9: define a version of map that takes a two-argument function
-- and two lists. Example:
--
--   map2 f [x,y,z,w] [a,b,c]  ==> [f x a, f y b, f z c]
--
-- If the lists have differing lengths, ignore the trailing elements
-- of the longer list.
--
-- Use recursion and pattern matching. Do not use any library functions.

map2 :: (a -> b -> c) -> [a] -> [b] -> [c]
map2 f as bs = todo

Exercise 3b.10

-- Ex 10: implement the function maybeMap, which works a bit like a
-- combined map & filter.
---
-- maybeMap is given a list ([a]) and a function of type a -> Maybe b.
-- This function is called for all values in the list. If the function
-- returns Just x, x will be in the result list. If the function
-- returns Nothing, no value gets added to the result list.
--
-- Examples:
--
-- let f x = if x>0 then Just (2*x) else Nothing
-- in maybeMap f [0,1,-1,4,-2,2]
--   ==> [2,8,4]
--
-- maybeMap Just [1,2,3]
--   ==> [1,2,3]
--
-- maybeMap (\x -> Nothing) [1,2,3]
--   ==> []

maybeMap :: (a -> Maybe b) -> [a] -> [b]

You have reached the end of this section!

You can check your current points from the blue blob in the bottom-right corner of the page.