A Quick Tour of Haskell

Functional Tools That You Can Take Home!

By Bailey Parker

Java
public static void <T extends Comparable<T>> quickSort(T[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void <T extends Comparable<T>> quickSort(T[] arr,
                                                        int lo,
                                                        int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }
}

private static int <T extends Comparable<T>> partition(T[] arr,
                                                       int lo,
                                                       int hi) {
    T pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j].compareTo(pivot) < 0) {
            swap(arr, ++i, j);
        }
    }

    swap(arr, i, j);
}

Haskell
sort :: [Integer] -> [Integer]
sort [] = []
sort (pivot:xs) = (sort left) ++ [pivot] ++ (sort right)
  where left = filter (< pivot) xs
        right = filter (>= pivot) xs
Mutability.java:41: error: method solvePuzzle in class Solver cannot be applied to given types;
        solution = solvePuzzle(puzzle);
                   ^
  required: int[][],SolvingStrategy
  found: int[][]
  reason: actual and formal argument lists differ in length
1 error

Learn to ❤ Your Compiler

Type Signatures

Let's start by figuring out the type signatures of Java methods.

Java
static int add(int lhs, int rhs) {
    // ...
}
Haskell
add :: Integer -> Integer -> Integer

The argument types are listed in order, followed by the return type.

Java
static double weirdAdd(float lhs, int rhs) {
      // ...
  }
Haskell
weirdAdd :: Float -> Integer -> Double

More Type Signatures

Lists use a slightly different syntax.

Java
static float average(int[] numbers) {
    // ...
}
Haskell
average :: [Integer] -> Float

But, strings and characters are what you would expect.

Java
static boolean beginsWith(String search, char prefix) {
      // ...
  }
Haskell
beginsWith :: String -> Char -> Bool

Functions as Arguments

What if we pass a function as an argument?

Java
static int findNumber(int[] nums, Predicate<Integer> isWanted) {
    for (int num : nums) {
        if (isWanted.test(num)) { return num; }
    }

    throw new NumberNotFoundException(i);
}
Java
findNumber(oddNumbers, num -> MathUtils.isPrime(num));
Java
interface Predicate<T> {
    boolean test(T t);
}
Java
findNumber(oddNumbers, MathUtils::isPrime);
Haskell
findNumber :: [Integer] -> (Integer -> Bool) -> Integer

The Basics

Basic Operations

Math, boolean, and string operations are straightfoward.

Haskell
> 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15 + 1/17 - 1/19)
3.0418396189294032
Haskell
> (True && False) || (True && True)
True
Haskell
> 8 /= 2 * 2 * 2  -- not equal
False
Haskell
> 1.0 == 1
True
Haskell
> "To understand recursion " ++ "we must first understand recursion"
"To understand recursion we must first understand recursion"

Basic Operations

But you don't get implicit casting...

Haskell
> "A random number: " ++ 4
<interactive>:2:24: error:
  • No instance for (Num String) arising from the literal ‘4’
  • In the second argument of ‘(++)’, namely ‘4’
    In the expression: "A random number: " ++ 4
Haskell
> "A random number: " ++ show 4
"A random number: 4"

Why didn't concatenating a string and integer work? Let's look at the types!

Haskell
(++) :: String -> String -> String
Haskell
show :: Integer -> String

Basic Operations

As an exercise, let's recall the types of some of these functions

Haskell
(+) :: Integer -> Integer -> Integer
(-) :: Integer -> Integer -> Integer
(*) :: Integer -> Integer -> Integer
(/) :: Integer -> Integer -> Integer

(&&) :: Bool -> Bool -> Bool
(||) :: Bool -> Bool -> Bool

Our First Function

In Java, we'd probably want to express factorial iteratively:

Java
public static int factorial(int n) {
    int product = 1;

    for (int i = 1; i <= n; i++) {
        product *= i;
    }

    return product;
}

But in Haskell, we need to think recursively:

Java
public static int factorial(int n) {
   if (n == 0) {
     return 1;
   }

   return n * factorial(n - 1);
}

Our First Function

Java
public static int factorial(int n) {
   if (n == 0) {
     return 1;
   }

   return n * factorial(n - 1);
}

Translated "verbatim" to Haskell, this would look like:

Haskell
factorial :: Integer -> Integer
factorial n = if n == 0
                 then 1
                 else n * factorial (n - 1)

Do you see any issues with these implementations?

Lists

The bread and butter of functional programming is lists.

