Haskell: Types & Functions

Functions and Operators

We have two ways to express calculations:

• [infix] operators: 4 + 2, a && b
• function calls: div 8 3, take 2 [1,2,3,4,5], someFunc a b c

Functions and Operators

They can be interchanged: (+) and (&&) are functions; `div` and `take` and `someFunc` are operators. i.e. these are equivalent:

Functions and Operators

Sometimes code can be more readable if you swap functions and operators: I often write a `div` 2 for symmetry with a / 2.

Sometimes it's necessary to have a function, even though you have an operation defined as an operator…

Parts of Lists

There are many ways to dissect lists in Haskell.

head/tail: the first/​rest of the list (but consider a cons pattern, which might be more readable).

Parts of Lists

take/drop: get/​throw away the first elements from a list.

Parts of Lists

takeWhile/dropWhile: take/​drop while a condition is true.

splitAt: chop a list in two at a specific position.

More List Processing

Processing lists so far: list comprehensions and recursion on lists. There are more built-in tools that are worth mentioning…

map: apply a function to each element in a list.

More List Processing

filter: Take only elements of a list that meet some condition.

We could have defined divisors with filter as:

divisors n = filter (divides n) [2..(n `div` 2)]
  where divides a b = (a `mod` b) == 0

More List Processing

Both map and filter duplicate things we can do with list comprehensions (or recursion): use whichever is easier to read in the specific situation.

… but not foldr: used to apply a function across a list.

[Compare the reduce function/​method in Python, Ruby, Scala, JavaScript, Apache Spark.]

More List Processing

An example: sum the values in a list. We could to it recursively:

mySum [] = 0
mySum (x:xs) = x + mySum xs

Important points: the operation is (+) and the starting point (result for []) is 0. Then, an equivalent fold:

mySum' xs = foldl (+) 0 xs

More List Processing

mySum' xs = foldl (+) 0 xs

If we call this on [1,2,3], it expands to:

foldl (+) 0 [1,2,3]
== (+) ((+) ((+) 0 1) 2) 3
== ((0 + 1) + 2) + 3

More List Processing

mySum' xs = foldl (+) 0 xs

The arguments to the fold:

1. the operation: function that combines the accumulator and an element.
2. the zero: correct result for an empty list, and where to start the accumulator.
3. the list.

More List Processing

The foldr function does the same thing, but associates the other way:

foldr (+) 0 [1,2,3]
== 1 + (2 + (3 + 0))

