Thursday 2 June 2016

Haskell: monoids

Before going to explain about, let me brief you about function composition.

Combining functions by passing output of one function as input to other function is called composition of functions.

For example,
Let g(x) = 2x, f(x) = x + 1
then
f(g(x)) = f(2x) = 2x + 1

g(f(x)) = g(x+1) = 2 (x+1) = 2x + 2
Prelude> let g x = 2 * x
Prelude> let f x = x + 1
Prelude> 
Prelude> f(g 10)
21
Prelude> g(f 10)
22

What is the use of function composition?
By using function composition, you can build complex functions from simple functions. It makes your code more readable.

For example, following ListUtil.hs provide functions to make string upper, lower and trim spaces at front, back of string. By using these let me show you how can I solve complex expressions.


StringUtil.hs
import Data.Char

stringToUpper :: String -> String
stringToUpper [] = []
stringToUpper (x:xs) =  (toUpper x) : stringToUpper xs

stringToLower :: String -> String
stringToLower [] = []
stringToLower (x:xs) =  (toUpper x) : stringToLower xs

trimFrontSpaces :: String -> String
trimFrontSpaces [] = []
trimFrontSpaces res@(x:xs) = if x == ' ' then trimFrontSpaces xs else res

trimBackSpaces :: String -> String
trimBackSpaces xs = reverse ((trimFrontSpaces (reverse xs)))


1. Trim the spaces of a string
*Main> (trimFrontSpaces (trimBackSpaces "    abcdef   "))
"abcdef"


2. Convert string to upper case by removing spaces.
*Main> stringToUpper (trimFrontSpaces (trimBackSpaces "    abcdef   "))
"ABCDEF"
*Main> 
*Main> stringToUpper (trimFrontSpaces (trimBackSpaces "    abcdesdsf   "))
"ABCDESDSF"


3. get the length of a string after removing spaces.
*Main> length((trimFrontSpaces (trimBackSpaces "    abcdef   ")))
6
*Main> 
*Main> length(trimFrontSpaces (trimBackSpaces "    abcdesdsf   "))
9


One advantage of function composition is you can define new functions from existing functions.

We can define trim function like below.
let trim = trimFrontSpaces.trimBackSpaces

We can solve the problem 2, by defining the function like below.
let toUpperTrim = stringToUpper.trim
*Main> let trim = trimFrontSpaces.trimBackSpaces
*Main> let toUpperTrim = stringToUpper.trim
*Main> 
*Main> trim "    abcdef   "
"abcdef"
*Main> 
*Main> trim  "    abcdesdsf   "
"abcdesdsf"
*Main> 
*Main> toUpperTrim "    abcdef   "
"ABCDEF"
*Main> 
*Main> toUpperTrim "    abcdesdsf   "
"ABCDESDSF"
*Main> 


Function composition is associative
The composition of functions is always associative. That is, if f, g, and h are three functions with suitably chosen domains and codomains, then f (gh) = (fg) h, where the parentheses serve to indicate that composition is to be performed first for the parenthesized functions.

What is monoid?
A Monoid is a collection of things plus a rule to combine the things.

What are the rules
In any monoid
a.   (x combineWith y) combineWith z = x xombineWith (y combineWith z), this meta rule is called associativity.
b.   The monoid should contain ‘s’, a special member such that
1.    (x combinesWith s) = x.
2.   (s combinesWith x) = x

A monoid operation no need to satisfy commutative property.
(x combinesWith y) /= (y combinesWith x)               

(/= stands for not equal to)

What are the operation in Haskell that are associative and has an identity element?
Operations like Addition, multiplication are associative and has an identity element.
Prelude> 10 + (20 + 30)
60
Prelude> 
Prelude> (10 + 20) + 30
60
Prelude> 
Prelude> 10 + 0 
10
Prelude> 0 + 10
10


There are many operations in Haskell which are associative and has an identity element, for example ++, which appends lists is associative and has identity element.
Prelude> "Welcome" ++ (" to" ++ " Haskell") 
"Welcome to Haskell"
Prelude> 
Prelude> ("Welcome" ++ " to") ++ " Haskell" 
"Welcome to Haskell"
Prelude> 
Prelude> "Welcome" ++ ""
"Welcome"
Prelude> 
Prelude> "" ++ "Welcome"
"Welcome"
Prelude> 


Whatever I mentioed +, *, ++ are all examples of Monoids.

Monoid class
Haskel provides a type class Monoid, with functions to satisfy associative and identiy rules.
class Monoid a where
         -- ^ Identity of 'mappend'
        mempty  :: a
    
        -- ^ An associative operation   
        mappend :: a -> a -> a
        
         -- ^ Fold a list using the monoid.
        -- For most types, the default definition for 'mconcat' will be
        -- used, but the function is included in the class definition so
        -- that an optimized version can be provided for specific types.
        mconcat :: [a] -> a
        mconcat = foldr mappend mempty


Following table summarizes the function is Monoid type class.
Function
Signature
Description
mempty
mempty :: Monoid a => a
Represents identity property.
mappend
mappend :: Monoid a => a -> a -> a
Represents a binary operation.
mconcat
mconcat :: Monoid a => [a] -> a
Fold a list using the monoid

Following is the simple example of monoind instance for lists. We can form a monoid for lists under concatenation.
instance Monoid [a] where
    mempty  = []
   
    mappend = (++)

    mconcat xss = [x | xs <- xss, x <- xs]

Prelude> mconcat ["Hello", " How", " are", " you"]
"Hello How are you"
Prelude> 
Prelude> mconcat [[1, 2, 3], [4, 5, 6], [7, 8], [9, 10, 11, 12]]
[1,2,3,4,5,6,7,8,9,10,11,12]


We can form monoid for addition using 0 as identity element.
Sample.hs
data Addition x = Addition x deriving Show

instance Num x => Monoid (Addition x) where
    mempty  = Addition 0

    mappend (Addition x) (Addition y) = Addition (x + y)

Prelude> :load Sample.hs
[1 of 1] Compiling Main             ( Sample.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> mappend (Addition 123) (Addition 234)
Addition 357
*Main> 
*Main> (Addition 123) `mappend` (Addition 234) `mappend` (Addition 345)
Addition 702


We can form monoid for multiplication using 1 as identity element.

Sample.hs
data Multiplication x = Multiplication x deriving Show

instance Num x => Monoid (Multiplication x) where
    mempty  = Multiplication 1

    mappend (Multiplication x) (Multiplication y) = Multiplication (x * y)

Prelude> :load Sample.hs
[1 of 1] Compiling Main             ( Sample.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> mappend (Multiplication 10) (Multiplication 20)
Multiplication 200
*Main> 
*Main> (Multiplication 10) `mappend` (Multiplication 20) `mappend` (Multiplication 30)
Multiplication 6000
*Main> mconcat [(Multiplication 10), (Multiplication 20), (Multiplication 30)]
Multiplication 6000
*Main> 
*Main> mconcat [(Multiplication 10), (Multiplication 20), (Multiplication 30), (Multiplication 40)]
Multiplication 240000


Note:
a. Defining mconcat is optional, since it has the following default definition in Monoid class
mconcat = foldr mappend mempty



Previous                                                 Next                                                 Home

No comments:

Post a Comment