Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Composition in FP

Composition in FP

Bucharest FP

August 20, 2018
Tweet

More Decks by Bucharest FP

Other Decks in Programming

Transcript

  1. What Is Composition? Composition is essential in functional programming. We

    use mathematical abstractions (such as Semigroup and Monoid) to define the composition of a wide variety of data types. Short recap: • Sets, e.g., B = { , ⊥}, N = {0, 1, 2, . . .}, T = {Void, (), Bool, Int, ((), Bool), [(Int, Bool)], . . .} • Operations, e.g., there are four unary operations on Bool (const , const ⊥, identity and not) • Associativity, e.g., (a ∨ b) ∨ c = a ∨ (b ∨ c) • Commutativity, e.g., a ∨ b = b ∨ a 2
  2. Semigroup A semigroup is an algebraic structure consisting of a

    set and an associative binary operation. Given a set S and an operation +, then: ∀ a, b ∈ S, ∃ c ∈ S, a + b = c ∀ a, b, c ∈ S, (a + b) + c = a + (b + c) Examples of semigroups: concatenation on (non-empty) lists, addition and multiplication of numbers, conjunction and disjunction of booleans, appending parts in a path or chunks of a file, combining IO actions, etc. 3
  3. Monoid A monoid is an algebraic structure consisting of a

    set, an associative binary operation, and an identity element. Given a set S, an operation +, and the identity element e, then: ∀ a, b ∈ S, ∃ c ∈ S, a + b = c ∀ a, b, c ∈ S, (a + b) + c = a + (b + c) ∀ a ∈ S, e + a = a + e = a Examples of monoids: concatenation on (possibly empty) lists, addition and multiplication on numbers, conjunction and disjunction on booleans, appending parts in a path or chunks of a file, combining IO actions, etc. 4
  4. Semiring 1/2 A semiring is an algebraic structure consisting of

    a set S, a commutative monoid (S, +, 0) and monoid (S, ∗, 1), such that ∗ distributes over + and 0 annihilates ∗. So, given a set S, and two operations + and ∗, and the identity elements 0 and 1, we can say: 5
  5. Semiring 2/2 ∀ a, b ∈ S, ∃ c ∈

    S, a + b = c ∀ a, b, c ∈ S, (a + b) + c = a + (b + c) ∀ a ∈ S, 0 + a = a + 0 = a ∀ a, b ∈ S, a + b = b + a ∀ a, b ∈ S, ∃ c ∈ S, a ∗ b = c ∀ a, b, c ∈ S, (a ∗ b) ∗ c = a ∗ (b ∗ c) ∀ a ∈ S, 1 ∗ a = a ∗ 1 = a ∀ a, b, c ∈ S, a ∗ (b + c) = (a ∗ b) + (a ∗ c) ∀ a, b, c ∈ S, (a + b) ∗ c = (a ∗ c) + (b ∗ c) ∀ a ∈ S, a ∗ 0 = 0 ∗ a = 0 6
  6. Semiring Example: Bool ∀ a, b ∈ B, ∃ c

    ∈ B, a ∨ b = c ∀ a, b, c ∈ B, (a ∨ b) ∨ c = a ∨ (b ∨ c) ∀ a ∈ B, ⊥ ∨ a = a ∨ ⊥ = a ∀ a, b ∈ B, a ∨ b = b ∨ a ∀ a, b ∈ B, ∃ c ∈ B, a ∧ b = c ∀ a, b, c ∈ B, (a ∧ b) ∧ c = a ∧ (b ∧ c) ∀ a ∈ B, ∧ a = a ∧ = a ∀ a, b, c ∈ B, a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) ∀ a, b, c ∈ B, (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c) ∀ a ∈ B, a ∧ ⊥ = ⊥ ∧ a = ⊥ 7
  7. Semiring Example: Types ∀ a, b ∈ T, ∃ c

    ∈ T, Either a b ∼ = c ∀ a, b, c ∈ T, Either (Either a b) c ∼ = Either a (Either b c) ∀ a ∈ T, Either Void a ∼ = Either a Void ∼ = a ∀ a, b ∈ T, Either a b ∼ = Either b a ∀ a, b ∈ T, ∃ c ∈ T, (a, b) ∼ = c ∀ a, b, c ∈ T, ((a, b), c) ∼ = (a, (b, c)) ∀ a ∈ T, ((), a) ∼ = (a, ()) ∼ = a ∀ a, b, c ∈ T, (a, Either b c) ∼ = Either (a, b) (a, c) ∀ a, b, c ∈ T, ((Either a b), c) ∼ = Either (a, c) (b, c) ∀ a ∈ T, (a, Void) ∼ = (Void, a) ∼ = Void 8
  8. Monoid in Haskell 1 class Semigroup a where 2 (<>)

    :: a -> a -> a 3 4 5 class Semigroup a => Monoid a where 6 mempty :: a 7 8 9 instance Semigroup [a] where 10 a <> b = a ++ b 11 12 13 instance Monoid [a] where 14 mempty = [] 9
  9. Monoid Usage 1 λ> "foo" <> "bar" 2 "foobar" 3

    4 fold :: (Foldable t, Monoid m) => t m -> m 5 λ> fold ["fo", "o", "bar"] 6 "foobar" 7 8 foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m 9 λ> foldMap Sum [1,2,3,4,5] 10 Sum {getSum = 15} 11 12 λ> foldMap All [True, True, True] 13 All {getAll = True} 14 15 λ> foldMap All [True, True, False] 16 All {getAll = False} 10
  10. Monad When viewed from the perspective of composability, monads allow

    us to compose things that are not obtained independently, but rather in a more sequential manner. 1 conn <- getSqlConnection 2 someData <- runSomeSelectQuery conn 3 writeToDisk someData 4 5 -- or: 6 getSqlConnection 7 >>= runSomeSelectQuery 8 >>= writeToDisk 12
  11. Just a Monoid in the... 1 -- These two functions

    are equivalent: 2 (>>=) :: m a -> (a -> m b) -> m b 3 join :: m (m a) -> m a 4 5 -- Forward 6 ma >>= mab = join (mab <$> ma) 7 -- Backward 8 join mma = mma >>= id Any Monad is a Monoid. The easiest way to look at it is by looking at the join operation, which takes two m’s and returns a single m, or combines two m’s into a single one. See @KenScambler’s excellent tweets about this at https://twitter.com/KenScambler/status/956111889519357952 13
  12. Applicative 1 class Functor f where 2 (<$>) :: (a

    -> b) -> f a -> f b 3 4 class Functor f => Applicative f where 5 (<*>) :: f (a -> b) -> f a -> f b 6 pure :: a -> f a 7 8 -- Applicative should really be like this. 9 class Functor f => Apply f where 10 (<*>) :: f (a -> b) -> f a -> f b 11 12 class Apply f => Applicative f where 13 pure :: a -> f a 14
  13. Applicative Example 1 op :: A -> B -> C

    2 a :: A 3 b :: B 4 5 op a b :: C 6 7 fa :: f A 8 fb :: f B 9 10 op <$> fa <*> fb :: f C 11 12 λ> (+) <$> Just 1 <*> Just 2 13 Just 3 14 15 λ> (+) <$> Just 1 <*> Nothing 16 Nothing 15
  14. Is this a semigroup / monoid? 1 class Functor f

    => TupleSemigroup f where 2 (<>) :: f a -> f b -> f (a, b) 3 4 class TupleSemigroup f => TupleMonoid f where 5 mempty :: f () The answer is, yes, if we alter the rules a bit to say that the operation is associative up to isomorphism (and that using the identity element results in isomorphic structures). The claim is these classes are equivalent to Apply and Applicative. How do we prove it? By implementing these in terms of Apply and Applicative, and then implementing Apply/Applicative in terms of these clases. 16
  15. Equivalence 1 -- Applicative -> Tuple* 2 instance Apply f

    => TupleSemigroup f where 3 (<>) :: f a -> f b -> f (a, b) 4 fa <> fb = (,) <$> fa <*> fb 5 6 instance Applicative f => TupleMonoid where 7 mempty :: f () 8 mempty = pure () 9 10 -- Tuple* -> Applicative 11 instance TupleSemigroup f => Apply f where 12 (<*>) :: f (a -> b) -> f a -> f b 13 fa2b <*> fa = (\(a2b, a) -> a2b a) <$> (fa2b <> fa) 14 15 instance TupleMonoid f => Applicative f where 16 pure :: a -> f a 17 pure a = const a <$> mempty 17
  16. Wait, is TupleMonoid really a Monoid? ∀ fa, fb ∈

    T, ∃ fc ∈ T, fa <> fb ∼ = fc ∼ = f(a, b) ∀ fa, fb, fc ∈ T, (fa <> fb) <> fc ∼ = fa <> (fb <> fc) f(a, b) <> fc ∼ = fa <> f(b, c) f((a, b), c) ∼ = f(a, (b, c)) ∀ fa ∈ T, mempty <> fa ∼ = fa <> mempty ∼ = fa () <> fa ∼ = fa <> () ∼ = fa f(a, ()) ∼ = f((), a) ∼ = fa 18
  17. Alternative 1 -- Semigroup 2 class Functor f => Alt

    f where 3 (<|>) :: f a -> f a -> f a 4 5 -- Monoid 6 class Alt f => class Plus f where 7 empty :: f a 8 9 -- Near Semiring-ish 10 class Applicative f, Plus f => Alternative f 11 12 -- Alternative guarantees the following laws: 13 (f <|> g) <*> x == (f <*> x) <|> (g <*> x) 14 empty <*> f == empty 19
  18. Applicative Semiring Example 1 λ> ([(+1), (+2)] <|> [(+3), (+4)])

    <*> [1,2] 2 [2,3,3,4,4,5,5,6] 3 4 λ> ([(+1), (+2)] <*> [1,2]) <|> ([(+3), (+4)] <*> [1, 2]) 5 [2,3,3,4,4,5,5,6] 6 7 λ> [(+1), (+2)] <*> empty 8 [] 20
  19. Alternative Intuition To get some intuition, we can think of:

    • <*> as: multiplication, conjunction, or carthesian product • pure as: 1, True, or the unit set • <|> as: addition, disjunction, or concatenation • empty as: 0, False, or the empty set In a way, Applicative is a higher kinded monoid, and Alternative is a higher kinded semiring (except it’s not commutative in Plus). 21