If there's a choice, foldl should be faster, since it's working from the head of the list (but there's more to say about that, later).

More List Processing

foldr and foldl are surprisingly flexible. For example:

myLength xs = foldl oneMore 0 xs
    where oneMore n _ = n+1

When it's called:

myLength "abc"
== oneMore (oneMore (oneMore 0 'a') 'b') 'c'
== oneMore (oneMore 1 'b') 'c'
== oneMore 2 'c'
== 3

More List Processing

Two more:

myConcat xs = foldl (++) [] xs
myReverse xs = foldl prefix [] xs
    where prefix xs x = x:xs

myConcat [[1,2], [3,4], [5,6]]
== ([1,2] ++ [3,4]) ++ [5,6]
== [1,2,3,4,5,6]

myReverse [1,2,3,4]
== prefix (prefix (prefix (prefix [] 1) 2) 3) 4
== prefix (prefix (prefix [1] 2) 3) 4
== prefix (prefix [2,1] 3) 4
== prefix [3,2,1] 4
== [4,3,2,1]

More List Processing

It's (usually?) possible to swap foldr and foldl if you change the operation appropriately.

myReverse' xs = foldr postfix [] xs
    where postfix x xs = xs ++ [x]

myReverse' [1,2,3,4]
== postfix 1 (postfix 2 (postfix 3 (postfix 4 [])))
== postfix 1 (postfix 2 (postfix 3 [4]))
== postfix 1 (postfix 2 [4,3])
== postfix 1 [4,3,2]
== [4,3,2,1]

Haskell Types

We have already seen some simple types:

• Bool: boolean True or False
• Char: one character
• Int: fixed-precision signed integer (usually 64-bit)
• Float/Double: floating-point values

Haskell Types

And compound types:

• Lists which contain several values of a single type, written [Type].
• String: list of characters. Shortcut for [Char].

Haskell Types

All type names start with a uppercase character. Functions and arguments start with lowercase.

Types can be explicitly declared with the :: syntax:

val :: Int
val = 6
lst :: [Int]
lst = [1,2,3]
lstlst :: [[Int]]
lstlst = [[1,2,3], [4,5]]

Haskell Types

…or queried with the GHCi :t command:

Prelude> :t 6
6 :: Num t => t
Prelude> :t "Hello"
"Hello" :: [Char]

Haskell Types

More types…

Integer: arbitrary-precision integer:

Prelude> let base=2 :: Int
Prelude> let power=64 :: Int
Prelude> base ^ power
0
Prelude> let base=2 :: Integer
Prelude> let power=64 :: Integer
Prelude> base ^ power
18446744073709551616

Haskell Types

tuples: collection of values with a fixed length, but may have different types in each position. Different type signatures/​lengths are considered different types.

Prelude> (1, "Hello") :: (Int, String)
(1,"Hello")
Prelude> (1,2,3) :: (Int,Int,Int)
(1,2,3)
Prelude> [(1,'a'), (2,'b')] :: [(Int,Char)]
[(1,'a'),(2,'b')]
Prelude> [(1,'a'), (2,2)]
error…
Prelude> [(1,2,3), (4,5)]
error…

Haskell Types

Functions also have a type. It can (and should) be explicitly declared.

half_of :: Float -> Float
half_of x = x/2
myPower :: Int -> Int -> Int
myPower _ 0 = 1
myPower x y = x * myPower x (y-1)

The type A -> B -> C indicates a function that takes two arguments of type A and B, and returns a C.

Haskell Types

Some functions can work on a variety of types.

*Main> :t zip
zip :: [a] -> [b] -> [(a, b)]
*Main> :t half_of
half_of :: Float -> Float
*Main> let another_half_of x = x/2
*Main> :t another_half_of
another_half_of :: Fractional a => a -> a

Here, a and b are type variables that can represent any type. The function another_half_of has a more general type because it wasn't explicitly declared.

Haskell Types

Functions can also be passed as arguments or returned (as we have seen). Their types are given in the type signature.

*Main> :t map
map :: (a -> b) -> [a] -> [b]
*Main> :t filter
filter :: (a -> Bool) -> [a] -> [a]

flip_args :: (a -> b -> c) -> b -> a -> c
flip_args f x y = f y x

Haskell Types

Types are important in Haskell. Important enough that you can search by type signature in Hoogle.

Some searches to try:

• I think map might exist: (a -> b) -> [a] -> [b]
• … with wrong argument order: [a] -> (a -> b) -> [b]
• What kind of arithmetic is there? Double -> Double -> Double
• What can I do to a list? [Int] -> [Int]

Haskell Types

Everything has a type, even if you don't specify it. Haskell will do type inference to guess the types of values. It's surprisingly good at it.

myAnd False _ = False
myAnd True a = a

*Main> :t myAnd
myAnd :: Bool -> Bool -> Bool

Haskell Types

The inferred types can be useful, but it's often better to give the type explicitly. There can be performance implications: these functions will perform differently:

myPower :: Int -> Int -> Int

myPower :: Integer -> Integer -> Integer

… because Int operations are processor instructions; Integer operations are calls to an arbitrary-precision integer library.

Haskell Types

If you give an explicit type, you can get better error messages when what you write has different types than you intended.

Rule starting with Exercise 3: must give explicit types of functions you declare.

Type Classes

A type class is a set of operations.

• Like a Java or C# interface: a class that implements the right operations can declare that it implements that interface.
• Like Go interfaces, but explicitly declared on the type.
• Like traits in Rust.
• A little like a C++ abstract class: defines a set of operations that must be implemented on a specific class.

Type Classes

e.g. if (==) and (/=) can be applied to values of a type, it is in the Eq type class.

Type classes are indicated in types with =>. e.g.

Prelude> let theSame x y = x == y
Prelude> :t theSame
theSame :: Eq a => a -> a -> Bool

theSame :: Eq a => a -> a -> Bool
theSame x y = x == y

Type Classes

Other important type classes:

• Ord: Eq plus can be ordered ((<), (>=), min, …).
• Num: Number-like things ((+), (*), abs, …).
• Integral: Integer-like things (div, mod, …).
• Fractional: Num plus true division ((/), recip).
• Show: can be converted to a string for display.
• Enum: has previous/​next elements (pred, succ)

Type Classes

e.g.

*Main> :t 6
6 :: Num t => t
*Main> :t 6/4
6/4 :: Fractional a => a
*Main> :t qsort
qsort :: Ord t => [t] -> [t]
*Main> :t (<)
(<) :: Ord a => a -> a -> Bool

Type Classes

Type inference will often give a type class, not a specific type. Types with classes are more flexible: can be used on any value/​type in the class.

Type classes (and type variables) provide easy and flexible polymorphism in Haskell: functions can operate on any type(s) where the operations used in their definition make sense.

Partially-Applied Functions

Consider the type declaration for a two-argument function:

join :: String -> [String] -> String

This is actually parsed as:

join :: String -> ([String] -> String)

i.e. join is actually a function that takes a String and returns a function [String] -> String.

Partially-Applied Functions

So, we can write:

join :: String -> [String] -> String
-- ...
commajoin :: [String] -> String
commajoin = join ", "

Then:

*Main> commajoin ["one", "two", "three"]
"one, two, three"

Partially-Applied Functions

When a function has values applied to some (but not all) of its arguments, it is referred to as a partial function.

A partial function can be treated like any other function. Every function application we have done could have been parenthesized left associating:

map sqrt someList == (map sqrt) someList
foldl (+) 0 someList == ((foldl (+)) 0) someList

Partially-Applied Functions

That means that all of these are the same calculation:

Prelude> div 10 2
5
Prelude> (div 10) 2
5
Prelude> let d10=(div 10) in d10 2
5

Partially-Applied Functions

We can define functions using partial function application as well. These are equivalent:

myConcat :: [[a]] -> [a]
myConcat xs = foldl (++) [] xs

myConcat' :: [[a]] -> [a]
myConcat' = foldl (++) []

Partially-Applied Functions

When you need to pass a function as an argument, a partially-applied function can be used. This example did this with divides n:

divisors n = filter (divides n) [2..(n `div` 2)]
  where divides a b = (a `mod` b) == 0

Partially-Applied Functions

Operators can also be partially-applied, but more flexibly, since you can easily get to either argument.

Prelude> map (12/) [6,2,12]
[2.0,6.0,1.0]
Prelude> map (/12) [6,2,12]
[0.5,0.16666666666666666,1.0]

Curried Functions

Functions (like all examples so far) that take multiple arguments by taking single arguments multiple times are called curried functions. (After Haskell Curry.)

The other possibility (in Haskell) is to wrap multiple arguments in a tuple: an uncurried function. e.g.

myDiv :: (Int, Int) -> Int
myDiv (n,d) = div n d

Curried Functions

There are functions to curry and uncurry two-argument functions:

*Main> (uncurry div) (10,2)
5
*Main> (curry myDiv) 10 2
5

Curried Functions

These are often useful during list manipulations, particularly with zip, which puts two lists together into tuples:

*Main> :t zip
zip :: [a] -> [b] -> [(a, b)]
*Main> zip [1,2,3] ['a','b','c']
[(1,'a'),(2,'b'),(3,'c')]

Curried Functions

Using uncurry, we can operate on these pairs:

addPairwise :: Num a => [a] -> [a] -> [a]
addPairwise xs ys = map (uncurry (+)) (zip xs ys)

addPairwise [1,2,3] [4,5,6]
== map (uncurry (+)) (zip [1,2,3] [4,5,6])
== map (uncurry (+)) [(1,4), (2,5), (3,6)]
== [(uncurry (+)) (1,4), (uncurry (+)) (2,5), (uncurry (+)) (3,6)]
== [(+) 1 4, (+) 2 5, (+) 3 6]
== [5, 7, 9]

Manipulating Functions

Once you start to think of functions as values, there are many useful ways to manipulate them. We have seen:

• partial function application,
• currying/​uncurrying.

But also…

Manipulating Functions

Function composition with (.) (like \(f\circ g\) in a math class). Lets us combine two functions, so:

(f.g) x == f (g x)

Some functions we could have defined this way:

hailLen :: Int -> Int
hailLen = length . hailSeq

reverseJoin :: String -> [String] -> String
reverseJoin s = (join s) . reverse

weekday :: Day -> Int
weekday = snd . mondayStartWeek

[See also tacit- or pointfree-style definitions.]

Manipulating Functions

Reverse function arguments of a (two-argument curried) function with flip. Useful to partially-apply on the second argument.

joinPrimes :: String -> String
joinPrimes = (flip join) ["2", "3", "5", "7", "11"]

myReverse'' :: [a] -> [a]
myReverse'' xs = foldl (flip (:)) [] xs

*Main> joinPrimes ","
"2,3,5,7,11"
*Main> joinPrimes "+"
"2+3+5+7+11"
*Main> myReverse'' "testing"
"gnitset"

Lambda Expressions

Haskell has first-class functions: functions are values just like integers, lists, etc. They can be passed as arguments, assigned names, etc.

When we define things in our code:

val :: Int
val = 6

half_of :: Float -> Float
half_of x = x/2

… val is value of type Int, and half_of is a value of type Float -> Float.

Lambda Expressions

Functions can also be created with lambda expressions. The Greek letter λ is spelled \ in Haskell.

This defines an equivalent function:

half_of' :: Float -> Float
half_of' = \x -> x/2

The lambda expression \x -> x/2 could be read a value [function] that takes an argument called x and returns x/2.

Lambda Expressions

Like partial application, lambdas can be useful to define functions on their own, but are more likely to be used to create readable larger expressions. For example,

addToEach :: Num a => a -> [a] -> [a]
addToEach n lst = map (\x -> x+n) lst

… is arguably more readable than…

addToEach' :: Num a => a -> [a] -> [a]
addToEach' n lst = map addN lst
    where addN x = x+n

Lambda Expressions

Lambda could be more clear than partial application. e.g. which is more readable?

commajoin0, commajoin1, commajoin2 :: [String] -> String
commajoin0 = \xs -> join ", " xs
commajoin1 = join ", "
commajoin2 xs = join ", " xs