GHCI
> ["lists", "must", "be", "homogenous"]
["lists", "must", "be", "homogenous"]
GHCI
> ["so", "this", "breaks", 22]
<interactive>:5:26: error:
    • No instance for (Num String) arising from the literal ‘22’
    • In the expression: 22
      In the expression: ["so", "this", "breaks", 22]

The above is syntactic sugar for an important function called cons:

GHCI
> "cons" : "prepends" : ["to", "lists"]
["cons", "prepends", "to", "lists"]
Haskell
(:) :: a -> [a] -> [a]

Type Variables

Haskell
(:) :: a -> [a] -> [a]

This is similar to generics in Java:

Java
public static <T> T[] cons(T item, T[] items) {
    // ...
}

So, a or T can be replaced with any type.

GHCI
> 1 : [2, 3]
[1, 2, 3]
> "one" : ["two", "three"]
["one", "two", "three"]
Java
cons(1, new Integer[] {2, 3}); // {1, 2, 3}
cons("uno", new String[] {"dos", "tres"}); // {"uno","dos","tres"}

Lists

Strings are just lists of characters!

GHCI
> ['J','o','h','n',' ','H','o','p','k','i','n']
"John Hopkin"
> 'J':'o':'h':'n':' ':'H':'o':'p':'k':'i':'n':[]
"John Hopkin"

And concatenation works on generic lists, not just strings!

GHCI
> [1, 2, 3] ++ [4, 5, 6]
[1, 2, 3, 4, 5, 6]

And that's because the type of concatenate is actually general:

Haskell
(++) :: [a] -> [a] -> [a]

Lists

Constructing lists of numbers is tedious, so we use ranges instead:

