You can read about these subjects in Learn You a Haskell, chapter 8.
We've already seen that we can write a function to generate an infinite list of numbers:
intsFrom :: Integer -> [Integer] intsFrom x = x : intsFrom (x + 1)
For example:
> take 10 (intsFrom 1) [1,2,3,4,5,6,7,8,9,10]
Alternatively we may produce this list using a recursive value definition. Consider an infinite list of integers starting with 1:
[1, 2, 3, 4, 5, ...]
If we add 1 to each element of the list, we get
[2, 3, 4, 5, …]
which is the same as the tail of the original list. So we may in fact define this list as 1 followed by the result of adding 1 to each element:
ints :: [Integer] ints = 1 : map (+1) ints
As another example, suppose that we wish to produce this infinite diagonal matrix:
[[1,
0,
0,
0,
...],
[0,
1,
0,
0,
...],
[0,
0,
1,
0,
...],
.
.
.
]
We could write
diag :: [[Integer]]
diag = (1 : [0, 0..]) : map (0:) diag
Here are some types and type classes that we defined in the lecture.
import Data.List
-- A fraction type for rational numbers.
data Frac = Frac Int Int
instance Eq Frac where
(==) (Frac a b) (Frac c d) = a * d == b * c
instance Show Frac where
show (Frac a b) = show a ++ "/" ++ show b
instance Ord Frac where
Frac a b <= Frac c d = a * d <= b * c
-- A generalized fraction type where the numerator and denominator
-- can be of any integral type.
data GFrac t = GFrac t t
instance (Integral t) => Eq (GFrac t) where
(==) (GFrac a b) (GFrac c d) = a * d == b * c
-- A type class for a set of integers.
class IntSet s where
empty :: s
contains :: Int -> s -> Bool
add :: Int -> s -> s
remove :: Int -> s -> s
-- A list of integers is an IntSet.
instance IntSet [Int] where
empty = []
contains = elem
add = (:)
remove = delete
-- A tree of integers is an IntSet.
data IntTree = Nil | Node IntTree Int IntTree
deriving (Show)
instance IntSet IntTree where
empty = Nil
contains x Nil = False
contains x (Node left y right) = case compare x y of
EQ -> True
LT -> contains x left
GT -> contains y right
add x Nil = Node Nil x Nil
add x tree@(Node left y right) = case compare x y of
EQ -> tree
LT -> Node (add x left) y right
GT -> Node left y (add x right)
remove x tree = …
-- A type class for a set of values of any type.
class Set s where
empty :: s a
contains :: Ord a => a -> s a -> Bool
add :: Ord a => a -> s a -> s a
remove :: Ord a => a -> s a -> s a
-- A list is a Set.
instance Set [] where
empty = []
contains = elem
add = (:)
remove = delete
-- A tree is a Set.
data Tree a = Nil | Node (Tree a) a (Tree a)
deriving (Show)
instance Set Tree where
empty = Nil
contains x tree = …
add x tree = …
remove x tree = …We've 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.
As one possible approach, we can provide an implementation of 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
There is another easier, approach that will work for algebraic data
types such as Tree. We can simply derive
Foldable, and then Haskell will
implement both foldr and foldl
automatically:
data Tree a = Nil | Node (Tree a) a (Tree a) deriving (Show, Read, Foldable)