You can read about these topics in Learn You a Haskell, chapter 9 "Input and Output".
We've previously seen that the Functor type class represents any type that we can map over using fmap. Similarly, the Foldable type class represents any type that we can fold over. In fact the built-in functions foldl and foldr are members of this type class.
Certainly the built-in list type []
is an instance of Foldable. In fact Maybe is also a Foldable:
> foldl (+) 2 (Just 10) 12 > foldl (+) 2 Nothing 2
We can see that when folding, a Just acts like a single-element list, and Nothing acts like an empty list.
Many of the built-in functions that we've seen on
lists will actually work on any Foldable. These include all,
any, elem,
product, sum,
and others. So we can write, for example:
> any (>3) (Just 5) True > any (>3) Nothing False > all (>3) (Just 5) True > all (>3) Nothing True > sum (Just 5) 5 > sum Nothing 0
We may declare our own types to be instance of Foldable. To do so, we only need to implement foldr. For example, let's define a binary tree type and make it foldable:
data Tree a = Nil | Node (Tree a) a (Tree a)
deriving (Show, Read)
instance Foldable Tree where
foldr f a Nil = a
foldr f a (Node left x right) =
foldr f (f x (foldr f a right)) left
Because our type is Foldable, many useful built-in functions will now work on it automatically:
> my_tree = Node (Node (Node Nil 1 Nil) 2 (Node Nil 3 Nil)) 4 (Node Nil 5 Nil) > sum my_tree 15 > elem 3 my_tree True > all (>0) my_tree True
In fact Haskell will even implement foldl automatically given our implementation of foldr:
> foldl (+) 0 my_tree 15
Haskell has immutable arrays that allow you to access elements in O(1) using the ! operator. You'll need to import Data.Array to use these.
The listArray function builds an array given a range of indices and a list of values. Let's build an array whose indices are the values 0..5:
> a = listArray (0, 5) [2, 9, 8, 3, 7, 6]
Now we can access elements in constant time:
> a ! 2 8 > a ! 4 7
Array indices can be any instance of the Ix
type class. That includes Int, Integer, Char, and also tuples of
types belonging to Ix. So we can
construct, for example, a 2-dimensional array whose indices are of
type (Int, Int):
> a = listArray ((0, 0), (2, 2)) [7, 2, 4, 8, 9, 5, 3, 11, 14]
This represents the matrix
1 2 4 8 9 5 3 11 14
Again, we can access elements in constant time:
> a ! (1, 1) 9 > a ! (1, 2) 5
The built-in function accumArray builds an array from an association list, using a function to fold together all values with the same key. It has this type:
accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
Here, i is the index type, e is the type of the elements in the input list, and 'a' is the type of the accumulator used for joining elements. This function can be useful for building a histogram of values in a fixed range. As an example, this function will sort a list of integers in a fixed range in linear time:
-- counting sort
sort :: Int -> Int -> [Int] -> [Int]
sort lo hi xs =
let arr = accumArray (+) 0 (lo, hi) [(x, 1) | x <- xs]
in concat [replicate x i | (i, x) <- assocs arr]
Array elements are evaluated lazily, and may even refer to other elements of the same array:
> a = listArray (1, 3) [10, 20, a ! 1 + a ! 2] > a ! 1 10 > a ! 3 30
So we can build an entire array using a recursive calculation. We can use this technique to solve dynamic programming problems in a top-down fashion. For example, consider the following function that calculates the Nth Fibonacci number recursively. It is exponentially inefficient:
fib :: Int -> Int fib 1 = 1 fib 2 = 1 fib n = fib (n - 1) + fib (n - 2)
We can use dynamic programming to cache each return value in an array:
fib :: Int -> Int
fib n = a ! n
where a = listArray (1, n) (1 : 1 : map f [3..n])
f n = a ! (n - 1) + a ! (n - 2)
Now the function will run in linear time.
In Haskell, a do block is like a generalized list comprehension.
As a first example, we may use 'do' with ordinary lists. Consider this list comprehension:
> list = [(x, y) | x <- [1..2], y <- [1..3]] > list [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
We may alternatively write it using 'do' notation:
list = do
x <- [1..2]
y <- [1..3]
return (x, y)
We see that in a 'do' block, we can use the <- operator to retrieve a value. At the end of the 'do' block, we can use the 'return' function to produce a value to be returned. When we use 'do' with ordinary lists, we retrieve values from lists, and the return values are joined together into a list.
We may also use 'do' with Maybe. Here's a function that takes three values of type (Maybe Int), and returns their sum:
add :: Maybe Int -> Maybe Int -> Maybe Int -> Maybe Int
add mx my mz = do
x <- mx
y <- my
z <- mz
return (x + y + z)
Let's try it:
> add (Just 3) (Just 4) (Just 5) Just 12 > add (Just 3) Nothing (Just 5) Nothing
Notice that if any of the input values is absent, the result is Nothing. To see why this is true, recall that a Maybe behaves like a list that has 0 or 1 elements, and notice that the following 'do' block will produce an empty list:
list = do
x <- [3]
y <- []
z <- [5]
return (x + y + z)
A 'do' block with Maybe values can be quite useful for error handling. Suppose that we want to call several functions, any of which might fail and return Nothing. If we place these calls in a 'do' block, then it will return Nothing if any of the function calls failed.
As we saw in the lecture (and you can also read about in Learn You a Haskell), 'do' blocks also work with I/O objects. In future lectures we'll learn more about the type classes underlying 'do' blocks, and will learn how to make our own types that work with 'do'.