HASKELL MONAD OVERVIEW

REVISED: Sunday, October 13, 2024

1. INTRODUCTION

What is a monad?

A monad is a type constructor we will refer to as M, with two operations we will refer to as return and bind.

The operation return takes a value of type a and returns a value of type M a.

The operation bind takes a value of type M a and a function of type a -> M b, and returns a value of type M b.

The return operation is used to create new monadic values, and the bind operation is used to chain together monadic computations.

2. OVERVIEW

Why use monads?

Monads are a powerful tool for structuring computations. They can represent various computational concepts, such as state, sequencing, and exceptions.

State: Monads can be used to represent computations that have side effects, such as reading or writing to a file.

Sequencing: Monads can be used to represent computations that need to be executed in a specific order.

Exceptions: Monads can be used to represent computations that can fail.

Haskell has many built-in monads, including:

Maybe: This monad represents computations that can fail.

IO: This monad represents computations that have side effects.

State: This monad represents computations that have mutable states.

3. EXAMPLE

Here is an example of how to use the Maybe monad to represent a computation that can fail:

-- mayMon.hs

import Control.Monad()

{-

The function divide x y returns a Maybe Integer, representing the result of dividing two numbers. x is the numerator, y is the denominator. 

-}

divide :: Integer -> Integer -> Maybe Integer

divide x y =

  if y == 0 then Nothing else Just (x `div` y)

{-

The function main uses the `Maybe` monad to print the result of dividing x by y.

-}

main :: IO ()

main = do

  xStr <- readLn

  yStr <- readLn

  result <- divide x y

  case result of

    Just z -> print z

    Nothing -> putStrLn "Division by zero!"

This program effectively handles division by zero using the Maybe monad, providing a Nothing value in such cases and printing an appropriate error message.

Here's a breakdown of the code:

• import Control.Monad(): Imports the Control.Monad module, which provides essential functions and type classes for working with monads, including Maybe.
• divide :: Integer -> Integer -> Maybe Integer: Defines a function named divide that takes two Integer arguments (numerator and denominator) and returns a Maybe Integer quotient result.
• if y == 0 then Nothing else Just (xdivy): Uses a conditional expression to check if the denominator (y) is zero. If it is, the function returns Nothing to indicate an error (division by zero). Otherwise, it returns Just (xdivy), where xdivy performs integer division and Just wraps the result in a Maybe value.
• main :: IO (): Defines the main function that executes the program's logic.
• x <- readLn: Reads an Integer value from the standard input and binds it to the variable x.
• y <- readLn: Reads another Integer value from the standard input and binds it to the variable y.
• result <- divide x y: Calls the divide function with the values of x and y, binds the result (either Just z or Nothing) to the variable result.
• case result of: Uses a pattern matching case expression to handle the different possible values of result.
• Just z -> print z: If result is Just z, it prints the value of z (the result of the division).
• Nothing -> putStrLn "Division by zero!": If result is Nothing, it prints the error message "Division by zero!".

This program effectively demonstrates the use of the Maybe monad for handling potential errors and providing meaningful feedback to the user.

4. CONCLUSION

Monads are a powerful tool for structuring computations in Haskell. They can be used to represent a wide variety of computational concepts, such as state, sequencing, and exceptions.

This tutorial has helped you to learn how to program using Haskell monads.

5. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL UNWRAP WRAP INTRODUCTION

REVISED: Thursday, February 8, 2024

Haskell code shows copious amounts of (>>=) pronounced bind.

A Monad is a data structure which implements a Monad type class and satisfies Monad laws. A Monad typeclass defines two functions, the (>>=) and the return that know how to unwrap and wrap data. (>>=) bind is used to unwrap data and apply it to a function which takes the data as input and outputs a monad. (>>=) binds the unwrapped result of the computation on the left to the parameter of the one on the right. return is used to wrap data into a monad's type constructor.

Unwrap is the deconstructor in Haskell; destructing/unwrapping. Wrap is the constructor in Haskell; constructing/wrapping. You can also think of IO as a wrapper. The unwrapping of >>= cancels out the wrapping done by return, leaving only the function.

