How Haskell overloads function names like
==, <=, + for various types, and how
you can extend them to your own types, and how you can declare your own
overloadable function names.
Two aspects:
== and /= (Haskell's
not-equal operator) as belonging together, a type either has both or lacks
both.
A “type class” links the two aspects:
Using == and /= for example, the class is called
“Eq” in the standard library:
The definition of Eq goes like:
class Eq a where
(==), (/=) :: a -> a -> Bool
-- default implementation for (==)
x == y = not (x /= y)
-- default implementation for (/=)
x /= y = not (x == y)
-- default implementations deliberately circular so an instance just has to
-- override one of them to break the cycle
“For a type a to be an instance, it must support those
functions (of those types)”.
General syntax:
class ClassName typeVar where methodName :: type sig containing typeVar ... -- Optional: default implementations
Bool is an instance, it goes like:
instance Eq Bool where
-- So a=Bool in this context, i.e.,
-- (==), (/=) :: Bool -> Bool -> Bool
False == False = True
True == True = True
_ == _ = False
-- default implementation for (/=) takes hold
WARNING:
A class is not a type. Eq is not a type. These are
illegal:
foo :: Eq -> Eq -> Bool bar :: Eq a -> Eq a -> Bool
A type is not a “subclass”. Bool is not a “subclass”
of Eq.
Method types outside classes look like this:
(==) :: Eq a => a -> a -> Bool
The additional “Eq a =>” is marker for: polymorphic but
user's choice of a must be an instance of Eq. This
marker also appears when you write polymorphic functions using the methods,
e.g.,
-- Determine whether the 3 arguments are mutually equal. Needs the user-chosen -- type to be an instance of Eq (supports "==") but otherwise polymorphic. eq3 :: Eq a => a -> a -> a -> Bool eq3 x y z = x==y && y==zin HaskellTypes2.hs
Another example: The “Ord” class groups together <=,
<, etc.:
class Eq a => Ord a where
compare :: a -> a -> Ordering -- data Ordering = LT | EQ | GT
(<), (<=), (>), (>=) :: a -> a -> Bool
max, min :: a -> a -> a
-- there are default implementations; an instance just has to provide
-- compare or <=
This “Eq a =>” is a bit different. It means: An instance
of Ord is also an instance of Eq. Best understood
from two angles:
If you're making a type an instance of Ord, ensure that it
is also an instance of Eq (write it yourself or import from
someone else's code).
In type signatures, if you say “Ord a”, then you don't
need to say “Eq a”, it's implied.
We say “Ord is a subclass of Eq”, but beware that
this is unrelated to OOP subclasses.
-- Sorting algorithms just need Ord but otherwise polymorphic.
insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xt) = insert x (insertionSort xt)
where
insert e [] = [e]
insert e xs@(x:xt)
| e <= x = e : xs
| otherwise = x : insert e xt
-- De-duplicating sorting uses both (==) and (<). Type sig just needs Ord.
uniqInsertionSort :: Ord a => [a] -> [a]
uniqInsertionSort [] = []
uniqInsertionSort (x:xt) = insert x (uniqInsertionSort xt)
where
insert e [] = [e]
insert e xs@(x:xt)
| e < x = e : xs
| e == x = xs
| otherwise = x : insert e xt
in HaskellTypes2.hs
Recall we defined our own list types:
data MyIntegerList = INil | ICons Integer MyIntegerList
deriving Show
data MyList a = Nil | Cons a (MyList a)
deriving Show
in HaskellTypes2.hs
Let's make them instances of Eq so we can use == on
them too:
instance Eq MyIntegerList where
INil == INil = True
ICons x xs == ICons y ys = x==y && xs==ys
_ == _ = False
instance Eq a => Eq (MyList a) where
-- The "Eq a =>" there means I need to use (==) on type a.
-- Try omitting it to see what happens.
Nil == Nil = True
Cons x xs == Cons y ys = x==y && xs==ys
-- "x==y" is when we need to assume Eq a.
_ == _ = False
in HaskellTypes2.hs
Check out these other type classes:
Bounded,
Enum (its methods are behind the [1..n] notation),
Show,
Read.
Reference: Haskell 2010 Section 6.3: Standard Haskell Classes
Often it is straightforward but boring to write instances for these classes, so the computer offers to auto-gen for you. Restrictions apply. You request it at the definition of your algebraic data type like this:
data MyType = ... deriving (Eq, Ord, Bounded, Enum, Show, Read)
For example the computer would write the same == algorithms
above for MyIntegerList and MyList.
Reference: Haskell 2010 Chapter 11: Specification of Derived Instances
Standard library has Int, Integer, Rational,
Float (single-precision floating point), Double
(double-precision floating point), Complex a (a
is Double or Float usually).
Number operations are grouped into several type classes, e.g.,
Num:
some methods: +, -, *, abs
instances: all number types
Integral:
some methods: div, mod
instances: Int, Integer
Fractional:
some methods: /, recip
instances: Rational, Float, Double,
Complex a
You can add your own number type by making it an instance of the relevant
classes. (E.g., you could have written your own Rational and
Complex.)
Reference: Haskell 2010 Section 6.4: Numbers
Exercise: Why is this a type error?
let xs :: [Double]
xs = [1, 2, 3]
in sum xs / length xs
Answer:
sum xs :: Double
length xs :: Int
(/) wants the two operands to be of the same type.
How to fix: sum xs / fromIntegral (length xs)
or use realToFrac
fromIntegral :: (Integral a, Num b) => a -> b realToFrac :: (Real a, Fractional b) => a -> b
Example: Machine epsilon.
https://gist.github.com/AndrewBarfield/2557034 is forced to write two copies of the same code for two number types because C# is a stupid language.
This is criminal in this the 21st Century.
(But see https://twitter.com/mosheroperandi/status/856946180810354688 for even worse!)
A satisfactory language allows you to hand in just one copy:
epsilon :: (Ord a, Fractional a) => a
epsilon = let
-- [1, 0.5, 0.25, ...]
halves = iterate (/ 2) 1
-- But only those that satisfy 1+e > 1.
notTooSmall = takeWhile (\e -> 1 + e > 1) halves
-- The last such e is the machine epsilon.
in last notTooSmall
epsilonDouble :: Double
epsilonDouble = epsilon
epsilonFloat :: Float
epsilonFloat = epsilon
in HaskellTypes2.hs
Before C++20: Template function prototype does not say which overloaded functions/operators it uses:
template<typename T> List<T> insertionSort(List<T> xs)
{
... just go ahead use <= on T values ...
}
But template is like macro. At use site, compiler has access to the
insertionSort template code (to expand it right there), can see it uses
<=, can check the user-chosen type supports it.
Works, but tight coupling and all its problems: defeats separate compilation, poor error messages.
Since C++20: That, plus concepts, similar to Haskell classes and can do other things.
Type signature states that the type variable has to extend an interface:
<T extends Comparable<T>> List<T> insertionSort(List<T>)
Learned from Haskell type classes but adapted to OOP. (In fact, Java generics came from Phil Wadler who brought it from Haskell parametric polymorphism.)
Good de-coupling and all its benefits (Haskell type classes too):
Friendly to separate compilation:
When compiling insertionSort: Code is allowed to use
comparison methods, does not need to know use sites.
When compiling use site: Compiler checks that user-chosen type extends
Comparable, does not need to read insertionSort internal code,
only needs to read type sig.
Good error messages at use site: Just say “user-chosen type doesn't
extend Comparable”.
A module can take other modules as parameters. Real Template Methods.
Put insertionSort into a module—call it
Sorter—but it takes as parameter another module that
specifies element type and comparator.
(* Example in OCaml *)
module Sorter(Cmp : sig
type t
val leq : (t,t) -> bool
end)
= struct
let rec insertionSort xs = ...
(* insertion sort code; use Cmp.leq to compare *)
end
To use Sorter for ints, write a module that contains int
comparison operators, use it to instantiate Sorter.
(* Example in OCaml *)
module IntCmp = struct
type t = int
let leq (x,y) = x<=y
end
module IntSorter = Sorter(IntCmp)
(* Now can use IntSorter.insertionSort for [int] *)
Similarly for other element types, even alternative orders.