GHCI
> [1..10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

> [10,9..1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Lists

There are lots of builtin functions for working with lists.

GHCI
> length [2, 3, 4, 5, 6]
5

> intercalate ", " ["foo", "bar", "baz"]
"foo, bar, baz"

> concat [[1, 2, 3], [2, 4, 6]]
[1, 2, 3, 2, 4, 6]

> head ["foo", "bar", "baz"]
"foo"

Lists

What about infinite lists?

GHCI
> [1..]
[1, 2, 3, 4, 5,  -- forever and ever

> head [1..]
1

Why doesn't the first one never finish, but the second does? Laziness

Python
def positive_integers():
    i = 1
    while True:
        yield i
        i += 1

> numbers = positive_integers()
> next(numbers)
1
> next(numbers)
2

Lists

But what happens if we do this:

GHCI
> head []
*** Exception: Prelude.head: empty list

This is bad. It compiles, but you get a runtime error. We can do better!

Guard Syntax

Our previous implementation is bad, because it uses control structures.

Haskell
factorial :: Integer -> Integer
factorial n = if n == 0
                 then 1
                 else n * factorial (n - 1)

The preferred approach when you have conditions is guard syntax:

Haskell
factorial :: Integer -> Integer
factorial n | n == 0    = 1
            | otherwise = n * factorial (n - 1)

This syntax also allows multiple branches:

Haskell
factorial :: Integer -> Integer
factorial n | n < 0  = error "complex number"
            | n == 0    = 1
            | otherwise = n * factorial (n - 1)

But for this there's an even better approach.

Pattern Matching

Haskell
factorial :: Integer -> Integer
factorial n = if n == 0
                 then 1
                 else n * factorial (n - 1)

Pattern matching works by choosing which expression to evaluate (which definition of a function to use) based on argument patterns:

Haskell
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

You can use _ (hole) to indicate that you don't care about the value of an argument (matches any value):

Haskell
ignoreSecond :: a -> b -> a
ignoreSecond a _ = a

Pattern Matching

As an example say we wanted to write a function to sum a list of numbers:

Python
def sum(numbers):
    total = 0
    for number in numbers:
        total += number
    return total

We need to write this recursively to translate it to Haskell:

Python
def sum(numbers):
    return numbers[0] + sum(numbers[1:])

But you may notice this has a bug!

Python
def sum(numbers):
    if len(numbers) == 0:
        return 0
    return numbers[0] + sum(numbers[1:])

Pattern Matching

Python
def sum(numbers):
    if len(numbers) == 0:
        return 0
    return numbers[0] + sum(numbers[1:])

With a correct Python implementation, we can see a clear path to the Haskell version:

Haskell
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs

Pattern Matching

Haskell
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs

Cons can be used in pattern matching to destructure lists:

Haskell
sum [1, 2, 3] = sum (1 : [2, 3])
                 = 1 + sum [2, 3]
                 = 1 + sum (2 : [3])
                 = 1 + 2 + sum [3]
                 = 1 + 2 + sum (3 : [])
                 = 1 + 2 + 3 + sum []
                 = 1 + 2 + 3 + 0

This is a useful pattern! We can use it for other operations on lists.

Pattern Matching

We can also build a function to compute the product of a list of numbers.

Haskell
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
Haskell
product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs

These work as you would expect:

GHCI
> sum [1, 3, 5]
8

> product [1, 3, 5]
15

But wait, isn't n! the product of all integers from 1 to n?

Pattern Matching

So, when we originally had:

Haskell
factorial :: Integer -> Integer
factorial n = 1
factorial n = n * factorial (n - 1)

We can combine our product and ranges to arrive at:

Haskell
factorial :: Integer -> Integer
factorial n = product [1..n]

Small, Composable Functions

Prefer small functions that do one thing well. For more complex tasks, compose these small functions together. This makes you code more easily testable and more obviously correct.

Also known as the single resposibility principle.

Pattern Matching

Returning our list operations, we should notice a pattern:

Haskell
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs

product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs

train :: Model -> Example -> Model
emptyModel :: Model
-- Leave it to the pros...

machineLearn :: [Example] -> Model
machineLearn [] = emptyModel
machineLearn (x:xs) = train (machineLearn xs) x

All of these have some default value for the base case (empty list), and apply a function recursively on this list until that base case is reached. There is an opportunity to refactor!

Pattern Matching

Haskell
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ initial [] = initial
foldl action initial (x:xs) = action (foldl action initial xs) x

The works exactly how our sum did!

Haskell
sum             [1, 2] = sum (1 : [2])
                          = 1 +   sum [2]
                          = 1 +   sum (2 : [])
                          = 1 +   2 +   sum []
                          = 1 +   2 +   0
Haskell
foldl f initial [1, 2] = foldl f initial (1 : [2])
                          = 1 `f` (foldl f initial [2])
                          = 1 `f` (foldl f initial (2 : []))
                          = 1 `f` 2 `f` (foldl f initial [])
                          = 1 `f` 2 `f` initial

Pattern Matching

Haskell
foldl :: (a -> b -> a) -> a -> [b] -> a

With this behavior extracted, we can rewrite our other functions:

Haskell
sum :: [Integer] -> Integer
sum xs = foldl (+) 0 xs

product :: [Integer] -> Integer
product xs = foldl (*) 1 xs

train :: Model -> Example -> Model
emptyModel :: Model
-- Leave it to the pros...

machineLearn :: [Example] -> Model
machineLearn examples = foldl train emptyModel examples

Pattern Matching

Haskell
sum xs = foldl (+) 0 xs
product xs = foldl (*) 1 xs
machineLearn examples = foldl train emptyModel examples

This is a worthwhile refactoring, because if for example, we test foldl and train and are sure that they are correct, then we know that machineLearn is also correct!

Don't Repeat Yourself!

Extract common behavior between functions into a small, composable function to make your functions easier to reason about and more obviously correct.

Pattern Matching

It turns out there are other functions like this. What if we wanted a list of prime numbers?

One (naive) way to obtain this is to go through a list of all positive integers and pull out the ones that are prime.

Haskell
-- Assuming we had a:
isPrime :: Integer -> Bool

primes :: [Integer]
primes = filter isPrime [2..]

We could do this with a function like:

Haskell
filter (a -> Bool) -> [a] -> [a]
filter predicate xs = foldl collect [] xs
  where collect :: [a] -> a -> [a]
        collect collected item | predicate item = item:collected
                               | otherwise      = collected
Haskell
foldl :: (c -> d -> c) -> c -> [d] -> c

Pattern Matching

What if we had a list of videos that we needed to re-encode for different clients (different qualities and sizes for mobile devices, for example) for a video CDN? We have a function that does the re-encoding and a list of videos.

Haskell
encodeVideo :: Video -> [EncodedVideo]

encodeVideos :: [Video] -> [[EncodedVideo]]
encodeVideos videos = map encodeVideo videos

map :: (a -> b) -> [a] -> [b]
map f (x:xs) = f x : map f xs

See the mistake? Haskell does!

Haskell
<interactive>:2:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
        In an equation for ‘map’: Patterns not matched: _ []
Haskell
map (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

Pattern Matching

Check Your Cases

Use enums and inversion of control to have the compiler check that you have implemented all cases. In switch statements, the compilers can usually point out missed cases. In other cases, instead of code like this:

Java
if (entry instanceof Book) {
  return ((Book) entry).getIsbn();
} else if (entry instanceof Movie) {
  return ((Movie) entry).getBarcode();
}

Prefer code like this:

Java
interface Identifiable {
  public String getIdentifier();
}

class Book implements Identifiable {
  public String getIdentifier() { return this.getIsbn(); }
}

class Movie implements Identifiable {
  public String getIdentifier() { return this.getBarcode(); }
}

// And then use it like...
return entry.getIdentifier();

Pattern Matching

What if we want to consider pairs of items from two lists at the same time?

Haskell
zip :: [a] -> [b] -> [(a, b)]
zip (x:xs) (y:ys) = (x, y) : zip xs ys
zip _ _ = []
GHCI
> zip ["Compilers", "PL", "Parallel"] [62, 95, 89]
[("Compilers", 62), ("PL", 95), ("Parallel", 89)]

This family of functions leads us to our next tip:

Use Lazy Functional Utilities

Prefer lazy functional tools like map, filter, zip. They don't construct lists in memory, so they're often more efficient.

Python has functions of this name. In Java 8, look at the Stream API.

Pattern Matching

As an example, instead of doing:

Python
courses = ["Compilers", "PL", "Parallel"]
grades = [62, 95, 89]

for i, course in enumerate(courses):
    print(f'I got a {grades[i]} in {course}!')

Prefer this:

Python
courses = ["Compilers", "PL", "Parallel"]
grades = [62, 95, 89]

for course, grade in zip(courses, grades):
    print(f'I got a {grade} in {course}!')

Because there are no explicit indexes, it's hard to pair two things incorrectly. And you'll also never run into any IndexErrors or ArrayOutOfBoundsExceptions!

Currying

In Haskell, a function always takes one parameter and returns some value.

Wait, what?

Haskell
(+)     :: Integer -> (Integer -> Integer)
(1 +)   ::            Integer -> Integer
(1 + 1) ::                       Integer

This means we can do:

GHCI
> map (2 *) [1..5]
[2, 4, 6, 8, 10]

Putting It All Together

Quicksort

Can you implement quicksort correctly from memory? Do you get all of the bounds correct? How about the termination conditions?

Java
public static void <T extends Comparable<T>> quickSort(T[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void <T extends Comparable<T>> quickSort(T[] arr,
                                                        int lo,
                                                        int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }
}

private static int <T extends Comparable<T>> partition(T[] arr,
                                                       int lo,
                                                       int hi) {
    T pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j].compareTo(pivot) < 0) {
            swap(arr, ++i, j);
        }
    }

    swap(arr, i, j);
}

Quicksort

Wouldn't you rather write?

Haskell
sort :: [Integer] -> [Integer]
sort [] = []
sort (pivot:xs) = (sort left) ++ [pivot] ++ (sort right)
  where left = filter (< pivot) xs
        right = filter (>= pivot) xs

Typeclasses

What if we wanted to make a quicksort work for lists of anything that can be ordered?

Haskell
sort :: [a] -> [a]
sort [] = []
sort (pivot:xs) = (sort left) ++ [pivot] ++ (sort right)
  where left = filter (< pivot) xs
        right = filter (>= pivot) xs

<interactive>:16:24: error:
    • No instance for (Ord a) arising from a use of ‘<’
      Possible fix:
        add (Ord a) to the context of the type signature for:
            sort :: forall a. [a] -> [a]
    • In the first argument of ‘filter’, namely ‘(< pivot)’
      In the expression: filter (< pivot) xs
      In an equation for ‘left’: left = filter (< pivot) xs

<interactive>:17:25: error:
    • No instance for (Ord a) arising from a use of ‘>=’
      Possible fix:
        add (Ord a) to the context of the type signature for:
            sort :: forall a. [a] -> [a]
    • In the first argument of ‘filter’, namely ‘(>= pivot)’
      In the expression: filter (>= pivot) xs
      In an equation for ‘right’: right = filter (>= pivot) xs

Typeclasses

So let's take its advice!

Haskell
sort :: Ord a => [a] -> [a]
sort [] = []
sort (pivot:xs) = (sort left) ++ [pivot] ++ (sort right)
  where left = filter (< pivot) xs
        right = filter (>= pivot) xs

So why did this work?

Haskell
class Ord a where
    compare :: a -> a -> Ordering  -- either LT, EQ, or GT

Typeclasses

Other interesting typeclasses:

Haskell
class Eq a where
    (==) :: a -> a -> Bool

class Show a where
    show :: a -> String

class Num a where
    (+) :: a -> a -> a
    (-) :: a -> a -> a
    (*) :: a -> a -> a
    negate :: a -> a
    abs :: a -> a
    signum :: a -> a
    fromInteger :: Integer -> a

Representing Data

Data

How do we represent data?

Java
public class Product {
    public String name;
    public float cost;

    public Product(String name, float cost) {
        this.name = name;
        this.cost = cost; // NOTE: NEVER use floats for currency
    }

    public int hashCode() { return this.name.hashCode(); }

    public boolean equals(Object other) {
        if (other instanceof Product) {
            return this.name == ((Product) other).name;
        }

        return false;
    }

    public String toString() {
        return "Product: " + this.name + " - Cost: $" + this.cost;
    }
}

Data

What could go wrong with that Java code?

Java
HashMap<String, Product> products = new HashMap<>();

Product slapChop = new Product("Slap Chop", 4.95f);
products.put(slapChop.name, slapChop);

System.out.println(products.get("Slap Chop"));
// Product: Slap Chop - Cost: $4.95

// They decided to rebrand
slapChop.name = "Slap Chop!";

System.out.println(products.get("Slap Chop!"));
// null

Because Product was mutable, it was hard to see this problem.

Data

Haskell has a simple answer. Data is immutable by default. If you want to change data, you need to reconstruct it.

Haskell
data Product = Product String Float

describeProduct :: Product -> String
describeProduct (Product name cost) =
  "Product: " ++ name ++ " - Costs: $" ++ (show cost)

recommend :: Product -> String
recommend (Product name _) =
  "Other customers also bought: " ++ name

discount :: Product -> Product
discount (Product name cost) = Product name (cost / 2)

Immutability

Prefer immutable objects where possible. It is easier to reason about things that don't change.

Data

There are also other advantages to Haskell's approach. Consider:

Java
public class Cart {
    protected List<Product> products;

    public boolean isEmpty() {
        return this.products.size() == 0;
    }
}
Haskell
data Cart = Cart [Product]

isEmpty :: Cart -> Bool
isEmpty (Cart []) = True
isEmpty _ = False

Every value is not nullable in Haskell!

Null Considered Harmful

Avoid null where possible! Use static analysis tools to ensure that values you expect to be non-null aren't actually null.

Data

But what if we want a nullable value?

Haskell
lookupBarcode :: String -> Product
lookupBarcode = -- How do we handle failure?
Haskell
data Maybe a = Just a
             | Nothing
Haskell
lookupBarcode :: String -> Maybe Product
lookupBarcode "01234" = Just $ Product "Tide Pods" 4.95f
lookupBarcode _       = Nothing
GHCI
> lookupBarcode "01234"
Just (Product "Tide Pods" 4.95f)

> lookupBarcode "45678"
Nothing
Haskell
($) : (a -> b) -> a -> b

Data

But then how do we compose functions that return a Maybe?

This won't work:

Haskell
recommend :: Product -> String
lookupBarcode :: String -> Maybe Product

recommendBarcode :: String -> String
recommendBarcode barcode = recommend $ lookupBarcode barcode

<interactive>:26:40: error:
    • Couldn't match expected type ‘Product’
                  with actual type ‘Maybe a0’
    • In the second argument of ‘($)’, namely ‘lookupBarcode barcode’
      In the expression: recommend $ lookupBarcode barcode
      In an equation for ‘recommendBarcode’:
          recommendBarcode barcode = recommend $ lookupBarcode barcode

Data

To do this we'll take advantage of a typeclass called Functor.

Haskell
class Functor f where
    (<$>) :: (a -> b) -> f a -> f b

Doesn't this look familiar?

Haskell
map :: (a -> b) -> [a] -> [b]

For Maybe it is defined like so:

Haskell
instance Functor Maybe where
    f <$> (Just x) = Just $ f x
    _ <$> Nothing = Nothing

We can take advantage of this and write:

Haskell
recommend :: Product -> String
lookupBarcode :: String -> Maybe Product

recommendBarcode :: String -> Maybe String
recommendBarcode barcode = recommend <$> lookupBarcode barcode

Resources

Learn You a Haskell for Great Good

Hoogle - for when you need a function

Questions?

/