# [Haskell] 学习笔记4

### Type declarations

The simplest way of declaring a new type is to introduce a new name for an existing type, using the *type* mechanism of Haskell

The following declaration from the standard prelude states that the type *String* is just a synonym for the type *[Char]* of lists of characters. The name of a new type must begin with a **capital letter**

1 |
type String = [Char] |

Type declarations can be **nested**, in the sense that one such type can be declared in terms of another.

1 2 |
type Pos = (Int,Int) type Trans = Pos -> Pos |

Type declarations **cannot be recursive**

1 |
type Tree = (Int,[Tree]) |

Type declarations can also be **parameterized** by other types

1 2 3 4 5 |
type Pair a = (a,a) type Assoc k v = [(k,v)] find :: Eq k => k -> Assoc k v -> v find k t = head[v| (k',v) <- t, k == k'] |

1 2 |
*Type> find 'a' [('a', 3)] 3 |

### Data declarations

A completely new type, as opposed to a synonym for an existing type, can be declared by specifying its values using the *data* mechanism of Haskell

For example, the following declaration from the standard prelude states that the type Bool comprises two new values, named False and True. In such declarations, the symbol | is read as **or**, and the new values of the type are called **constructors. **As with new types themselves, the names of new constructors must begin with a capital letter.

Note that the names given to new types and constructors have no inherent meaning to the Haskell system. For example, the above declaration could equally well be written as *data A = B | C*

1 |
data Bool = False | True |

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Move = North | South | East | West deriving Show type Pos = (Int, Int) move :: Move -> Pos -> Pos move North (x, y) = (x, y+1) move South (x,y) = (x,y-1) move East (x,y)= (x+1,y) move West (x,y)= (x-1,y) moves :: [Move] -> Pos -> Pos moves [] p = p moves (m:ms) p = moves ms (move m p) -- using foldr --moves instruct p = foldr (\a b -> move a b) p instruct rev :: Move -> Move rev North = South rev South = North rev East= West rev West= East |

The constructors in a data declaration can also have arguments:

1 2 3 4 5 6 7 8 |
data Shape = Circle Float | Rect Float Float square :: Float -> Shape square n = Rect n n area :: Shape -> Float area (Circle r) = pi * r^2 area (Rect x y) = x * y |

1 2 3 4 5 |
*Type> area (Circle 3) 28.274334 *Type> square 9 Rect 9.0 9.0 |

Because of their use of arguments, the constructors Circle and Rect are actually constructor functions, which produce results of type Shape from arguments of type Float.

The difference between normal functions and constructor functions is that the latter have **no defining equations**, and exist purely for the purposes of building pieces of data, the expression Circle 1.0 is just a piece of data

1 2 3 4 |
*Type> :t North North :: Move *Type> :t Circle Circle :: Float -> Shape |

Data declarations themselves can also be parameterized:

1 |
data Maybe a = Nothing | Just a |

That is, a value of type Maybe a is either Nothing, or of the form Just x for some value x of type a. We can think of values of type Maybe a as being values of type a that may either fail or succeed, with Nothing representing failure, and Just representing success

1 2 3 4 5 6 7 8 9 |
data MaybeIs a = ReallyNothing | ReallyJust a deriving Show safediv :: Int -> Int -> MaybeIs Int safediv _ 0 = ReallyNothing safediv m n = ReallyJust(m `div` n) safehead :: [a] -> MaybeIs a safehead [] = ReallyNothing safehead xs = ReallyJust (head xs) |

1 2 3 4 5 |
*Type> safediv 9 3 ReallyJust 3 *Type> safehead [] ReallyNothing |

### Recursive types

The type of natural numbers from the previous section can also be declared in a recursive manner

1 |
data Nat = Zero | Succ Nat |

That is, a value of type Nat is either Zero, or of the form Succ n for some value n of type Nat. Hence, this declaration gives rise to an infinite sequence of values, starting with the value Zero, and continuing by applying the constructor function Succ to the previous value in the sequence:

Zero…Succ Zero … Succ(Succ Zero)…Succ(Succ (Succ Zero))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
data Nat = Zero | Succ Nat deriving Show one :: Nat one = Succ Zero two :: Nat two = Succ one three :: Nat three = Succ two nat2int :: Nat -> Int nat2int Zero = 0 nat2int (Succ n) = 1 + nat2int n int2nat :: Int -> Nat int2nat 0 = Zero int2nat n = Succ (int2nat (n-1)) add :: Nat -> Nat -> Nat add Zero n = n add (Succ m) n = Succ (add m n) |

1 2 3 4 5 |
*Type> add three one Succ (Succ (Succ (Succ Zero))) *Type> nat2int (add three one) 4 |

Binary tree:

1 2 3 4 |
data Tree a = Leaf a | Node (Tree a) a (Tree a) t :: Tree Int t = Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9)) |

value occurs in a leaf if it matches the value at the leaf, and occurs in a node if it either matches the value at the node, occurs in the left subtree, or occurs in the right subtree.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
occurs :: Eq a => a -> Tree a -> Bool occurs x (Leaf y) = x == y occurs x (Node l y r ) = x == y || occurs x l || occurs x r occursBinaryTree :: Ord a => a -> Tree a -> Bool occursBinaryTree x (Leaf y) = x == y occursBinaryTree x (Node l y r) | x == y = True | x < y = occursBinaryTree x l | otherwise = occursBinaryTree x r flatten :: Tree a -> [a] flatten (Leaf x) = [x] flatten (Node l x r) = flatten l ++ [x] ++ flatten r |

### Derived instances

When new types are declared, it is usually appropriate to make them into instances of a number of built-in classes. Haskell provides a simple facility for automatically making new types into instances of the classes *Eq, Ord, Show*, and *Read*, in the form of the *deriving* mechanism.

1 2 |
data Bool = False | True deriving (Eq, Ord, Show, Read) |

1 2 3 4 5 6 7 8 |
> False == False True > False < True True > show False "False" > read "False" :: Bool False |

Note that for the purposes of deriving instances of the class *Ord* of ordered types, the ordering on the constructors of a type is determined by their position in its declaration