Home
Course page
Module descriptor
Exercises

Questions

Question I
Question II
Question III
Question IV

F28PL Study Class

For basic drill, work your way through

• tutorial 6 and
• tutorial 7.
  If and when you get stuck, you can
  - ask a labhelper for help, or
  - look up the slides, or
  - check out this webpage and this webpage, which I just discovered while writing this page, and they are great.

Now for more interesting questions. Don’t worry if you can’t do these … but try:

(If you spot errors, e-mail me and I’ll fix it.)

I. Some stuff on functions

1. Write the type of fn x => fn y => x andalso y.
   (Answer)
   bool -> bool -> bool
   Make sure you understand why.
2. In ML, andalso and orelse need not evaluate their second argument. When, and why?
   (Answer)
   exp1 andalso exp2 will not evaluate exp2 if exp1 evaluates to false, for implementational efficiency because the overall result of the computation will not depend on the result of evaluating exp2 (see Short-circuit evaluation).
   What’s the corresponding property of orelse?
3. What’s the type of fn x => 42? Describe this type in words.
   (Answer)
   'a -> int
   In words: “$\alpha$ to int”, or more sexily: a parametric polymorphic function to integers.
4. (Hard) What do you think the implementational difference might be between fn x => 42 and fn _ => 42?
   (Answer)
   fn x => 42 evaluates its argument, then ignores the result and returns 42.
   fn _ => 42 ignores its argument and returns 42.
5. Write a deliberately implementationally inefficient function called myand in ML of type bool -> bool -> bool that implements logical $and$, and always evaluates both arguments. Use the fun construct to name it—-I showed you this in class, or see page 7 of Lecture 12, or see this page.
   (Answer)
   fun myand true true = true | myand true false = false | ...
6. Write your own implementation myandalso of andalso, complete with implementational efficiency.
   (Hint)
   A good start might be fun myandalso false _ =>.

II. Higher-order functions

1. Recall question I.1 above. Now write the type of fn y => fn x => y x. Why the difference?
   (Answer)
   ('a -> 'b) -> 'a -> 'b. Function application y x is polymorphic, whereas x andalso y requires x and y to have type bool thus imposing constraints on the overall type.
2. What’s the difference between the types 'a -> 'b -> 'c and 'a * 'b -> 'c?
   (Answer)
   The type 'a -> 'b -> 'c is inhabited by programs that input an argument of type 'a and return a value of type 'b -> 'c.
   'a * 'b is inhabited by programs that input an argument of type 'a * 'b and return an argument of type 'c.
3. (Hard) Write a program of type ('a -> 'b -> 'c) -> ('b -> 'a -> 'c).
   (Answer)
   fn f => fn y => fn x => f x y.
4. (Harder) Write programs of type ('a -> 'b -> 'c) -> ('a * 'b) -> 'c and ('a * 'b -> 'c) -> ('a -> 'b -> 'c).
   (Answer)
   I’m looking for this:
   - fn f => fn (x,y) => (f x y) and
   - fn f => fn x => fn y => f (x,y).
   It’s simple, provided you understand what the types are.
5. (Even harder) Write your own implementation mycompose of functional composition. This should have type ('a -> 'b) -> ('b -> 'c) -> ('a -> 'c) and should input $f$ and $g$ and output $g \circ f$ the function which inputs $x$ and outputs $g(f(x))$.
   (Answer)
   fun mycompose f g x = g(f(x)). If you can’t kick yourself yourself, get your neighbour to kick you for you. In nameless notation: fn f => fn g => fn x => g(f(x))
6. (Bloody hard) Write a program of type int -> ('a -> 'a) -> ('a -> 'a) which inputs an integer $n$ and a function $f$ and returns $f^n$ (the composition of $f$ with itself $n$ times). You’ll need to use recursion (see below).

III. Strings, numbers, and recursion

1. (Trick question) Write a program to output World Peace. What’s its type?
   (Answer)
   "World Peace":string. Sorry; couldn’t resist.
2. Write a program to input two strings x and y and output their concatenation x^y. What’s its type?
   (Answer)
   fn x => fn y => x^y : string -> string -> string
3. (Highly examinable) Write a program myfact that inputs $x$ and outputs $x$ factorial, which is $x!=x(x{-}1)(x{-}2)\dots 1$. We do not care what happens if $x$ is negative. What is the type of myfact?
   (Answer)
   fun myfact 0 = 0 | myfact 1 = 1 | myfact x = x*(myfact (x-1))
   myfact:int → int
   
4. (Highly examinable) Find the Fibonacci function and Ackermann’s function online and write them in ML.

IV. Discussion questions

1. Discuss two advantages of using ML over using Java and give two concrete examples which illustrate those advantages in a “real-life” scenario.
2. Discuss two advantages of using Java over using ML and give two concrete examples which illustrate those advantages in a “real-life” scenario.
   (Answer)
   The usual obvious things: it’s easier to find a Java programmer than an ML programmer. Better industry and library support. Possibly faster.
   However (skipping to partially answer the previous question) the ML program will be smaller and more maintainable than its Java equivalent so you get more productivity out of your programmer per man-hour—-possibly a factor of ten or more, if they’re good. It’s by no means clear that Java is “better” in any reliable sense than a modern functional language such as OCaml, Haskell, or Erlang.
   Check out a company like Jane Street (see “The OCaml difference”).
   
3. Give one concrete example where using assembly code would be more appropriate than using either ML or Java.
   (Answer)
   An embedded control chip with limited (e.g. 1k) of memory. Or a boot sector (that’s the first tiny fragment of code on a hard drive).
   But, as always in such questions, there are arguments for and against: check out Embedded C and somebody who wrote a boot sector in C.
4. (Possibly hard) I promise to give you an ML program which will input a Java program and tell you whether it outputs “Hello world”. Explain why I’m lying.
5. The Met office has just invested in a new supercomputer to model the weather. Give one good reason why it might be programmed in ML, and one good reason why we might prefer to use C.
   (Answer)
   C will probably run faster on a per-thread basis, but ML will be much easier to parallelise to many threads (and modelling the weather is a highly parallel task). In practice they’ll probably use a special-purpose language that combines a language like C with powerful parallelism constructs.

Conclusion

If you’ve worked your way through all these questions in two hours then you’re probably not human. To fill time so you’re not found out, read this great essay on beating the averages by Paul Graham, who made a mint out of functional programming and went on to found Y Combinator.