1. HASKELL WRAP UNWRAP EXAMPLE 1

The identity monad is a monad that does nothing special.

"Copy Paste" the following example into your text editor and "File Save As" WrapUnwrap.hs to your working directory.

module WrapUnwrap where

import Prelude hiding (Maybe(..))

import Control.Monad
import Control.Applicative

data Wrap a = Wrap a deriving Show

instance Functor Wrap where
   fmap f (Wrap a) = Wrap (f a)
   fmap _ Nothing  = Nothing

instance Monad Wrap where           
   return a = Wrap a
   Wrap a >>= f = f a   

instance Applicative Wrap where
   pure = Wrap
   Wrap f <*> Wrap a = Wrap (f a)
   _      <*> _      = Nothing

f :: Num a => a -> Wrap a
f a = Wrap (a + 1)                                -- Returns an incremented wrapped result.

(>>=) f (Wrap a) = f a                          -- unwrap does the exact opposite of wrap.

Load the example into GHCi.

Prelude>  :load WrapUnwrap
[1 of 1] Compiling WrapUnwrap       ( WrapUnwrap.hs, interpreted )
Ok, modules loaded: WrapUnwrap.
Prelude>

As shown below we can take data and wrap it inside a data type and then increment it while it is wrapped in that data type:

Prelude>  f 2
Wrap 3
Prelude>

2. HASKELL UNWRAP WRAP EXAMPLE 2

Consider the following Functor:

class Functor f where
     fmap :: (a -> b) -> f a -> f b

instance Functor Maybe where
     fmap _ Nothing = Nothing
     fmap f (Just x)   = Just (f x)

If a value is wrapped in Just the fmap calls the function on the unwrapped value, and then rewraps it in Just.

3. HASKELL WRAP EXAMPLE 3

Wrap was easy to see in Example 1. You have to look closer to see wrap in Example 2.

"Copy Paste" the following example into your text editor and "File Save As" JustNothing.hs to your working directory.

module JustNothing where

import Prelude hiding (Maybe(..), lookup)

data Maybe a = Just a | Nothing
  deriving (Eq, Ord, Show)

pie :: [(String, String)]
pie = [("3.141592653589793", "pi")]

lookup key [] = Nothing
lookup key ((k, v) : rest) = if key == k then Just v else lookup key rest

main = do
  putStrLn "Please type pi to 15 decimal places then press Enter."
  word <- getLine  -- Notice getLine has type "getLine :: IO String",  <- is used to unwrap String from the IO action and bind it to word.
  print (lookup word pie)  -- Notice word has type "word :: String", not IO String; therefore, word is not an IO action. 
  if word == "3.141592653589793"
     then return ( "Congratulations!" )
     else main  

Load the example into GHCi:

Prelude>  :load JustNothing
[1 of 1] Compiling JustNothing      ( JustNothing.hs, interpreted )
Ok, modules loaded: JustNothing.
Prelude>

Run the example in GHCi:

Prelude>  main
Please type pi to 15 decimal places then press Enter.
3.141592653589793
Just "pi"
"Congratulations!"
Prelude>

4. SUMMARY

The Haskell programming language is a functional language that makes heavy use of monads. A monad consists of a type constructor M and two operations, bind >>= and return. The return operation takes a value from a plain type and puts it into a monadic container using the constructor. The bind >>= operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline. This process effectively creates an action that chooses the next action based on the results of previous actions. Therefore, we should be able to determine our next action based on the results of previous actions. In other words, if x is a computation, and f is a function x >>= f is a computation which runs x, then applies f to its result, getting a computation which it then runs. Monads in Haskell can be thought of as composable computation descriptions.

5. CONCLUSION

Using return and bind we can wrap data and manipulate the wrapped data while keeping that data wrapped. We can also chain functions together that wrap. And in the process of doing these things we learn how monads work.

The unwrap wrap analogy is used to help you acquire intuition regarding how monads work. However, do not take unwrap wrap too literally. Unwrap wrap are mental tools to help you eventually gain the insight needed to think of monads in a computational context not in a unwrap wrap context.

6. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL MONAD TYPE CLASS

REVISED: Monday, February 12, 2024

Haskell Monad Type Class.

I.  HASKELL MONOID VERSUS MONAD TYPE CLASS

Monads are unavoidable, because they are the only way to do IO without violating referential transparency that given a function and an input value, you will always receive the same output. The essence of monads is composition.

As you study monads keep in mind it is no more necessary to understand monad theory to perform Haskell I/O than it is to understand group theory to do simple arithmetic. That said, the information below is for those of us who would like an introduction to monad theory with the objective of understanding monad theory.

A monad consists of a type constructor M and two operations, bind >>= and return. The return operation takes a value from a plain type and puts it into a monadic container using the constructor. The bind >>= operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline. This process effectively creates an action that chooses the next action based on the results of previous actions. Therefore, we should be able to determine our next action based on the results of previous actions.  The Haskell programming language is a functional language that makes heavy use of monads, and includes syntactic sugar to make monadic composition more convenient.  

(M t) -> (t -> M u) -> (M u)   -- Two common ways of describing a monad.
IO a → (a → IO b) → IO b

If M is the name of the monad and t is a data type, then M t is the corresponding type in the monad.

The unit function has the polymorphic type t → M t, which Haskell represents by return.

Binding operation of polymorphic type (M t) → (t → M u) → (M u), which Haskell represents by the infix operator >>= which is read as "bind". 

As shown above Haskell has an operator >>= pronounced "bind" with type IO a → (a → IO b) → IO b. That is, the operand on the left is an I/O action that returns a value of type a; the operand on the right is a function that can pick an I/O action based on the value produced by the action on the left. The resulting combined action, when performed, performs the first action, then evaluates the function with the first action's return value, then performs the second action, and finally returns the second action's value.

For example:

Use your editor to save the following MonadPipeline.hs file:

main =
       putStrLn "What is your name?" >> 
       getLine >>= \name ->
       putStrLn ("Nice to meet you, " ++ name ++ "!")

As shown below, load the above MonadPipeline.hs file into GHCi:

