quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort (x:xs) = l ++ [x] ++ r
where
(l, r) = partition (< x) xs
quickSort :: [a] -> [a]
quickSort [] = []
quickSort (x:xs) = l ++ [x] ++ r
where
(l, r) = partition (< x) xs
Enter Typeclasses
quickSort :: [a] -> [a]
quickSort [] = []
quickSort (x:xs) = l ++ [x] ++ r
where
(l, r) = partition (< x) xs
a
must be comparableInt
, Char
, [Int]
are comparable.Int -> Int
, a -> Bool
are not comparable.Int
, Char
, [Int]
are instances of the typeclass Ord
quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = l ++ [x] ++ r
where
(l, r) = partition (< x) xs
typechecks!
newtype Polynomial = Poly [Int]
*Main> Poly [1,2,3]
:10:1:
No instance for (Show (Polynomial a0))
arising from a use of ‘print’
In the first argument of ‘print’, namely ‘it’
In a stmt of an interactive GHCi command: print it
need to make Polynomial
to a member of Show
newtype Polynomial = Poly [Int]
deriving Show
*Main> Poly [1,2,3]
Poly [1,2, 3]
works now.. but not so great
show
instance Show Polynomial where
show (Poly []) = "0"
show (Poly (x:xs))
= (show x) ++ " + " ++ (concat $ intersperse " + " terms)
where
terms
= map (\(a,b) -> (show a) ++ " x^" ++ (show b)) (zip xs [1..n])
n = length xs
*Main Data.List> Poly [1..5]
1 + 2 x^1 + 3 x^2 + 4 x^3 + 5 x^4
our pretty printing works now!
...make them a member of the typeclass Ord
instance Ord Polynomial where
(Poly xs) `compare` (Poly ys)
| length xs < length ys = LT
| length xs > length ys = GT
| head xs < head ys = LT
| head xs > head ys = GT
| otherwise = EQ
Prelude Data.List> :r
[1 of 1] Compiling Main ( randomStuff.hs, interpreted )
randomStuff.hs:20:10:
No instance for (Eq Polynomial)
arising from the superclasses of an instance declaration
In the instance declaration for ‘Ord Polynomial’
Failed, modules loaded: none.
Ord
class extends the class Eq
. Ord
typeclass looks something like this:
class (Eq a) => Ord a where
(<), (<=), (>=), (>) :: a -> a -> Bool
max, min :: a -> a -> a
Eq
are available as a part of the Ord
class.Ord
is a subclass of Eq
.
newtype Polynomial = Poly [Int]
deriving Eq
... and that fixes our code.
Enter Num
Typeclass
instance Num Polynomial where
(Poly fs) + (Poly []) = Poly fs
(Poly []) + (Poly gs) = Poly gs
(Poly (f:fs)) + (Poly (g:gs)) = Poly (f+g : rest)
where (Poly rest) = (Poly fs) + (Poly gs)
(Poly (f:fs)) * (Poly (g:gs)) = Poly (f*g : rest)
where (Poly rest) = (Poly [f])*(Poly gs) + (Poly fs)*(Poly (g:gs))
(Poly _) * (Poly _) = Poly []
fromInteger n = Poly [fromInteger n]
abs (Poly xs) = undefined --length xs
signum (Poly xs) = Poly (map signum xs)
negate (Poly xs) = Poly (map (\x -> -x) xs)
*Main> (Poly [1,4,5])+(Poly [1,2,1])
2 + 6 x^1 + 6 x^2
addition works!
*Main> (Poly [1,4,5])*(Poly [1,2,1])
1 + 6 x^1 + 14 x^2 + 14 x^3 + 5 x^4
... so does multiplication
*Main> (Poly [1,1])^5
1 + 5 x^1 + 10 x^2 + 10 x^3 + 5 x^4 + 1 x^5
exponentiation comes for free!
Num
typeclass supports (^)
but we do not need to define it manually.(-)
, as long as we have negate
, and vice-versa.
newtype Polynomial = Poly [Int]
deriving Eq
but why stick to Int
polynomials?
newtype Polynomial a = Poly [a]
deriving Eq
we now have polynomials on arbitrary values
instance Show (Polynomial a)
instance Ord (Polynomial a)
instance Num (Polynomial a)
But how do you show, compare, or add arbitrary types?!
instance Show a => Show (Polynomial a)
instance Ord a => Ord (Polynomial a)
instance Num a => Num (Polynomial a)
... type of types
Polynomial Int
is really a type. We can produce values which inhabit Polynomial Int
*Main> :t (Poly [1,2,3]) :: Polynomial Int
(Poly [1,2,3]) :: Polynomial Int :: Polynomial Int
Polynomial
is not really a concrete type. It is a type constructor.*
*Main> :k Polynomial Int
Polynomial Int :: *
* -> *
*Main> :k Polynomial
Polynomial :: * -> *
(->)
is?
*Main> :k (->)
(->) :: * -> * -> *
Constraint
kind
*Main> :k Ord
Ord :: * -> GHC.Prim.Constraint
meet Functor
*Main> :k Functor
Functor :: (* -> *) -> GHC.Prim.Constraint
fmap
instance Functor [] where
fmap = map
data Tree a = Leaf a | Fork (Tree a) (Tree a)
instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Fork l r) = Fork (fmap f l) (fmap f r)
Functor
laws
fmap id ≡ id -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law
Polynomial
an instance of Functor
too..
instance Functor Polynomial where
fmap f (Poly xs) = Poly (map f xs)
*Main> fmap (+1) (Poly [1,2,3])
2 + 3 x^1 + 4 x^2
data DX a = DX { val :: a, dx :: DX a }
instance Num n => Num (DX n) where
fromInteger x = DX (fromInteger x) 0
...notice the circularity in the definition here.
instance Num n => Num (DX n) where
fromInteger x = DX (fromInteger x) 0
DX x₀ x' + DX y₀ y' = DX (x₀ + y₀) (x' + y')
DX x₀ x' - DX y₀ y' = DX (x₀ - y₀) (x' - y')
x@(DX x₀ x') * y@(DX y₀ y') = DX (x₀ * y₀) (x * y' + y * x')
signum (DX x₀ x') = DX (signum x₀) 0
abs x@(DX x₀ x') = DX (abs x₀) (signum x * x')
instance Fractional n => Fractional (DX n) where
fromRational n = DX (fromRational n) 0
x@(DX x₀ x') / y@(DX y₀ y') =
DX (x₀ / y₀) ((x' * y - x * y') / y ^ 2)
instance Eq a => Eq (DX a) where
a == b = val a == val b
instance Ord a => Ord (DX a) where
compare a b = compare (val a) (val b)
instance Show a => Show (DX a) where
show (DX x (DX x' (DX x'' _))) = show [x, x', x'']
var x = DX x 1
*Main> (\ x -> 7*x^2 + 3*x + 2) (var 5)
[192,73,14]
mySqrt :: (Num a, Ord a, Fractional a) => a -> a -> a
mySqrt eps x = go 1
where
go guess
| abs (guess^2 - x) < eps = guess
| otherwise = go newGuess
where
newGuess = guess - (guess^2 - x)/(2*guess)
*Main> mySqrt 0.001 (var 2)
[1.4142156862745099,0.35356593617839294,-8.832952635110178e-2]
*Main> (1/(2*(sqrt 2)))
0.35355339059327373
eps
*Main> mySqrt 0.0000000000001 (var 2)
[1.4142135623730951,0.35355339059327373,-8.838834764831843e-2]
newtons eps f guess
| abs (f guess) < eps = guess
| otherwise = newtons eps f newGuess
where
newGuess = guess - (x/x')
(DX x (DX x' _)) = f (var guess)
What type is this?
newtons :: (Num a, Fractional a, Ord a) => a -> (a -> a) -> a -> a
randomStuff.hs:75:34:
Couldn't match expected type ‘a’ with actual type ‘DX a’
‘a’ is a rigid type variable bound by
the type signature for
newtons :: (Num a, Fractional a) => a -> (a -> a) -> a -> a
at randomStuff.hs:69:12
Relevant bindings include
guess :: a (bound at randomStuff.hs:70:15)
f :: a -> a (bound at randomStuff.hs:70:13)
eps :: a (bound at randomStuff.hs:70:9)
newtons :: a -> (a -> a) -> a -> a (bound at randomStuff.hs:70:1)
In the first argument of ‘f’, namely ‘(var guess)’
In the expression: f (var guess)
newtons :: (Num a, Ord a, Fractional a) => a -> (DX a -> DX a) -> a -> a
...doesn't work either
newtons eps f guess
| abs (f guess) < eps = guess
| otherwise = newtons eps f newGuess
where
newGuess = guess - (x/x')
(DX x (DX x' _)) = f (var guess)
f
should not only behave as a -> a
but also DX a -> DX a
newtons
is not just polymorphic, but it also wants a polymorphic function as an argumentRank2Types
{-# LANGUAGE Rank2Types #-}
newtons :: (Num a, Ord a, Fractional a) => a -> (forall b. (Num b, Ord b, Fractional b) => b -> b) -> a -> a
...typechecks!
*Main> newtons 0.0000001 (\x -> x^2 - 2) 1
1.4142135623746899
data Op = Plus | Minus | Times | Divide deriving Eq
data Sym a = Lit a
| Var String
| Expr Op (Sym a) (Sym a) deriving Eq
instance Num a => Num (Sym a) where
fromInteger = Lit . fromInteger
(+) = Expr Plus
(-) = Expr Minus
(*) = Expr Times
instance Fractional a => Fractional (Sym a) where
fromRational = Lit . fromRational
(/) = Expr Divide
instance Show Op where
show Plus = "+"
show Minus = "-"
show Divide = "/"
show Times = "*"
instance Show a => Show (Sym a) where
show (Var x) = x
show (Lit n) = show n
show (Expr op e1 e2) = "(" ++ (show e1) ++ ")" ++ show op ++ "(" ++ (show e2) ++ ")"
*Main> val . dx $ (\x -> (x^2 + 2*x + 7)) (var (Var "x"))
((((x)*(1))+((x)*(1)))+(((2)*(1))+((x)*(0))))+(0)
...really need some simplification!
step :: (Eq a, Num a, Fractional a) => Sym a -> Sym a
step (Expr op (Lit n₁) (Lit n₂)) =
Lit $ (case op of Plus -> (+); Minus -> (-); Times -> (*); Divide -> (/)) n₁ n₂
step (Expr Plus
(Expr Times (Lit n₁) (Var x))
(Expr Times (Lit n₂) (Var y)))
| x == y = Expr Times (Expr Plus (Lit n₁) (Lit n₂)) (Var x)
step (Expr Plus (Var x) (Var y))
| x == y = Expr Times (Lit 2) (Var x)
step (Expr Plus 0 n) = n
step (Expr Plus n 0) = n
step (Expr Times 1 n) = n
step (Expr Times n 1) = n
step (Expr Times 0 n) = 0
step (Expr Times n 0) = 0
step (Expr op e₁ e₂) = Expr op (step e₁) (step e₂)
step (atom) = atom
simplify = until . iterate step
where until (x₁ : x₂ : xs) | x₁ == x₂ = x₁
| otherwise = until (x₂ : xs)
*Main> simplify . val . dx $ (\x -> (x^2 + 2*x + 7)) (var (Var "x"))
((2.0)*(x))+(2.0)
not so bad now!
*Main> simplify . val . dx $ (\x -> (1/x)) (var (Var "x"))
(-1.0)/((x)*(x))