Haskell 2

Cay S. Horstmann

Type Inference

• f1 x = x + 2

• Haskell interpreter gives type

  (Num a) => a -> a

  But we'll pretend for now it gives int -> int

• How does it know?
• Hindley-Milner Algorithm
• Start with the known knowns and the known unknowns

• 2 : int
  + : int -> int -> int
  x : u (unknown type)
  f1 : v (unknown type)

Parse Tree

Build Parse Tree

• Nodes for each @ (apply)
• Make type variable for each node
• Variables in the leaves
• Be sure to use the same type for the same item (e.g. x : u)
• Binary operators are curried:
  x + 2 is + x 2 = (+ x) 2 = Apply(Apply(+,x), 2)

  

• Remember that application is left associative

Get Equation Set

• From @ nodes

  v = u -> r
  s = int -> t
  int -> int -> int = u -> s

• left = right

  r = t

Simplify Equations

• int -> int -> int = u -> s

• -> is right associative

• int -> (int -> int) = u -> s

• int = u
  int -> int = s

• Now have more (and simpler) equations
• More opportunities for simplification

• s = int -> t, int -> int = s

• Keep goal in mind (v)

• v = u -> r = u -> t = int -> t = int -> int

• We are done: f1 has type int -> int

Function Types

• f2 g h = g(h(0))
• Parse tree
  

Equations

• u = v -> s
  s = w -> r
  v = q -> p
  w = int -> q
  r = p

You try it!

Hint: r = p tells you that you can use p instead of r.

Remember the goal (u). Keep plugging in until you can't simplify any more.

What do you get? Pay attention to parentheses.

Lists

• length (x:xs) = 1 + length(xs)

• Parse tree
  

Equations

• u = s -> r
  t = w -> s
  a -> [a] -> [a] = v -> t
  n = q -> p
  int -> int -> int = int -> n
  u = w -> q
  r = p
   . . .
  u = [a] -> int 

• Note that Haskell has no difficulty with recursive functions (unlike Scala)

Lab

1. Add this function to lab.hs and load it.

   f1 x = x + 2

   What type do you get? (Simplify Num a to int throughout in your answers.)

2. Add

   apply f x = f x

   What type do you get?

3. What do you expect to get as the result of

   apply f1 3

   Try it out to verify your expectation

4. Draw the parse tree for apply f x = f(x)
5. Read off the equations. What equations do you get?
6. Solve the equations. What is the type of apply?
7. Compare with Haskell. How do the answers differ?
8. Here we have used curried functions, just to be cool. Haskell has a pair type (a, b) (where a and b are any types). Try defining

   apply2(f,x) = f(x)

   What type does Haskell report?

9. Draw the parse tree. Here, the (f,x) needs to be described as an application of a curried function makepair f x. (makepair is similar to cons). makepair has type a -> b -> (a, b) (where a, b are type variables). That is, the left hand of the parse tree side is Apply(apply2, Apply(Apply(makepair, f), x)).
10. Read off the equations of the parse tree. (There will be 5 equations.) What are they?
11. Solve the equations. What is the type of apply2?
12. On to something more practical. Try this definition in Haskell:

    rev [] = []
    rev (x:xs) = rev xs

    What type do you get?

    There is an error in the function. It doesn't actually reverse a list. How can you tell that the function is wrong just by looking at the inferred type?