Skip to content

Latest commit

 

History

History
787 lines (574 loc) · 18.6 KB

exercises.md

File metadata and controls

787 lines (574 loc) · 18.6 KB
Raw

Solutions to problems of chapter 5

Type Matching

Below you'll find a list of several standard functions we've talked about previously. Under that is a list of their type signatures. Mathch the function to its type signature.

  1. Functions:
    a. not
    b. length
    c. concat
    d. head
    e. (<)
  2. Type signatures:
    a. _ :: [a] -> a
    b. _ :: [[a]] -> [a]
    c. _ :: Bool -> Bool
    d. _ :: [a] -> Int
    e. _ :: Ord a => a -> a -> Bool

Answers: (a, c), (b, d), (c, b), (d, a), (e, e)

Manual currying and un-currying

Load curry_uncurry_anon.hs into GHCi and check that all the functions return the same result given equal input.

Prelude> curriedFunction 10 True
815
Prelude> curriedFunction 20 False
31357
Prelude> uncurriedFunction (10, True)
815
Prelude> uncurriedFunction (20, False)
3157
Prelude> anonymous 10 True
815
Prelude> anonymous 20 False
3157
Prelude> anonNested 10 True
815
Prelude> anonNested 20 False
3157

Type Arguments

Given a function and its type, tell us what type results from applying some or all of the arguments.

You can check your work in the REPL:

Prelude> let f :: a -> a -> a -> a; f = undefined
Prelude> let x :: Char; x = undefined
Prelude> :t f x

It turns out that you can check the types of things that aren't implemented yet, so long as you give GHCi an undefined to bind the signature to.

  1. If the type of f is a -> a -> a -> a, and the type of x is Char then the type of f x is:
    a. Char -> Char -> Char
    b. x -> x -> x -> x
    c. a -> a -> a
    d. a -> a -> a -> Char
    Answer: a

  2. If the type of g is a -> b -> c -> b, then the type of g is a -> b -> c -> b, then the type of g 0 'c' "woot" is:
    a. String
    b. Char -> String
    c. Int
    d. Char
    Answer: d

  3. If the type of h is (Num a, Num b) => a -> b -> b, then the type of h 1.0 2 is:
    a. Double
    b. Integer
    c. Integral b => b
    d. Num b => b
    Answer: d

Note that because the type variables a and b are different, the compiler must assume that the types could be different.

  1. If the type of h is (Num a, Num b) => a -> b -> b, then the type of h 1 (5.5 :: Double) is:
    a. Integer
    b. Fractional b => b
    c. Double
    d. Num b => b
    Answer: c

  2. If the type of jackal is (Ord a, Eq b) => a -> b -> a, then the type of jackal "keyboard" "has the word jackal in it" is:
    a. [Char]
    b. Eq b => b
    c. b -> [Char]
    d. b
    e. Eq b => b -> [Char]
    Answer: a

  3. If the type of jackal is (Ord a, Eq b) => a -> b -> a then the type of jackal "keyboard" is:
    a. b
    b. Eq b => b
    c. [Char]
    d. b -> [Char]
    e. Eq b => b -> [Char]
    Answer: e

  4. If the type of kessel is (Ord a, Num b) => a -> b -> a then the type of kessel 1 2 is:
    a. Integer
    b. Int
    c. a
    d. (Num a, Ord a) => a
    e. Ord a => a
    f. Num a => a
    Answer: d

  5. If the type of kessel is (Ord a, Num b) => a -> b -> a, then the type of kessel 1 (2 :: Integer) is:
    a. (Num a, Ord a) => a
    b. Int
    c. a
    d. Num a => a
    e. Ord a => a
    f. Integer
    Answer: a

  6. If the type of kessel is (Ord a, Num b) => a -> b -> a, then the type of kessel (1 :: Integer) 2 is:
    a. Num a => a
    b. Ord a => a
    c. Integer
    d. (Num a, Ord a) => a
    e. a
    Answer: c

Parametricity

All you can do with a parametrically polymorphic value is pass or not pass it to some other expression. Prove that to yourself with these small demonstrations.

  1. Given the type a -> a, which is the type for id, attempt to make a function that terminates successfully that does something other than returning the same value. This is impossible, but you should try it anyway.
  2. We can get a more comfortable appreciate of parametricity by looking at a -> a -> a. This hypothetical function a -> a -> a has two-and only two-implementations. Write both possible versions of a -> a -> a. After doing so, try to violate the constraints of parametrically polymorphic values we outlined above.

