031 - Tea & FP: Monoids, Monoids Everywhere!


#1

Salutare! Pentru că tema întâlnirii de diseară sunt monoizii am pregătit câteva puzzle-uri despre acest subiect; iar dacă vi se par interesante le putem discuta când ne vedem.


Definition (monoid). A monoid consists of:

  1. a set M
  2. a binary operation · : M × M → M
  3. an element e ∈ M

such that

  1. the binary operation is associative, that is, x · (y · z) = (x · y) · z, ∀ x, y, z ∈ M
  2. the element e is identity: x · e = x = e · x, ∀ x ∈ M.

Definition (monoid homomorphism). A homomorphism between two monoids (M, ·, e) and (N, *, 1) is a function h : M → N such that

  1. h(x · y) = h(x) * h(y) for all x, y ∈ M
  2. h(e) = 1

Puzzle 1. Why does the definition of homomorphism require the second condition? If we let either y = e or x = e in the first condition, we see that h(e) behaves like the identity on N:

h(x) = h(x · e) = h(x) * h(e)                              
h(y) = h(e · y) = h(e) * h(y)

Construction (monoid of endomorphisms). For every set M we may construct the monoid of endomorphisms (M → M, ○, id), where denotes function composition and id is the identity function.

Puzzle 2. Show that the monoid of endomorphisms is indeed a monoid.

Definition (sub-monoid). A set N is a sub-monoid of a monoid (M, ·, e) if there exists an injection i : N → M such that

  1. i(1) = e for some 1 ∈ N
  2. i(x * y) = i(x) · i(y) for some * : N × N → N.

Puzzle 3. Show that if N is a sub-monoid then the existence of i makes (N, *, 1) a monoid and i a monoid homomorphism.

Theorem (Cayley’s theorem for monoids). Every monoid (M, ·, e) is a sub-monoid of the monoid of endo-morphisms on M.

Puzzle 4. Prove Cayley’s theorem for monoids. Hint: Come up with a function rep :: Monoid m => m -> (m -> m) and show that (i) it is a homomorphism and (ii) it is an injection.

Puzzle 5. Apply Cayles’s theorem for lists. This representation gives the difference (or Hughes) lists. Why is this representation more efficient for appending lists than the standard representation?


#2

Am pomenit aseară la meetup despre un exercițiu marcat ca “hard” în Functional Programming in Scala, care sună în felul următor:

Exercise 10.9 Hard: Use foldMap to detect whether a given IndexedSeq[Int] is ordered. You’ll need to come up with a creative Monoid.

Exercițiul ăsta e legat de un altul precedent:

Exercise 10.7. Implement foldMap for IndexedSeq (recall that IndexedSeq is the interface for immutable data structures supporting efficient random access. It also has efficient splitAt and length methods). Your implementation should use the strategy of splitting the sequence in two, recursively processing each half, and then adding the answers together with the monoid.

def foldMap[A, B](v: IndexedSeq[A], m: Monoid[B])(f: A => B): B

#3

Mulțumim @igstan! IndexedSeq corespunde unui type class în Haskell? Cum ar arăta o instanță de IndexedSeq? Edit: De fapt, ai putea rescrie cerința în Haskell? :stuck_out_tongue:


#4

Nu știu dacă corespunde chiar unui typeclass. Oricum, poți ignora partea cu IndexedSeq. Gândește-te că trebuie să faci pentru lista standard din Haskell, doar că nu poți face presupuneri legate de ordinea de traversare pe care foldMap o folosește (face split și join la listă după cum vrea).


#5

Exercise 10.9 Poate ceva de genul acesta, dar nu arată foarte elegant…

{-# LANGUAGE GeneralizedNewtypeDeriving #-}                

import Data.Semigroup        

data S = NotSorted           
       | Sorted Int Int      
    deriving (Show, Eq)      

instance Semigroup S where   
    (Sorted x y) <> (Sorted x' y') | x <= y && y <= x' && x' <= y' = Sorted x y'                                      
                                   | otherwise                     = NotSorted                                        
    _ <> _ = NotSorted       

newtype SOption = SOption (Option S)                       
    deriving (Semigroup, Monoid, Show, Eq)     

Dacă fac foldMap pe listă aș obține ceva de genul acesta (cred că s-ar comporta similar și pe IndexedSeq):

*Main> foldMap (\ a -> SOption (Option (Just (Sorted a a)))) [1,2,3,4]
SOption (Option {getOption = Just (Sorted 1 4)})    
*Main> foldMap (\ a -> SOption (Option (Just (Sorted a a)))) [1,2,3,4,3,2,1]                                          
SOption (Option {getOption = Just NotSorted})              

@igstan Tu cum ai rezolvat?


#6

O nouă încercare în care am vrut să mă bazez cât mai mult pe structurile definite în Data.Semigroup:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}                

import Data.Semigroup        

newtype Union a = Union { getUnion :: (Min a, Max a) }     
    deriving (Show, Eq, Semigroup)                         

getMinUnion :: Union a -> a  
getMinUnion = getMin . fst . getUnion                      

getMaxUnion :: Union a -> a  
getMaxUnion = getMax . snd . getUnion                      

data S = I | U (Union Int)   
    deriving (Show, Eq)      

instance Semigroup S where   
    (U u1) <> (U u2) | getMaxUnion u1 <= getMinUnion u2 = U (u1 <> u2)                                                
                     | otherwise                        = I                                                           
    _      <> _      = I     

newtype M = M (Option S)     
    deriving (Show, Eq, Semigroup, Monoid)                 

ap :: (a -> b, a -> c) -> a -> (b, c)                      
ap (f, g) x = (f x, g x)     

wrap :: Int -> M             
wrap = M . Option . Just . U . Union . ap (Min, Max)    

Și exemplu de utilizare:

*Main> foldMap wrap [1,2,3,4]
M (Option {getOption = Just (U (Union {getUnion = (Min {getMin = 1},Max {getMax = 4})}))})

Câteva întrebări:

  • Funcția pe care am numit-o ap există deja sau ar putea fi rescrisă altfel?
  • Există un mod mai elegant de lucra cu wrap-erele în care am ascuns datele?
  • Cum pot face syntax highlighting la cod pe acest forum?