Prelude>  :load MonadPipeline.hs
[1 of 1] Compiling Main             ( MonadPipeline.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  main
What is your name?
Elcric
Nice to meet you, Elcric!
Prelude>  

The pipeline structure of the bind >>= operator ensures that the getLine and putStrLn operations get evaluated only once and in the given order, so that the side-effects of extracting text from the input stream and writing to the output stream are correctly handled in the functional pipeline.

A. FUNCTOR

Every monad is a functor which transforms one category into another category.

class Functor f where
   fmap :: (a -> b) -> f a -> f b

Think of a functor as a type of container where we are permitted to apply a single function to every object in the container.

If f is a functor, and we are given a function of type (a -> b), and a container of type (f a), we can get a new container of type (f b).

B. MONOID

Given

∀  is for every.
∈  is an element of.
•  is a function.
∃  is there exists.
:   is such that.
≡ is defined to be.

then

a Monoid is a function (•) that satisfies the following:

1. The Set (S) is closed under the binary function (•).

∀ a,b ∈ S: a•b ∈ S

2. The binary function is associative.

∀ a,b,c ∈ S: (a•b)•c = a•(b•c)

3. e is the identity element.

∃ e∈S: ∀ a∈S: e•a = a•e = a

C. MONAD LAWS

As shown below the three monad laws can be described in many different ways. Each author seems to have their own favorite descriptions.

Four commonly used descriptions of the three laws that monads must obey are color coded below for comparison:

1. Left Identity

return a >>= f ≡ f a

return >=> f == f

id . f  ==  f

return x >>= f ==  f x

2. Right Identity

m >>= return ≡ m

f >=> return == f

f . id ==  f

mv >>= return ==  mv

3. Associativity

(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

(f >=> g) >=> h == f >=> (g >=> h)

(f . g) . h == f . (g . h)

(mv >>= f) >>= g == mv >>= (\x -> (f x >>= g))

1. Left Identity

return a >>= f ≡ f a

2. Right Identity

m >>= return ≡ m

3. Associativity

(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

1. Left Identity

return >=> f == f

2. Right Identity

f >=> return == f

3. Associativity

(f >=> g) >=> h == f >=> (g >=> h)

1. Left Identity

id . f  ==  f

2. Right Identity

f . id ==  f

3. Associativity

(f . g) . h == f . (g . h)

1. Left Identity

return x >>= f ==  f x

2. Right Identity

mv >>= return ==  mv

3. Associativity

(mv >>= f) >>= g == mv >>= (\x -> (f x >>= g))

Monad is a type class. To be an instance of the Monad type class, you must provide the functions (>>=) and return. The function (>>) will be derived from (>>=). >>= is called an argument in the monadic world.

Prelude> :type (>>)
(>>) :: Monad m => m a -> m b -> m b
Prelude>

Prelude> :type (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b
Prelude>

Prelude> :type return
return :: Monad m => a -> m a
Prelude>

m stands for Monad.

Everything before the => symbol is called a class constraint.

Using the same symbol or name for different operations is called overloading. A type that contains one or more class constraints is called ad hoc polymorphism, better known as overloaded. In Haskell, type classes provide a structured way to control ad hoc polymorphism, or overloading.

D. MONAD

NO SIDE EFFECTS

The following identity Functor is also a  monad, a monad with no side effects.

data I a = I a
instance Functor I where
    fmap f (I x) = I (f x)

The identity function takes one argument and returns that argument.

Composing functions with no side effects:

g :: a -> b  -- Function g has input type a and output type b.
f  :: b -> c  -- Function f has input type b and output type c.

f o g :: a -> c

Their composition f o g is defined as first the application of function g to a variable of type a and then the application of function f to the output of g a variable of type b.

SIDE EFFECTS

Monads make possible the composition of functions with side effects, we have to use bind instead of normal function composition.

Given M is a monad, we want to compose the following two functions.

g :: a -> M b
f  :: b -> M c

The output of g is of type a ->  M b and f is of type b -> M c. Therefore, >>= is of type 

M b -> (b -> M c) -> M c

f composed with g is taking the output of g and passing it to f.

g  >>= f

>>= takes the output of g which is of type M b and also takes the function f
which is of type b -> M c and produces the output of f which is of type M c.

M b -> (b -> M c) -> M c

which is the type of  >>= bind.

By providing the definition of the function

M b -> (b -> M c) -> M c

we provide the way for the functions

g :: a -> M b
f  :: b -> M c

to be composed.

II. CONCLUSION

In this tutorial, you have received an introduction to the Haskell monad type class.

III. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL MONADS

REVISED: Wednesday, January 24, 2024

Haskell Monad.

The monad serves as the glue which binds together the actions in a program.

I.  FUNCTIONAL VERSUS IMPERATIVE

In functional programming, code is just like data; code and data are the same. In imperative programming, code and date, are two different things. For example, imperative programmers often access a function's data, via "table look ups".

The term "monad" comes from "category theory", which is a branch of algebra; or, depending on whom you talk to, algebra is a branch of "category theory."

Eugenio Moggi introduced the idea of using monads for programming in 1988, around the time the Haskell 1.0 standard was being developed. Many of the functions in today's Prelude date back to Haskell 1.0, which was released in 1990. In 1991, Philip Wadler started writing for a wider functional programming audience about the potential of monads, at which point they began to see some use. Not until 1996, and the release of Haskell 1.3, did the standard acquire support for monads.

Functional programming is not difficult; you do not need to know "category theory" to program "shared mutable state" with functions using  Haskell monads. Haskell functions are first-class data types, meaning that Haskell programs can work with them just as well as they can work with any other type of data.

x : int                   -- Asserts function x has type int.

f : int -> int      -- Asserts function f is a thing that takes an int and gives you an int.

x : a                      -- Asserts function x has type a, which is a generic, any type.

f : a -> a            -- Asserts function f takes an a of any type and gives you an a of any type.

g : a -> a           -- Asserts function g takes an a of any type and give you an a of any type.

We can combine the two functions f and g shown above.

One way would be to call the function g on a variable a of type a; for example, g(a); then call the function f on that result; for example, f(g(a))

Another way would be to call the function f on a variable a of type a; for example, f(a); then call the function g on that result; for example, g(f(a))

In Haskell, calling a function is the same as function application.

g a        -- Function application in Haskell; calling the function g with an argument of type a.

g(f a)  -- Calls function f first and then calls function g.

f(g a)  -- Calls function g first and then calls function f.

Function composition: composing two functions produces a new function that, when called with a parameter, a, is the equivalent of calling g with the parameter a, and then calling f with that result.

(f o g) a = f (g a)    

The little circle o is called function composition; it is a generic composition operator. The notation (f o g) is read as "f composed with g" or just "f of g". Composition operators are studied in the field of "operator theory".

Prelude>  :type (.)

(.) :: (b -> c) -> (a -> b) -> a -> c

Prelude> 

(f o g) = h

(f o g) = h : a -> a     -- The function h takes an a of any type and give you an a of any type.

II.  MONOID

Functions under composition are a monoid.

A monoid is a set or collection of things, plus a rule for combining those things, and that rule obeys some rules. 

One of the biggest problems in software today is controlling complexity. The world of side effects is very complicated. Monoids are the way to build complexity. Monoids allow you to create complexity starting with simplicity. We started with two functions and created a third function of the same type; i.e.:

f  : a -> a            
g : a -> a            
h : a -> a     

Compositionality is the way to control complexity.

Examples of monoids:

(+)     and 0
(*)     and 1
(||)    and False
(&&) and True
(++) and []
(>>) and done

III.  MONOID EXAMPLE

Consider a clock. The numbers on a clock form a monoid. The rule for combining them is take one number from the clock x, add another number from the clock y, and then cast out 12s; for example:

(x + y) % 12     -- % is "modulus" which in this case means the remainder after dividing by 12. 

(7 + 10) / 12 = 17/12 = 1 twelve and a remainder of 5. 

Prelude> (7 + 10) `mod` 12     -- `mod` is a modulus operator.
5

it :: Integral a => a
Prelude>

Prelude> (7 + 10) `rem` 12     -- `rem` is a modulus operator.

5

it :: Integral a => a
Prelude>

A. ASSOCIATIVITY

It does not matter how you group the applications; function composition is always associative.

x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z

(f o g) o h = f o (g o h)     -- (g o h) = g (h a) and  f o (g o h) = f ( g(h a) )

B. EXISTENCE OF A UNIT OR A ZERO

The monoid must contain a special member such that:
 x ⊕ 12 = x            -- In the clock example, 12 represents a "special member".
12 ⊕ x = x

There is a special function that lives in the monoid called id.

id : a -> a
id a = a

(f o id) = f (id a)
            = f a

In Haskell unit is:

return : a -> Ma

C. COMMUTATIVITY

A monoid does not have to satisfy the law of commutativity.

x ⊕ y != y ⊕ x 

f(g a) != g(f a)          -- For example, sin cos not same as cos sin.

If you are going to nest function calls, the types must line up; then compositionality makes sense.

IV.  MONADS

x : a

f : a -> Ma          -- Ma is a type constructor which creates a function of a generic type.            
g : a -> Ma         -- The function g takes an a and returns a Ma            
h : a -> Ma
>>= : a -> Ma     

\a -> [ (f a) >>=  \a -> (g a) ]        -- A function of a that does f a; >>= is  bind or shove
          Ma             a -> Ma            -- Ma is data living in a monad; or functions live in a monoid.

\a -> [ Ma >>=  a -> Ma ]

>>= ensures your functions are compositional.

g : a -> b
f : b -> c
(f o g) : a -> c

(f o g) a = f (g a)

V. CONCLUSION

In this tutorial, you have received an introduction to Haskell monads.

VI. REFERENCES

Brian Beckman: Don't fear the Monad.