Answer:

f :: a -> a -> a
f x y = x
-- or
f x y = y
  1. Implement a -> b -> b. How many implementations can it have? Does the behavior change when the types of a and b change?

Answer:

f :: a -> b -> a
f x y = y

This is the only possible implementation. The behavior does not change when the types of a and/or b change.

Apply Yourself

Look at these pairs of functions. One function is unapplied, so the compiler will infer maximally polymorphic type. The second function has been applied to a value, so the inferred type signature may have become concrete, or at least less polymorphic. Figure out how the type would change and why, make a note of what you think the new inferred type would be and then check your work in GHCi.

-- Type signature of general function
(++) :: [a] -> [a] -> [a]

-- How might that change when we apply
-- it to the following value?
myConcat x = x ++ " yo"

Answer: (++) :: [Char] -> [Char] -> [Char]

-- General function
(*) :: Num a => a -> a -> a

-- Applied to a value
myMult x = (x / 3) * 5

Answer: (*) :: Fractional a => a -> a -> a

take :: Int -> [a] -> [a]

myTake x = take x "hey you"

Answer: take :: Int -> [Char] -> [Char]

(>) :: Ord a => a -> a -> Bool

myCom x = x > (length [1..10])

Answer: `(>) :: Int -> Int -> Bool

(<) :: Ord a => a -> a -> Bool

myAlph x = x < 'z'

Answer: (<) :: Char -> Char -> Bool

Chapter Exercises

Multiple choice

  1. A value of type [a] is:
  • a. a list of alphabetic characters
  • b. a list of lists
  • c. a list whose elements are all of some type a
  • d. a list whose elements are all of different types

Note: [a] could also be of the types described in a and b but it does not have to be. In other words, the types described in a and b are subsets of c. c is the most polymorphic permissable type that still respects the constraints of [a].

  1. A function of type [[a]] -> [a] could:
  • a. take a list of strings as an argument
  • b. transform a character into a string
  • c. transform a string into a list of strings
  • d. take two arguments
  1. A function of type [a] -> Int -> a:
  • a. takes one argument
  • b. returns one element of type a from a list
  • c. must return an Int value
  • d. is completely fictional
  1. A function of type (a, b) -> a:
  • a. takes a list argument and returns a Char value
  • b. has zero arguments
  • c. takes a tuple argument and returns the first value
  • d. requires that a and b be of different types

Determine the type

For the following functions, determine the type of the specified value. We suggest you type them into a file and load the contents of the file in GHCi. In all likelihood, it initially will not have the polymorphic types you might expect due to the monomorphism restriction. That means that top-level declarations by default will have a concrete type if any can be determined. You can fix this by setting up your file like so:

{-# LANGUAGE NoMonomorphismRestriction #-}

module DetermineTheType where

-- simple example
example = 1

If you had not included the NoMonomorphismRestriction extension, example would have had the type Integer instead of Num a => a. Do your best to determine the most polymorphic type an expression could have in the following exercises.

  1. All function applications return a value. Determin the value returned by these function applications and the type of that value.
    a. (* 9) 6
    Answer: value: 36, type: Num a => a
    b. head [(0, "doge"), (1, "kitteh")]
    Answer: value: (0, "doge"), type: Num a => (a, [Char])
    c. head [(0 :: Integer, "doge"), (1, "kitteh")]
    Answer: value: (0, "doge"), type: (Integer, [Char])
    d. if False then True else False
    Answer: value: False, type: Bool
    e. length [1, 2, 3, 4, 5]
    Answer: value: 5, type: Int
    f. (length [1, 2, 3, 4]) > (length "TACOCAT")
    Answer: value: False, type: Bool

  2. Given:

x = 5
y = x + 5
w = y * 10

What is the type of w?
Answer: Num a => a

  1. Given:
x = 5
y = x + 5
z y = y * 10

What is the type of z?
Answer: z :: Num a => a -> a

  1. Given:
x = 5
y = x + 5
f = 4 / y

What is the type of f?
Answer: f :: Fractional a => a

  1. Given:
x = "Julie"
y = " <3"
z = "Haskell"
f = x ++ y ++ z

What is the type of f?
Answer: f :: [Char]

Does it compile?

For each set of expressions, figure out which expression, if any, causes the compiler to squawk at you (n.b. we do not mean literal squawking) and why. Fix it if you can.

bigNum = (^) 5 $ 10
wahoo = bigNum $ 10


Answer: The second line wahoo = bigNum $ 10 throws an error. It is not clear what operation we intend to do with the two numbers.

x = print
y = print "woohoo!"
z = x "hello world"


Answer: None of the lines is syntactically incorrect.

a = (+)
b = 5
c = b 10
d = c 200


Answer: Lines 3 and 4 are problematic because 2 numbers are introduced without any operator or function. We can rewrite the code as follows:

a = (+)
b = 5
c = a b 10 -- c evaluates to (+) b 10 = 5 + 10
d = a c 200 -- d evaluates to (+) c 200 = (5 + 10) + 200
a = 12 + b
b = 10000 * c


Answer: c is not in scope. Adding it will solve the problem. Keep in mind that for it to run in GHCi, you need to arrange the order such that every introduced variable is defined previously.

a = 12 + b
b = 10000 * c
c = 1

Type variable or specific type constructor?

You will be shown a type declaration, and you should categorize each type. The choices are a fully polymorphic type variable, constrained polymorphic type variable, or concrete type constructor.

f :: Num a => a -> b -> Int -> Int
--           [0]  [1]   [2]    [3]
  • ([0]), constrained polymorphic Num
  • ([1]), fully polymorphic
  • ([2],[3]), concrete type constructor
f :: zed -> Zed -> Blah
--   [0]    [1]    [2]
  • ([0]), fully polymorphic
  • ([1], [2]), concrete type constructor
f :: Enum b => a -> b -> C
--            [0]  [1]  [2]
  • ([0]), fully polymorphic
  • ([1]), constrained polymorphic Enum
  • ([2]), concrete type constructor
f :: f -> g -> C
--  [0]  [1]  [2]
  • ([0], [1]), fully polymorphic
  • ([2]), concrete type constructor

Write a type signature

For the following expressions, please add a type signature. You should be able to rely on GHCi type inference to check your work, although you might not have precisely the same answer as GHCi gives (due to polymorphism, etc).

  1. While we haven't fully explained this syntax yet, you've seen it in Chapter 2 and as a solution to an exercise in Chapter 4. This syntax is a way of destructuring a single element of a list by pattern matching.
functionH ::
functionH (x:_) = x

Answer:

functionH :: [a] -> a
functionH (x:_) = x
functionC ::
functionC x y = if (x > y) then True else False

Answer:

functionC :: (Ord a) => a -> a -> Bool
functionS ::
functionS (x, y) = y

Answer:

functionS :: (a, b) -> b
functionS (x, y) = y

Given a type, write the function

You will be shown a type and a function that needs to be written. Use the information the type provides to determine what the function should do. We'll also tell you how many ways there are to write a function. Syntactically different but semantically equivalent implementations are not counted as being different. For example, writing a function one way then rewriting the semantically identical function but using anonymous lambda syntax does not count as two implementations.

To make things a little easier, we'll demonstrate how to solve this kind of exercise. Given:

muFunc :: (x -> y)
       -> (y -> z)
       -> c
       -> (a, x)
       -> (a, z)
myFunc xToY yToZ _ (a, x) = undefined

Talking through the above, we have a function that takes four arguments. The final result is a tuple with the type (a, z). It turns out, the c argument is nowhere in our results and there's nothing to do with it, so we use the underscore to ignore that. We named the two function arguments by their types and pattern matched on the tuple argument. The only way to get the second value of the tuple from teh type x to the type z is to use both of the functions furnished to us. If we tried the following:

myFunc xToY yToZ _ (a, x) =
   (a, (xToY x))

We would get a type error that it expected the type z but the actual type was y. That's because we're on the right path, but not quite done yet! Accordingly, the following should typecheck:

myFunc :: (x -> y)
       -> (y -> z)
       -> c
       -> (a, x)
       -> (a, z)
myFunc xToY yToZ _ (a, x) =
   (a, (yToZ (xToY x)))
  1. There is only one function definition that typechecks and doesn't go into an infinite loop when you run it.
i :: a -> a
i = undefined

Answer:

i :: a -> a
i x = x
  1. There is only one version that works.
c :: a -> b -> a
c = undefined

Answer:

c :: a -> b -> a
c x y = x
  1. Given alpha equivalence are c'' and c (see above) the same thing?
c'' :: b -> a -> b
c'' = undefined

Answer: Yes they are alpha equivalent.

c'' :: b -> a -> b
c'' x y = x
  1. There is only one version that works. 
    c' :: a -> b -> b
c' = undefined

Answer:

c' :: a -> b -> b
c' x y = y
  1. There are multiple possibilities, at least two of which you've seen in previous chapters. 
    r :: [a] -> [a]
r = undefined

Answer: Here are a few possible solutions

r :: [a] -> [a]
r x = tail x
-- or
r x = x ++ x
-- or
r x = concat [x, x] -- can add as many xs you like
-- or
r x = reverse x
  1. There is only one version that will typecheck.
co :: (b -> c) -> (a -> b) -> a -> c
co = undefined

Answer:

co :: (b -> c) -> (a -> b) -> a -> c
co bToC aToB a = bToC $ aToB a
  1. One version will typecheck.
a :: (a -> c) -> a -> a
a = undefined

Answer:

a :: (a -> c) -> a -> a
a _ x = x
  1. One version will typecheck.
a' :: (a -> b) -> a -> b
a' = undefined

Answer:

a' :: (a -> b) -> a -> b
a' aToB a = aToB a

Fix it

Won't someone take pity on this poor broken code and fix it up? Be sure to check carefully for things like capitalization, parentheses, and indentation.

module sing where

fstString :: [Char] ++ [Char]
fstString x = x ++ " in the rain"

sndString :: [Char] -> Char
sndString x = x ++ " over the rainbow"

sing = if (x > y) then fstString x or sndString y
where x = "Singin"
      x = "Somewhere"

Answer: Solution file: ./exercise.files/sing.hs

  1. Now that it's fixed, make a minor change and make it sing the other song. If you're lucky, you'll end up with both songs stuck in your head!

Answer: Solution file: ./exercise.files/sing.hs

module Arith3Broken where

main :: IO ()
Main = do
   print 1 + 2
   putStrLn 10
   print (negate -1)
   print ((+) 0 blah)
   where blah = negate 1

Answer: Solution file: ./exercise.files/arith3broken_fixed.hs

Type-Kwon-Do

The name is courtesy of Phillip Wright. Thank you for the idea!

The focus here is on manipulating terms in order to get the types to fit. This sort of exercise is something you’ll encounter in writing real Haskell code, so the practice will make it easier to deal with when you get there. Practicing this will make you better at writing ordinary code as well. We provide the types and bottomed out (declared as undefined) terms. Bottom and undefined will be explained in more detail later. The contents of the terms are irrelevant here. You’ll use only the declarations provided and what the Prelude provides by default unless otherwise specified. Your goal is to make the ???’d declaration pass the typechecker by modifying it alone. Here’s a worked example for how we present these exercises and how you are expected to solve them. Given the following:

data Woot
data Blah

f :: Woot -> Blah
f = undefined

g :: (Blah, Woot) -> (Blah, Blah)
g = ???

Here it’s g that you’re supposed to implement; however, you can’t evaluate anything. You’re to only use type-checking and type-inference to validate your answers. Also note that we’re using a trick for defining datatypes which can be named in a type signature, but have no values. Here’s an example of a valid solution:

g :: (Blah, Woot) -> (Blah, Blah)
g (b, w) = (b, f w)

The idea is to only fill in what we've marked with ???.

Not all terms will always be used in the intended solution for a problem.

f :: Int -> String
f = undefined

g :: String -> Char
g = undefined

h :: Int -> Char
h = ???

Answer:

h :: Int -> Char
h i = g f i
data A
data B
data C

q :: A -> B
q = undefined

w :: B -> C
w = undefined

e :: A -> C
e = ???

Answer:

e :: A -> C
e a = w q a
-- we could also write 'e a = w $ q a' which would make it more readable
-- but syntax-wise the first solution is also correct
-- this is also valid for the previous problem
data X
data Y
data Z

xz :: X -> Z
xz = undefined

yz :: Y -> Z
yz = undefined

xform :: (X, Y) -> (Z, Z)
xform = ???

Answer:

xform :: (X, Y) -> (Z, Z)
xform x y = (xz x, yz y)
-- we could also write 'xform x y = (yz y, xz x)'
-- this may evaluate to something else depending on implementation
-- but type-wise it is correct
munge :: (x -> y)
      -> (y -> (w, z))
      -> x
      -> w
munge = ???

Answer:

munge :: (x -> y)
      -> (y -> (w, z))
      -> x
      -> w
munge xToY yToWZTuple x = fst $ yToWZTuple $ xToY x