Types
Haskell, Iteration 8

Haskell is famous for two reasons:

• It's a pure functional programming language (i.e., no assignment statement)
• It uses strong, inferred, static, classed, parameterized typing.

We'll focus on types in this iteration.

Too... Many... Adjectives!

What do all these adjectives mean in the context of a language's type system?

Let's first see some types from GHCi. Running from the factorial folder:

ghci> :load Factorial
ghci> import Complex
ghci> pi
3.141592653589793
ghci> :type pi
pi :: (Floating a) => a
ghci> :type take
take :: Int -> [a] -> [a]
ghci> :type factorial
factorial :: (Num t) => t -> t
ghci> :type (:+)
(:+) :: (RealFloat a) => a -> a -> Complex a

Strong, Static Typing

"Static" is the easiest adjective to define: Haskell does its type checking at compile time. When you load or import a module, GHCi compiles it, and not only does it know the types of the names in scope, it can tell you what those types are!

Static typing usually implies strong typing (although the reverse is not valid).

A strongly typed language will not allow you to violate the types on its names.

ghci> pi + 3
ghci> pi + 98.6
ghci> pi + "foo"

Haskell rejects the last expression because "foo" is not of type Floating a (whatever that is!).

Similarly, take requires an Int and an array:

ghci> take 2 [1, 2, 3]
ghci> take 2.0 [1, 2, 3]
ghci> take 2 3.14159

Inferred Typing

Did you ever tell Haskell what the type signature of factorial is? And yet it knows! You return 1 in the base case. You use * and - on the result and argument, respectively. So it stands to reason that factorial takes a number and returns a number.

Occasionally you have to help Haskell along with a few type signatures on functions, but you never have to explicitly type everything.

Classed and Parameterized

What about the Floating a and Num t in the type signatures? Floating and Num are type classes. Let's consider your factorial function.

Its inferred type is (Num t) => t -> t. You could have hamstrung yourself and declared the type explicitly like so:

factorial :: Int -> Int

This would tell GHC that you wanted to use the machine's natural implementation of an integer (int in Java or C++). If you add this in the Factorial module, GHC is happy to compile it, and you end up with a factorial function that can't compute anything larger than 16!! (That's one '!' for the factorial and another '!' for the indignity of it all.) You might as well use C then.

Int is a concrete type in Haskell. Integer is as well, although it transitions seamlessly into using bigints when necessary. So you could declared factorial's type like this:

factorial :: Integer -> Integer

Now you can compute arbitrarily large factorials. However, this still isn't the type that Haskell originally inferred. So what's the power of (Num t) => t -> t?

The key here is that you're using * and - on the argument and the returned result. Due to the way you're using them, the argument's type must be the same as the type of the returned result. Instead of using concrete types, you can use parameterized types: t -> t.

However, this is not enough to strongly capture the types that factorial needs. Because you're using * and - the types bound to t must implement these functions. The type class Num ensures this.

So while Integer -> Integer would let you compute arbitrarily large integer factorials, it wouldn't let you do these computations:

ghci> :type 5.0 :+ 0.0
5.0 :+ 0.0 :: (RealFloat t) => Complex t

ghci> factorial 5.0
ghci> factorial (5.0 :+ 0.0)

Did you have any idea that your factorial function would work on complex numbers?

Things to Do

Write tests for each function.

Use high-level functions, not explicit recursion. (Write the recursion first if that helps, but then turn it into maps and folds and the like.)

Give an explicit type declaration for each function in the Palindrome module. Make them as general as you can.

For Exercise 3, a function mean is horribly out of place in a module named Palindrome. Let's just keep that our little secret.

I think Exercise 5 is easier than Exercise 4.

For some extra credit, create a second "make palindrome" function (as in Exercise 4), but return the smallest one possible. For example,

ghci> minimalPalindrome [1, 2, 3]
[1, 2, 3, 2, 1]
ghci> minimalPalindrome [1, 2, 1]
[1, 2, 1]
ghci> minimalPalindrome [1, 2, 3, 2]
[1, 2, 3, 2, 1]