Unit Testing & Propoerty Testing
Propety tests test the formal propoerties of programs.
In Haskell, we recognize abstract pattern in code which have well-defined, lawful representation in math. These abstractions is described as algebra, by which we mean operations and the set(the type they operate on) they operate over.
The stude of mathematical symbols and the rules govening their manipulation. It differ from arithmetic by its use of abstractions such as variables. By use of variables, we care about the rule of how to manipulate this thing without reference to its particular value. In Haskell, these algebras can be implemented with type-classes. the typeclasses define the set of operations. The instance defines how each operation will perform for a given type or set. Algebras are defined by their laws and are useful principally for their laws. Laws make up what algebras are.
A common algebra. Math: A monoid is binary associative operation with an identity. Eng: A monoid is a function that take two arguments and follows two laws: associativity and identity. Urban: Smashing two values of same type together.
class Monoid m where
mempty ::m
mappend :: m -> m -> m
mconcat :: [m] -> m
mconcate = foldr mappend mempty
Integers form a monoid under summation and multiplication. Intead of using scope tricks and abide by the rule that type-class instance are unique they are for, we use newtype to seprate the different monoidal behaviors.
data Server = Server String
newtype Server' = Server' String
The main difference are that using newtype constrains the datatype to having a single unary data constructor and newtype guarantee no additional runtime overhead in wrapping the original type. i.e. the runtime representation of newtype and what it wraps are always identical - no additional "boxing up" of the data is necessary for typical products and sums.
newtype is like a single-member C union that avoid creating an extra pointer, but still give you a new type constructor and data constructor so you don't mix up the many many many things that share a single representation.
Why use newtype
- Signal Intent. it's clear that you only intend for it to be a wrapper for the underlying type. The newtype cannot eventually grow into a more complicated sum or product type.
- Improve type safety: avoid mixing up many value of the same representation, such as Text or Integer
- Add different typeclasss instance to a type that is otherwise unchanged representationally, suchas as Sum and Product.
import Data.Monoid
:info Sum
# newtype Sum a = Sum {getSum:: a}
# instance Num a => Monoid (Sum a)
:info Product
# newtype Product a = Product {getProduct:: a}
# instance Num a => Monoid (Product a)
helloMe :: CoolBool -> String
helloMe (CoolBool _) = "hello"
newtype CoolBool = CoolBool { getCoolBool :: Bool }
helloMe undefined -- "hello" why is that? Well, like we've said, when we use newtype, Haskell can internally represent the values of the new type in the same way as the original values. It doesn't have to add another box around them, it just has to be aware of the values being of different types. And because Haskell knows that types made with the newtype keyword can only have one constructor, it doesn't have to evaluate the value passed to the function to make sure that it conforms to the (CoolBool _) pattern because newtype types can only have one possible value constructor and one field!
Whereas data can be used to make your own types from scratch, newtype is for making a completely new type out of an existing type. Pattern matching on newtype values isn't like taking something out of a box (like it is with data), it's more about making a direct conversion from one type to another.
(<>) :: Monoid m => m -> m -> m #infix operator for mappend
Proofs are programs, and programs are proofs. We care about programs that compose well, that are easy to understand, and which have predictable behavior. Algebras are defined by their laws and are useful principally for their laws. Laws make up what algebras are.
Monoid instance must abide by the following laws:
-- left identity
mappend mempty x = x
-- right identity
mappend s mempty = x
-- associativity
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
Mappending is best thought of a way to condense any set of values to a summary value. Monoid instance of Bool: Two possible monoids. a monoid of conjunction and one of disjunction.
All True <> All False # All {getAll = False}
Any True <> All False # All {getAny = True}
class Semigroup
Functor is all about a pattern of mapping over structure. Functor is combinator for function application over some structure we don't want to have to think about.
Combinator
- A function or definition with no free variables.
Functor is a way to apply a function over or around some structure that we don't want to alter.
class Functor f where
fmap :: (a -> b) -> f a -> f b
-- f must have the kind * -> *(higher-kinded type that's awaited for application to a type constand of kind *
(.) :: (b -> c) -> (a -> b) -> a -> c
fmap :: Functor f => (m -> n) -> f m -> f n
fmap :: Functor g => (x -> y) -> g x -> g y
(.) fmap :: Functor f => (a -> m -> n) -> a -> f m -> f n
fmap . fmap :: Functor f, Functor g => a -> f g m -> f g nNatural Transformation transforming the structure and preserve the values as they were
nat :: (f -> g) -> f a -> g a -- it wont' compile cause higher-kinded types can't be argument type to the function type
:set -XRank2Types
type Nat f g = forall a. f a -> g a
-- This'll work
maybeToList :: Nat Maybe []
maybeToList Nothing = []
maybeToList (Just a) = [a]
-- This will not work, not allowed.
degenerateMtl :: Nat Maybe []
degenerateMtl Nothing = []
degenerateMtl (Just a) = [a+1]
-- natural transformations we’re saying as much about what we don’t want as we are about what we do want. In this case, the ---- invariant we want to preserve is that the function cannot do anything mischievous with the values. If you want something ---- clever, just write a plain old fold!fmap :: Functor f => (a -> b) -> f a -> f b
The maximally polymorphic version of this is: (a -> b) -> a -> b
So in fact, not having a type argument means this is just: ($) :: (a -> b) -> a -> b
We just saw how trying to make a Functor instance for a type constant means you just have function application. But, in fact, fmap is a specific sort of function application. Let’s look at the types: fmap ::Functorf=>(a->b)->fa->fb
So it means the only functor instance can be made for all type constant is to set fmap as $fmap
(<$>)::Functorf=>(a->b) ->fa->fb # infix version of fmap ($) :: (a->b) -> a -> b
newtype Constant a b =
Constant [ getConstant :: a}
deriving (Eq, Show)
the type parameter b is a phantom type. It has no corresponding witness at the value/term level.
instance Functor (Constant m) where
fmap _ (Constant v) = Constant v
Its abstract datatype. There are no data constructors that you're permitted to pattern m
A functor is a type of mapping between categories. Functor can be thought of as homomorphisms between categories. Homomorphism is a structure-preserving map between two algebraic categories of the same type
It gives us a means of expression indefinite or incremental computation without forcing us to explicitly repeat ourselves and allowing the data we are processing to decide when we are done computing
Lambda calculus does not appea on the surface to have any means of recursion, because of the anonymity of expressions. Being able to write recursive functoins, though, is essential to Turing completeness. We use a combinator - known as the Y combinator or fixed-point combinator - to write recursive functions in the lambda calculus.
Recursion vs Composition(HOC) indefinite - staic & defnite The difference is that instead of a fixed number of applications, recursive functions rely on inputs to determine when to stop applying functions to successive results
Bottom ⊥ or bottom is a term used in Haskell to refer to computations that do not successfully result in a value The two main varieties of bottom are computations that failed with an error or those that failed to terminate.
dividedBy :: Integral a => a -> a -> (a, a) dividedBy num denom = go num denom 0
where go n d count
| n < d = (count, n)
| otherwise = go (n - d) d (count + 1)
The key concept here is purity: a pure function is a function with no side effects and no state. Functional programming languages generally embrace purity for many reasons, such as reasoning about code and avoiding non-obvious dependencies. Some languages, most notably Haskell, even go so far as to allow only pure code; any side effects a program may have (such as performing I/O) are moved to a non-pure runtime, keeping the language itself pure.
Inefficient in imperative lang. But it pure FP, it can be optimized by compiler aggresively.(e.g tail call optimization, lazy Evaluation (recursive data structure, recursive method)
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)
data # create new type
newtype # create a wrapper
type # create alias
Applicative is a monoidal functor. Applicative typeclass allows for function application lifted over structure(like Functor). But with Applicative the function we're applying is also embedded in some structure. We smasth the function stucture and value's structure together.
pure is all about putting a value in a minimal computational context that still hold it
as its result.
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b # called apply or ap
fmap :: (a->b)->fa->fb
(<*>)::f(a->b)->fa->fb
fmap f x = pure f <*> x
($) :: (a -> b) -> a -> b
(<$>) :: (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b
<$> we are lifting (a -> b) over the f wrapped around value and applying function to that value
<*> our function is now also embedded in the functorial structure.
We call it monoidal because
f (a -> b)
-- and
f a
We saparate the structure part from the function parts.
f f f
(a -> b) a b
mappend :: f f f
$ :: (a -> b) a b
(<*>) :: f (a -> b) -> fa -> fb
-- List
[(*2), (*3)] <*> [4, 5] -- [2*4,2*5,3*4,3*5]
-- Maybe
Just (*2) <*> Just 2 = Just 4
Just (*2) <*> Nothing = Nothing
Nothing <*> Just 2 = Nothing
Nothing <*> Nothing = Nothing
With Maybe, the ordinary functor is mapping over the possibility of value's nonexistence. With Applicative, the functoin also might not be provied.
(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: [(a -> b)] -> [a] -> [b]
pure :: a -> f a
pure :: a -> [a]
With List Functor, we are mapping a single function over values With List Applicative, we are mapping functions over values It maps each function value from the first list over the second list and so on. The fact that it doesn't return nested list is monoidal part.
(,) <$> [1, 2] <*> [3, 4] -- [(1,3),(1,4),(2,3),(2,4)]
liftA2 (,) [1, 2] [3, 4]
(++) <$> getLine <*> getLine
(,) <$> getLine <*> getLine
(<*>) :: f (a -> b) -> f a -> f b
(<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
pure :: a -> f a
pure :: a -> Maybe a
-- e.g
data Cow = Cow {
name :: String
, age :: Int
, weight :: Int
} deriving (Eq, Show)
noEmpty :: String -> Maybe String
noEmpty "" = Nothing
noEmpty str = Just str
noNegative :: Int -> Maybe Int
noNegative n | n >= 0 = Just n
| otherwise = Nothing
-- this look shit
cowFromString :: String -> Int -> Int -> Maybe Cow
cowFromString name' age' weight' =
case noEmpty name' of
Nothing -> Nothing
Just nammy ->
case noNegative age' of
Nothing -> Nothing
Just agey ->
case noNegative weight' of
Nothing -> Nothing
Just weighty ->
Just (Cow nammy agey weighty)
-- better one using applicative
cowFromString' :: String -> Int -> Int -> Maybe Cow
cowFromString' name' age' weight' =
Cow <$> noEmpty name'
<*> noNegative age'
<*> noNegative weight'
-- even better one
cowFromString'' :: String -> Int -> Int -> Maybe Cow
cowFromString'' name' age' weight' =
liftA3 Cow (noEmpty name')
(noNegative age')
(noNegative weight')
So applicative is really just a way of saying:
we fmap my function over some functorial f
Scenario: I want to do something like an fmap but my function is embedded in the functorial structure,
not just the value I want to apply my function to.
With Maybe, it's like how we handle when we want to do function application on both function or value might
not exist at all.
instance Applicative ((->) r) where
pure x = (\_ -> x)
f <*> g = \x -> f x (g x)pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
The result of composing our functions first and then applying them and the result of applying the functions first and then composing them should be the same.
pure (.) <*> [(+1)] <*> [(*2)] <*> [1, 2, 3]
[(+1)] <*> [(*2)] <*> [1, 2, 3]
A homomorphism is a structure-preserving map between two algebraic structures. Applying the function doesn't change the structure around the values.
pure f <*> pure x = pure (f x)
Because the "structure" that pure is providing there isn't really meaningful. Applicative is also function application that preserves structure. However, with applicative, since the function being applied also has structure, the structures have to be monoidal and com together in some fashion.
u <*> pure y = pure ($ y) <*> u
-- e.g.
(Just (+2) <*> pure 2) == pure ($ 2)
$ y created an environment in which the y is there, awaiting a function to apply to it.
It scales up to functions with any number of arguments
Monads are applicative functors with some unique features that make them powerful than <*>
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :; a -> m aBecasue Applicative is superclass of Monad, Functor is superclass of Applicative we can derive Applicative and Functor in terms of Monad. Chaing of Dependency Functor -> Applicative -> Monad
-- example
fmap f xs = xs >>= return . freturn basically just like pure in Applicative Functor
>> basically sequence two actions while discarding any resulting value of
the first action.
>>= it's called bind.
fmap :: Functor f => (a -> b) -> f a -> f b
<*> :: Applicative f => f (a -> b) -> f a -> f b
>>= :: Monad f => f a -> (a -> f b) -> f b-
Impure. Monadic functions are functions. IO is an abstract datatype that allows for impure, or effectful, actions, and it has a Monad instance. But there's nothing impure about monads.
-
And Embedded language for imperative programming. While monads are often used for sequnecing actions in a way that look like imperative programming., there are commutative monads that do no order actions. e.g Reader
-
A Value. The typeclass describe a specific relationship between elements in a domain and defines some operations over them. not a value
-
About strictness. The monadic operations of bind and return are nonstrict. Some operation can be made strict withing a specific instance.
liftA :: Applicative f => (a -> b) -> f a -> f b
liftM :: Monad m => (a1 -> r) -> m a1 -> m r(*>) :: Applicative f => f a -> f b -> fb (>>) :: Monad m => m a -> m b -> m b
import Control.Monad (join)
:t putStrLn <$> getLine -- IO(IO ())
:t join $ putStrLn <$> getLine -- IO()This merged IO acion performs the effect in the "order" determined by the nesting of the IO actions. The cleanest way to express "ordering" in a lambda calculus is through nesting of expressions or lambdas
- Identity Laws
-- right identity
m >>= return = m
-- left identity
return x >>= f = f xSo these two laws imply return should nbe neutral and not perform any computation.
- Associativity
(m >>= f) >>= g = m >>= (\x -> f x >>= g)mcomp f g a = g a >>= f
(.) :: (b -> c) -> (a -> b) -> a -> c
(>>=) :: Monad m => m a -> (a -> m b) -> m b
import Control.Monad
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
flip (.) :: (a -> b) -> (b -> c) -> a -> c
Applicative functors allow you to take a "normal" function (taking non-functorial arguments) use it to operate on several values that are in functor contexts. As a corollary, this gives you effectful programming without monads.
When are they useful? A common example is parsing, where you need to run a number of actions that read parts of a data structure in order, then glue all the results together. This is like a general form of function composition:
f a b c df <$> a <*> b <*> c <*> dMonad more expressive. It can dpend on earlier results while applicative can't
do bool <- parseBool
if bool then parseStr
else parseNumSince the structure of the applicative doesn't depend in intermediate results, it makes the whole thing easier to parallelize.