A crash course in Haskell

Functions and Programming









What is Haskell?


A typed, lazy, purely functional programming language


Haskell = λ-calculus ++

  • better syntax
  • types
  • built-in features
    • booleans, numbers, characters
    • records (tuples)
    • lists
    • recursion







Why Haskell?

Haskell programs tend to be simple and correct

Elizabeth Murnane Motahareh Eslamimehdiabadi Cesar Torres

QuickSort in Haskell

Goals for this week

  1. Understand the code above
  2. Understand what typed, lazy, and purely functional means (and why it’s cool)







Haskell vs λ-calculus: similarities

(1) Programs

A program is an expression (not a sequence of statements)

It evaluates to a value (it does not perform actions)

(2) Functions

Functions are first-class values:

  • can be passed as arguments to other functions
  • can be returned as results from other functions
  • can be partially applied (arguments passed one at a time)

But: unlike λ-calculus, not everything is a function!

(3) Top-level bindings

Like in Elsa, we can name terms to use them later

Elsa:

Haskell:

The names are called top-level variables

Their definitions are called top-level bindings







Better Syntax: Equations and Patterns

You can define function bindings using equations:







A single function binding can have multiple equations with different patterns of parameters:

At run time, the first equation whose pattern matches the actual arguments is chosen

For now, a pattern is:

  • a variable (matches any value)

  • or a value (matches only that value)



Same as:



Same as:







QUIZ

Which of the following definitions of pair is incorrect?

A. pair x y = \b -> if b then x else y

B. pair x = \y b -> if b then x else y

C.

D.

E. all of the above







Equations with guards

An equation can have multiple guards (Boolean expressions):

Same as:










Recusion

Recursion is built-in, so you can write:

or you can write:









The scope of variables

Top-level variable have global scope, so you can write:



Or you can write:




Is this allowed?





Local variables

You can introduce a new (local) scope using a let-expression:




Syntactic sugar for nested let-expressions:




If you need a variable whose scope is an equation, use the where clause instead:









Types





What would Elsa say?





What would Python say?





What would Java say?








Types

In Haskell every expression either

  • ill-typed and rejected at compile time or
  • has a type and can be evaluated to obtain _ a value of the same type.

Ill-typed* expressions are rejected statically at compile-time, before execution starts

  • like in Java
  • unlike λ-calculus or Python …









Why are types good?

  • Helps with program design
  • Types are contracts (ignore ill-typed inputs!)
  • Catches errors early
  • Allows compiler to generate code
  • Enables compiler optimizations







Type annotations

You can annotate your bindings with their types using ::, like so:

If you omit annotations, GHC will infer them for you

  • Inspect types in GHCi using :t
  • You should annotate all top-level bindings anyway! (Why?)







Function Types

Functions have arrow types:

  • \x -> e has type A -> B
  • if e has type B assuming x has type A

For example:





Always annotate your function bindings

First understand what the function does

  • Before you think about how to do it





When you have *multiple arguments

For example

why? because the above is the same as:

however, as with the lambdas, the -> associates to the right so we will just write:







Lists

A list is

  • either an empty list

    [] -- pronounced "nil"

  • or a head element attached to a tail list

    h : t -- pronounced "h cons t"



Examples:





Terminology: constructors and values

[] and (:) are called the list constructors

We’ve seen constructors before:

  • True and False are Bool constructors
  • 0, 1, 2 are … well, you can think of them as Int constructors
    • The Int constructors don’t take any parameters, we just called them values

In general, a value is a constructor applied to other values

  • examples above are list values









The Type of a List

A list has type [Thing] if each of its elements has type Thing

Examples:







Lets write some Functions

A Recipe

Step 1: Write some tests

Step 2: Write the type

Step 3: Write the code

Functions on lists: range

1. Tests

2. Type

3. Code






Syntactic Sugar for Ranges

There’s also syntactic sugar for this!









Functions on lists: length

1. Tests

2. Type

3. Code











Pattern matching on lists



A pattern is either a variable (incl. _) or a value

A pattern is

  • either a variable (incl. _)
  • or a constructor applied to other patterns



Pattern matching attempts to match values against patterns and, if desired, bind variables to successful matches.







Functions on lists: take

Let’s write a function to take first n elements of a list xs.

1. Tests

2. Type

3. Code

QUIZ

Which of the following is not a pattern?

A. (1:xs)

B. (_:_:_)

C. [x]

D. [1+2,x,y]

E. all of the above







Strings are Lists-of-Chars

For example

shout Shout SHOUT

How can we convert a string to upper-case, e.g.


Some useful library functions


You can search for library functions on Hoogle!







Tuples


(,) is the pair constructor



Field access

Using fst and snd

Tuples to pass parameters

but watch out, add2 expects a tuple.

Tuples and Pattern Matching

It is often clearer to use patterns for tuples, e.g.

or equivalently,

or, best, use the pattern in the parameter,



You can use pattern matching not only in equations, but also in λ-bindings and let-bindings!






QUIZ: Pattern matching with pairs

Is this pattern matching correct? What does this function do?

What is quiz "dog" [ ("cat", 10), ("dog", 20), ("cat", 30)] ?

A. Type error!

B. 0

C. 10

D. 20

D. 30








Generalized Tuples

Can we implement triples like in λ-calculus?





Sure! but Haskell has native support for n-tuples:

The “Empty” Tuple

It also makes sense to have an 0-ary tuple:

often used like void in other languages.







List comprehensions

A convenient way to construct lists!

QUIZ

What is the result of evaluating:

A. Infinite loop B. [] C. [0, 10, 20, 30, 40, 50] D. 150 E. Type error






Comprehensions and Ranges

Recall you can enumerate ranges as

So, we can write the above more simply

QUIZ: Composing Comprehensions

What is the result of evaluating

A. Type error B. [] C. [0,1] D. [(0,0), (1,1)] E. [(0,0), (0,1, (1,0), (1,1)]






QUIZ: Composing Comprehensions

What is the result of evaluating

A. Type error B. [] C. [0,1] D. [(0,0), (1,1)] E. [(0,0), (0,1, (1,0), (1,1)]







shout revisited

How can we convert a string to upper-case, e.g.

Use comprehensions to write a *non-recursive" shout?






QuickSort in Haskell

Step 1: Write some tests

Step 2: Write the type

Step 3: Write the code







Haskell is purely functional

Functional = functions are first-class values

Pure = a program is an expression that evaluates to a value

Referential transparency: The same expression always evaluates to the same value


Why is this good?

  • easier to reason about (remember x++ vs ++x in C++?)
  • enables compiler optimizations
  • especially great for parallelization (e1 + e2: we can always compute e1 and e2 in parallel!)







QUIZ

The function head returns the first element of a list.

What is the result of:

A. Loops forever B. Type error C. 0 D. 1

Haskell is Lazy

An expression is evaluated only when its result is needed!

Why?




Why is this good?






That’s all folks!