Haskell is a statically typed functional programming language. This means that the type of every value is known at compile time. Additionally Haskell is type safe meaning that values at runtime always do indeed have the type that was decided at compile time.
A type describes a set of values. In Haskell these values are described with a fairly expressive language that includes variables (in the mathematical sense), functions, and quantification. Types have names that start with an uppercase letter while type variables start with lowercase. For example the type that includes all values can be written as:
type AnyValue = forall a. a
This means that we are declaring a new name AnyValue for the type that is made up of the values for all types. The forall quantification is usually implicit in Haskell types:
type AnyValue = a -- This is equivalent
Functions are described by the (->) type operator which can be read as "maps to":
type SomeFunction = a -> a
This is the type of all functions that take values of some type 'a' and map to values with the same type.
We can also describe type functions, that is instead of quantifying over all types of a variable we can make the variable a parameter to the type:
type Function a b = a -> b
We can pick an a and b by applying the type constructor Function to some types:
type FunctionOfInt = Function Int Int
Some primitive types in Haskell include basic numeric types: Integer, Rational, and Double. Some other standard data types: Char, String, Maybe a (Either a value of type a or nothing), [a] (list of a's), (a,b) (a pair of values), Either a b (Union which either has a value of a or a value of b).
We can connect the world of types with the world of values using the type declaration operator ::. On the left-hand side we give a value (or the name of a value) and on the right-hand side we give a type. If a type declaration is not made the most general type will be inferred. Some examples:
-- Function declaration
square :: Double -> Double
square x = x * x
hypotenuse :: Double -> Double -> Double
hypotenuse x y = sqrt (square x + square y)
Like at the type level, functions are defined by giving a name on the left-hand side and an expression on the right-hand side. Function application is done by simply putting an argument after a function. Notice that this mirrors the syntax of the function declaration where on the left-hand side the name of the function appears followed by its arguments.
But there is even more going on. The left-hand side of the = in Haskell is a pattern match. The parameters to a function can be bindings that go deep inside the structure of a value. You can think of a function declaration as a template and when an application happens it matches with the appropriate template and is replaced by code on the right hand side. Note that we will clearly need to be allowed to declare several patterns for any given function. Some examples:
f :: Either String Int -> String
f (Left x) = x -- We know 'x' is a String
f (Right y) = "A number" -- We know 'y' is an Int
-- We can nest matching:
g :: Either String (Maybe a) -> String
g (Left s) = "Message: " ++ s
g (Right (Just _)) = "We have something"
g (Right Nothing) = "We have Nothing"
Also take note that:
f can refer to g which in turn can refer back to f.The relative order of different value definitions does not matter, but the relative order of parts of a value definition does matter. In particular:
f a = ...
f [] = ...
The second declaration will never come into effect because the [] case will always be caught by the first. But in reverse order:
f [] = ...
f a = ...
The [] declaration will be matched.
Haskell allows binary operators to be declared just like other functions. Operators are applied infix just like you would write a mathematical expression. Operators must consist of symbols and declarations and are written mirroring application.
-- Function composition
compose f g x = f (g x)
(f . g) x = f (g x)
apply f x = f x
f $ x = f x
It may be convenient to refer to an operator much like you can refer to a function by giving its name. We can do this by wrapping the symbol in parentheses. For example we could have written the definition of apply as apply = ($) (given that we have defined the symbol '$').
We can also go the other direction and make a function application infix by surrounding it with backticks "`" (the key left of "1" on most keyboards). For example:
blah = f . g
-- is the same as
blah = f `compose` g
We do not have to have a name for every function. We can express values that are functions "on the fly" with a lambda abstraction. Haskell uses the backslash (which looks a little like the Greek letter lambda) to indicate the start of the function. The pattern follows this, then an arrow where there would be an equals in a named declaration:
hypotenuse :: Double -> Double -> Double
-- We could write either of the equivalent
hypotenuse x y = sqrt (square x + square y)
hypotenuse = \x y -> sqrt (square x + square y)
Multiple functions with multiple arguments in Haskell are actually special syntax for a simpler notion. We can limit ourselves to only functions of one argument and when we need two arguments make an outer function of one argument that results in a new function of the second argument. We can see this in the type of hypotenuse when we read (->) as right associative:
hypotenuse :: Double -> (Double -> Double)
hypotenuse = \x -> \y -> sqrt (square x + square y)
Also note that function application is left associative:
ghci> hypotenuse 3 4
5.0
ghci> (hypotenuse 3) 4
5.0
ghci> hypotenuse (3 4)
<interactive>:11:13:
No instance for (Num (a0 -> Double))
arising from the literal `3'
Possible fix: add an instance declaration for (Num (a0 -> Double))
In the expression: 3
In the first argument of `hypotenuse', namely `(3 4)'
In the expression: hypotenuse (3 4)
Note: I give the last example to illustrate that type errors might be difficult to understand at first. At times you will need to ignore the specific types involved and narrow in on the location. In this specific case the "non-sense" that is written is the application of 3 to 4. We do not get an error that says "You can't apply a number as a function!" because given the right instances in play you can apply a number as a function.
We can also partially apply a function and get a new function:
ghci> :type hypotenuse 3
hypotenuse 3 :: Double -> Double
There is another form of partial application for infix operators. This is called an operator section and is written by putting the symbol for an operator and a single argument together in parentheses. For example (+ 3) is the function that adds three to another number. Similarly (2 ^) is the function that raises two to a given power.
ghci> let (~~~) = hyp
ghci> :t (~~~ 4)
(~~~ 4) :: Double -> Double
ghci> (~~~ 4) 3
5.0
We can, of course, get carried away with these operators so use cautiously:
hypotenuse = (sqrt .) . ((+) `on` square)
where
on f g x y = g x `f` g y
We have been holding off long enough and we should now introduce data types. The keyword data lets us write a declaration which gives us a new way to build values that contain data. We write these declarations in a similar way to how we write productions for a grammar. For example:
data Bool = False | True
data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
The name on the left-hand side is the name of the new type we are defining. It may or may not take some parameters. On the right-hand side we have one or more "constructors" that specify the shape of the data. Each constructor gives us a name to use on the left-hand side for pattern matching. On the right-hand side we get a function to build a new value. For example:
ghci> :t Left
Left :: a -> Either a b
ghci> :t Right
Right :: b -> Either a b
Notice that these functions start with a capital letter. You can be assured if you are using a capital letter identifier for function application on the right-hand side that you are building a value of some data type.
Some other useful data types:
-- Warning: it is common to overload the name of the type with a
-- constructor. Do not be confused!
data Pair a = Pair a a
-- This is the standard list type without the special "[]" syntax.
-- Notice the recursive use of "List a".
data List a = Nil | Cons a (List a)
-- This is a tree with data only at the leaves.
-- Notice the recursion again.
data Tree a = Leaf a | Node (Tree a) (Tree a)
Imperative programming languages often have many structures that conditionally perform some operations. Many of these structures involve Boolean conditions. As we saw above Bool in Haskell is just a data type with two constructors that themselves contain no data (beyond their name). Pattern matching gives us the conditional choice:
myIf :: Bool -> a -> a -> a
myIf True t _ = t
myIf False _ f = f
isItFour :: Int -> String
isItFour x = myIf (x == 4) "Yes!" "No."
We often encounter situations where there are several conditions that we want to handle with their own values. There is a built in if then else but its use is not encouraged:
isItFour :: Int -> String
isItFour x = if (x == 4)
then "Yes!"
else "No."
Using an "if" function does not scale well to these situations. Haskell provides special syntax for this situation inspired by mathematical notation for piecewise functions. We first start the function definition as we would normally pattern matching on the left-hand side. Then conditions call "guards" are added each after a pipe "|" symbol and each with an equals sign and a right-hand side. The first option where the condition is met will be the value of the function. A "catch all" case is indicated with otherwise.
isItFour :: Int -> String
isItFour x
| x == 4 = "Yes!"
| otherwise = "No."
whatIsIt :: Int -> String
whatIsIt x
| x == 4 = "Four!"
| even x = "Even!"
| x > 10000 = "Big."
| otherwise = "I'm not sure."
There are situations were we may want to do pattern matching on the right-hand side to inspect some value that will be part of our computation. We can do this with the case of keywords. The pattern matching we have been using on the left-hand side is actually equivalent to using case. Some examples of case statements:
whoIsIt :: Int -> String
whoIsIt x = case whatIsIt x of
"Four!" -> "It's four!"
'B':_ -> "They with a 'B'."
_ -> "Someone else."
ghci> whoIsIt 4
"It's four!"
ghci> whoIsIt 3
"Someone else."
ghci> whoIsIt 3000001
"They with a 'B'."
Notice that because we want to reuse our whatIsIt function we cannot just do our pattern matching on the left-hand side. So we use case. Also notice that we use an arrow -> to separate the sides like with a lambda expression.
Another option would be to use another function as a "helper" to do the inner pattern match. We can declare new values in the context of a right-hand side with access to all the same variables as its parent using the where keyword.
whoIsIt :: Int -> String
whoIsIt x = helper (whatIsIt x)
where
helper "Four!" = "It's four!"
helper ('B':_) = "They with a 'B'."
helper _ = "Someone else."
Note that indentation is important so that we know that helper belongs to whoIsIt. Similarly we can define helper values up front with the let in keywords:
whoIsIt :: Int -> String
whoIsIt x = let
helper "Four!" = "It's four!"
helper ('B':_) = "They with a 'B'."
helper _ = "Someone else."
in helper (whatIsIt x)
Lets pull together several of these concepts in one example.
data List a = Nil | Cons a (List a)
deriving (Show, Eq) -- This tells the compiler to
-- automatically generate code
-- to convert to a String and
-- to evaluate equality.
range a b
| a <= b = Cons a (range (a+1) b)
| otherwise = Nil
allPositives = from 1
where from x = Cons x (from (x + 1))
filterList _ Nil = Nil
filterList p (Cons x xs)
| p x = Cons x (filterList p xs)
| otherwise = filterList p xs
evens = filterList (even) allPositives
takeList _ Nil = Nil
takeList 0 _ = Nil
takeList n (Cons x xs) = Cons x (takeList (n-1) xs)
If we put all of this into a file named example.hs we run can run with:
$ ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load example.hs
[1 of 1] Compiling Main ( example.hs, interpreted )
Ok, modules loaded: Main.
*Main> filterList even (range 1 20) == takeList 10 evens
True