Haskell

A good programming language to start on functional programming ideas (and one that is ever more readily used in practical applications) is Haskell.

Here is a summary of the things covered in lecture. For more information, refer to the first few chapters of http://learnyouahaskell.com/chapters. See also the resources page.

The Structure of Code

The body of a Haskell code file is a bunch of declarations of variable values, represented by expressions, each of which has a particular type, like so:

a :: <type>
a = <expression>

x :: <type>
x = <expression>

myvariable' :: <type>
myvariable' = <expression>

Syntax (mostly)

The <expression> and <type> sections of the code are filled by, broadly speaking, the following syntax:

<expression> ::=             EXAMPLES

    <variable>               x  y  factorial  id

    <constructor>            True  []  (:)

    <pattern match>          case <expression> of
                               <pattern> -> <expression>
                               <pattern> -> <expression>
                               ...

    <lambda>                 \ <pattern> -> <expression>

    <application>            <expression> <expression>

Particular other syntax, like let and where expressions and infix operators, can be considered as syntactic sugar on top of this syntax.

<pattern> ::=                EXAMPLES

    <variable>               x  y  xs ...

(matches anything; assigns the matched value to the variable)

    <wildcard>               _

(matches anything; throws away the value)

    <constructor>            True  []

    <constructor> <pattern>  S x    Just _    y:[]    \_:[]

Data

You define new datatypes (which give the data constructors) by listing all the ways to make (construct) a value of that datatype, as follows:

data MyType = Constructor1
            | Constructor2
            | Constructor3 ...

Note, the names of types and of data constructors must start with capital letters. Constructors can also take input, and act as functions. For example, the option type Maybe has a constructor Nothing which takes no input and gives a Maybe a and a constructor Just which takes as input a value of type a and gives a Maybe a.

data Maybe a = Nothing
             | Just a

Every natural number is either zero or one more than (the successor of) another natural number. Thus, the natural numbers, have a constructor for zero Z, that just gives a Nat, and a constructor for successor, S, that takes some Nat and gives (its successor) Nat. This kind of data type with a recursive definition is called “inductive.”

data Nat = Z
         | S Nat

Another very useful example, lists, have a constructor [] (pronounced “Nil”) and a constructor (:) (pronounced “Cons” (short for constructor)). This definition,

data List a = Nil
            | Cons a (List a)

uses written out words for the type and constructors, while this definition (the real one) uses the actual syntax.

data [a] = []
         | a : [a]

Functions

This is the core of the representation of computation in Haskell and why Haskell is a Functional Programming language. more to come…

Types

Every (well-typed) expression has a type. The “judgment” that an expression <expression> has type <type> is written

<expression> :: <type>

Data Constructors

These have type the type whose values they construct:

True  :: Boolean
False :: Boolean
[]    :: [a]
Z     :: Nat

Functions

The type of a function that takes values of type a and gives values of type b has type a -> b. For example, the function not, which takes a Boolean value and gives its negation, has type Boolean -> Boolean:

not :: Boolean -> Boolean
not = \ b -> if b then False else True

Function Application

If f :: a -> b and x :: a , then (f x) :: b

Pattern Matching

The type of a pattern match expression is the type of all of the subexpressions. They must all be the same type for the overall expression to be well-typed.

Types

Every expression has a type, even types themselves! Their types are called “kinds”. The kind of the usual types, like Boolean, Int, and [a] is *, let’s pronounce it “type” (though, in Haskell, it’s usually pronounced “star”).

Pattern Matching

Data constructors build values, this is how we use values. Examples (the syntax <expression (n)> denotes an expression that can depend on n):

case <Boolean> of
  True  -> <expression>
  False -> <expression>

case <Nat> of
  Z   -> <expression>
  S n -> <expression (n)>

case <List> of
  []   -> <expression>
  x:xs -> <expression (x, xs)>

If you need nested pattern matches,

case <Boolean> of
  True  ->
    case <Nat> of
      Z   -> <expression>
      S n -> <expression (n)>
  False ->
    case <Nat> of
      Z   -> <expression>
      S n -> <expression (n)>

You can simplify by matching on two expressions simultaneously (technically, you are constructing a pair, and then immediately pattern matching the pair constructor away)

case (<Boolean>, <Nat>) of
  (True,  Z)   -> <expression>
  (True,  S n) -> <expression (n)>
  (False, Z)   -> <expression>
  (False, S n) -> <expression (n)>

Variables

We assign values to variables. Computation is just the process of substituting variables and applying functions. more to come…