first commit
mhe authored 1 week ago
even-more-typeclasses.md 5.35 KiB
Type classes in more detail Some Haskell options we will use in this file
Copyright By PowCoder代写 加微信 powcoder
We’ll be using the following Haskell option to have more flexibility in the ways we are allowed to define thin {-# Language FlexibleInstances #-}
We will also use the option below
{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}
to ask ghc to give us warning when we don’t have enough patterns in a definition by pattern matching. Motivation
Consider the following interaction at the ghci command prompt:
Prelude> “abcd” == “ab” ++ “cd”
Prelude> “abcd” == reverse (“ab” ++ “cd”) False
Good. We successfully compared some strings for equality. But now consider the Haskell code below
f1, f2, f3 :: Bool -> Bool
f1 x = if x then False else True f2 x = not x
and try to see whether these two functions are equal at the
ghci prompt:
Prelude> f1 == f2
Why do we get an error? Because Haskell doesn’t know how to compare functions for equality. In this particular ca two functions are equal. But, from Computability Theory, we know that, unfortunately, there is no algorithm that ca functions are equal, in general
But Haskell gives us a more cryptic error message instead:
• No instance for (Eq (Bool -> Bool)) arising from a use of ‘==’ (maybe you haven’t applied a function to enough arguments?)
• In the expression: f1 == f2
In an equation for ‘it’: it = f1 == f2
What does this mean? It means that there is no equality function == defined for the function type Bool -> Bool For this particular type Bool -> Bool , it is easy to compare functions for equality, and we can implement it:
instance Eq (Bool -> Bool) where
f == g = f True == g True && f False == g False
Now we can compare our functions f1, f2, f3 successfully for equality at the ghci prompt:
*Main> f1 == f2 True
*Main> f1 == f3 False
We can do better, in the sense of being more general:
instance Eq a => Eq (Bool -> a) where
f == g = f True == g True && f False == g False
In English, this says the following:
• If we know how to compare elements of the type a for equality,
• then we can compare functions f,g :: Bool -> a for equality using the algorithm f True == g True &&
Self-contained example
The following Haskell code is self-contained and deliberately doesn’t use any Haskell library, not even the pr picture of
• what type classes are,
• what they are for, and
• how they are used.
We now define our own equality class from scratch as follows. We only include an equality function in our definition, written === :
class MyEq a where
(===) :: a -> a -> Bool
We implement this equality for some types. Booleans first:
instance My where
False === False = True
True === True = True
_ === _ = False
Now pairs. What is different here is that assuming we have equality on the types a and b , we define equality on
instance (MyEq a , MyEq b) => MyEq (a , b) where (x , y) === (u , v) = x === u && y === v
Similarly, if we have equality in the type a , then we can define equality in the type [a] of lists of elements of typ
instance MyEq a => MyEq [a] where
[] === [] = True
(x:xs) === (y:ys) = x === y && xs === ys _ === _ = False
instance MyEq a => MyEq (Bool -> a) where
f === g = f True === g True && f False === g False
Here are some examples of functions using the above:
allEqual :: MyEq a => [a] -> Bool
allEqual [] = True
allEqual (x:[]) = True
allEqual (x:y:zs) = x === y && allEqual (y:zs)
someDifferent :: MyEq a => [a] -> Bool
someDifferent [] = False
someDifferent (x:[]) = False
someDifferent (x:y:zs) = not (x === y) || someDifferent (y:zs)
Convince yourself that allEqual xs === not (someDifferent xs) is True for all lists xs :: [a] . (L induction on lists and be able to argue rigorously to show this.)
We now illustrate default methods:
class YourEq a where (====) :: a -> a -> Bool (=//=) :: a -> a -> Bool
a====b=not(a=//=b) a=//=b=not(a====b)
The last two are the default definitions:
— (1) — (2)
— Default definition of (1) using (2)
— Default definition of (2) using (1)
• If we define (1), then we don’t need to define (2).
• If we define (2), then we don’t need to define (1).
• But we can define both if we want.
Some examples follow:
• Only define (1):
instance Your where False ==== False = True True ==== True = True _ ====_ = False
• We only define (2):
instance (YourEq a , YourEq b) => YourEq (a , b) where
(x , y) =//= (u , v) = x =//= u || y =//= v
• We only define (1):
instance YourEq a => YourEq [a] where
[] ==== [] = True
(x:xs) ==== (y:ys) = x ==== y && xs ==== ys _ ==== _ = False
We define both (1) and (2):
instance YourEq a => YourEq (Bool -> a) where
f ==== g = f True ==== g True && f False ==== g False f =//= g = f True =//= g True || f False =//= g False
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com