「学习笔记」Chapter 7 - Part II Making Our Own Types And Type Classes
Think about how to define a List. List is in a form either be [], or a:List.So we should define it in a recursive way.
-- You must deriving Read, or you will get an error when load this scriptdata MyList a = MyEmpty | MyCons a (MyList a) deriving (Show, Read, Eq, Ord)intList :: MyList IntintList = MyCons 1 ( MyCons 2 (MyEmpty))
Let's test our own List!
ghci>MyEmpty MyEmptyghci>MyCons 1 (MyEmpty)MyCons 1 MyEmptyghci>MyCons 2 (MyCons 1 (MyEmpty))MyCons 2 (MyCons 1 MyEmpty)
You see, MyEmpty equals to [] in List, "MyCons 1 MyEmpty" equals to "1:[]" in List,i.e. 1. "MyCons 2 (MyCons 1 MyEmpty)" equals to "2:1:[]", thus [2,1] in List.
We can define functions to be automatically infix by naming them using only special characters. We can also do the same with constructors, since they’re just functions that return a data type. There is one restriction however: Infix constructors must begin with a colon. Look at an example.
data MyListfix a = MyEmptyfix | a :- (MyListfix a) deriving (Show)
Let's have a test.
ghci>MyEmptyfixMyEmptyfixghci>1 :- MyEmptyfix1 :- MyEmptyfixghci>2 :- (1:- MyEmptyfix)2 :- (1 :- MyEmptyfix)
Be care that you musnt' write
data MyListfix a = MyEmptyfix | a - (MyListfix a) deriving (Show)
Or you will get an error when load script.
To get a better feel for recursive data structures in Haskell, we’re going to implement a binary search tree.
In a binary search tree, an element points to two elements—one on its left and one on its right. The element to the left is smaller;
A tree is either an empty tree or it’s an element that contains some value and two trees.
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
Let's test it!
ghci>EmptyEmptyghci>Node 1 Empty EmptyNode 1 Empty Emptyghci>Node 1 (Node 2 Empty Empty) EmptyNode 1 (Node 2 Empty Empty) Empty
After defining the tree,we need a function to build the tree.
-- Build a treemakeLeaf :: (Ord a) => a -> Tree a -- a should have order propertymakeLeaf x = Node x EmptyTree EmptyTreeinsertNode :: (Ord a) => a -> Tree a -> Tree ainsertNode x EmptyTree = makeLeaf xinsertNode x (Node a leftTree rightTree) | x == a = Node a leftTree rightTree | x < a = Node a (insertNode x leftTree) rightTree | x > a = Node a leftTree (insertNode x rightTree)
Let's test it!
ghci>let t0 = EmptyTreeghci>t0EmptyTreeghci>let t1 = insertNode 1 t0ghci>t1Node 1 EmptyTree EmptyTreeghci>let t2 = insertNode 3 t1ghci>t2Node 1 EmptyTree (Node 3 EmptyTree EmptyTree)ghci>let t3 = insertNode 0 t2ghci>t3Node 1 (Node 0 EmptyTree EmptyTree) (Node 3 EmptyTree EmptyTree)ghci>let t4 = insertNode 7 t3ghci>t4Node 1 (Node 0 EmptyTree EmptyTree) (Node 3 EmptyTree (Node 7 EmptyTree EmptyTree))
Next, we give a function to check whetehr an element is in a tree or not.
isInTree :: (Ord a) => a -> Tree a -> BoolisInTree x EmptyTree = FalseisInTree x (Node a leftTree rightTree) | x == a = True | x < a = isInTree x leftTree | x > a = isInTree x rightTree
Let's test it.
ghci>let t0 = EmptyTreeghci>isInTree 1 t0Falseghci>let t1 = Node 1 (Node 0 EmptyTree EmptyTree) (Node 3 EmptyTree (Node 7 EmptyTree EmptyTree))ghci>isInTree 1 t1Trueghci>isInTree 2 t1Falseghci>isInTree 3 t1Trueghci>isInTree 7 t1Trueghci>isInTree 10 t1False
If we are given a list which is to be used to construct a binary search tree. How to construct it? Instead of construct it manually, we can use fold to construct it.
ghci>let d = [3,1,2,7,2,9]ghci>let tree = foldr insertNode EmptyTree dghci>treeNode 9 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 7 (Node 3 EmptyTree EmptyTree) EmptyTree)) EmptyTree
Be care that you should not use foldl, as the first parameter of insertNode is not a Tree, which we want to accumulate on.
This section explains how to make your own type classes and how to make type instances of them by hand. A quick type class recap: Type classes are sort of like interfaces. A type class defines some behav- ior (such as comparing for equality, comparing for ordering, and enumeration). Types that can be- have in that way are made instances of that type class. The behavior of type classes is achieved by defining functions or just type declarations that we then implement. So when we say that a type is an instance of a type class, we mean that we can use the functions that the type class defines with that type.
First, we look at the definition of Eq in standard library.
class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool x == y = not (x /= y) x /= y = not (x == y)
class Eq a where means a new type class called Eq is being defined. The a is the type variable, so a will play the role of the type that will soon be made an instance of Eq.
So once we have a class, what can we do with it? We can make type instances of that class and get some nice functionality.
If we define a type like
data TrafficLight = Red | Yellow | Green
Notice how we didn’t derive any class instances for it. If you type "Red == Red" in GHCI, you will get an error. We will make TrafficLight an instance of Eq by hand.
instance Eq TrafficLight where Red == Red = True Yellow == Yellow = True Green == Green = True _ == _ = False
Let's test it.
ghci>Red == RedTrueghci>Red == YellowFalse
Let’s make this an instance of Show by hand, too.
instance Show TrafficLight where show Red = "Red Light" show Yellow = "Yellow Light" show Green = "Green Light"-- be care of "show", not "Show"-- "show" is a fucntion name-- "Show" is a type class name
Let's test it.
ghci>RedRed Lightghci>YellowYellow Lightghci>GreenGreen Lightghci>[Red,Green,Yellow][Red Light,Green Light,Yellow Light]
Now, we can define the way to show data of a type, not just a "deriving (Show)".
You can also make type classes that are subclasses of other type classes. For example, Num is a subclass of Eq.
class (Eq a) => Num a where ...
But how are the Maybe or list types made as instances of type classes? Why we ask this question?That is because in the definition of Eq.
class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool x == y = not (x /= y) x /= y = not (x == y)
a is a concrete type, but Maybe and List is not. Notice that although Maybe is not a concrete type, Maybe m is. So we can make Maybe m an instance of Eq.
instance Eq (Maybe m) where Just x == Just y = x == y Nothing == Nothing = True _ == _ = False
If you want to see what the instances of a type class are, just type :info YourTypeClass in GHCi.
ghci>:info Maybedata Maybe a = Nothing | Just a -- Defined in `Data.Maybe'instance Eq a => Eq (Maybe a) -- Defined in `Data.Maybe'instance Monad Maybe -- Defined in `Data.Maybe'instance Functor Maybe -- Defined in `Data.Maybe'instance Ord a => Ord (Maybe a) -- Defined in `Data.Maybe'instance Read a => Read (Maybe a) -- Defined in `GHC.Read'instance Show a => Show (Maybe a) -- Defined in `GHC.Show'
Now, let's make our own type class for fun.
First, we define a type class.
class YesNo a where yesno :: a -> Bool
Then we use it on Int and List
instance YesNo Int where yesno 0 = False yesno _ = Trueinstance YesNo [a] where yesno [] = False yesno _ = True
Now, we can use yesno on Int and List.
ghci>yesno (0 :: Int)Falseghci>yesno []Falseghci>yesno (1 :: Int)Trueghci>yesno [1,2,3]Trueghci>yesno ""Falseghci>yesno "sddf"True
Notice that we should write "(0 :: Int)" as a parameter of yesno, this is becasue we just make Int an instance of YesNo.If we just give a 0, GHCI don't know it is an Integer or an Int.
Now, we’re going to take a look at the Functor type class, which is for things that can be mapped over. First, we look at the definition of Functor.
class Functor f where fmap :: (a -> b) -> f a -> f b
You may find that in the definitions of type classes so far, the type variable that played the role of the type in the type class was a concrete type, like the a in (==) :: (Eq a) => a ->a -> Bool. But now, the f is not a concrete type (a type that a value can hold,like Int, Bool, or Maybe String), but a type constructor that takes one type parameter.
In fact, fmap take a function and a parameter which have the type (f a), then return a value which have the type (f b).
If you can't understand it, let's look at an instance of Functor: map!
map have the type:
map :: (a -> b) -> [a] -> [b]
compare it with fmap
fmap :: (a -> b) -> f a -> f b
As f is a type constructor, then if f x = [x], then f a = [a], f b = [b].
Here's how Maybe is a functor
instance Functor Maybe where fmap f (Just x) = Just (f x) fmap f Nothing = Nothing
Again, notice how we wrote instance Functor Maybe where instead of instance Functor (Maybe m) where. Functor wants a type constructor that takes one type, and not a concrete type.
Another thing that can be mapped over and made an instance of Functor is our Tree a type.
instance Functor Tree where fmap f EmptyTree = EmptyTree fmap f (Node a leftTree rightTree) = (Node (f a) (fmap f leftTree) (fmap f rightTree) )
Let's look at the power of fmap.
ghci>let tree = foldr insertNode EmptyTree [3,1,4,2,5]ghci>treeNode 5 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 4 (Node 3 EmptyTree EmptyTree) EmptyTree)) EmptyTreeghci>let tree2 = fmap (*2) treeghci>tree2Node 10 (Node 4 (Node 2 EmptyTree EmptyTree) (Node 8 (Node 6 EmptyTree EmptyTree) EmptyTree)) EmptyTreeghci>let tree3 = fmap (^2) treeghci>tree3Node 25 (Node 4 (Node 1 EmptyTree EmptyTree) (Node 16 (Node 9 EmptyTree EmptyTree) EmptyTree)) EmptyTree
Now, compare with function map, you may understand how to use instance of Functor. map can map a function on a list, fmap can map a function on a type which is instance of Functor, just like tree in this case.
Here’s how Either a is a functor in the standard libraries
instance Functor (Either a) where fmap f (Right x) = Right (f x) fmap f (Left x) = Left x
You can see how Either a was made an instance instead of just Either. That’s because Either a is a type constructor that takes one parameter, whereas Either takes two. If fmap were specifically for Either a, the type signature would be this:
(b -> c) -> Either a b -> Either a c
The function is mapped in the case of a Right value constructor, but it isn’t mapped in the case of a Left.
Type constructors take other types as parameters to eventually produce concrete types. This behavior is similar to that of functions,which take values as parameters to produce values. Also like functions, type constructors can be partially applied. For example, Either String is a type constructor that takes one type and produces a concrete type, like Either String Int.
In this section, we’ll take a look at formally defining how types are applied to type constructors.
Each value like 3, "Ya",has their own types. Types are little labels that values carry so that we can reason about the values. But types have their own little labels called kinds. A kind is more or less the type of a type.
What are kinds, and what are they good for? Well, let’s examine the kind of a type by using the :k command in GHCi
ghci>:k IntInt :: *ghci>:k [][] :: * -> *ghci>:k (,)(,) :: * -> * -> *
What does that * mean? It indicates that the type is a concrete type. A concrete type is a type that doesn’t take any type parameters. Let's look at kinds of Maybe
ghci>:k MaybeMaybe :: * -> *
This kind tells us that the Maybe type constructor takes one concrete type (like Int) and returns a concrete type (like Maybe Int). Just as Int -> Int means that a function takes an Int and returns an Int, * -> * means that the type constructor takes one concrete type and returns a concrete type.
Let's look at kinds of Maybe Int.
ghci>:k (Maybe Int)(Maybe Int) :: *
You see, it is a concrete type.
