Scribd
Upload
17 views3 pages

Haskell Monad Exercises: Maybe & State

This document describes two Haskell exercises involving monads. The first exercise involves defining the Expr data type as a monad and using it to implement functions for replacing variables and converting expressions. The second exercise involves modeling randomness using the State monad by rewriting a dice rolling program to explicitly manage the random seed.

Uploaded by

jdkdjs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views3 pages

Haskell Monad Exercises: Maybe & State

This document describes two Haskell exercises involving monads. The first exercise involves defining the Expr data type as a monad and using it to implement functions for replacing variables and converting expressions. The second exercise involves modeling randomness using the State monad by rewriting a dice rolling program to explicitly manage the random seed.

Uploaded by

jdkdjs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Haskell exercise: Monads

Department of Mathematics and Computer Science


University of Southern Denmark
October 25, 2017

1. The Maybe-monad, and a monad for Expr


You are given a data type for expressions:

data Expr a = Var a | Add (Expr a) (Expr a) deriving Show

1. To turn Expr into a monad, we should give valid definitions for return
and bind:

return :: a → Expr a
(>>=) :: Expr a → (a → Expr b) → Expr b

Fill out the function bodies with appropriate definitions:

instance Monad Expr where


return x =⊥
(Var a) >>= f = ⊥
(Add x y) >>= f = ⊥

2. We would like to define a function

replace :: Eq a ⇒ [(a, b)] → Expr a → Expr (Maybe b)

which replaces occurences of type a with something of type Maybe b.


Example:

• replace [ ] (Var ’a’) = Var Nothing


• replace [(’a’, 3)] (Var ’a’) = Var (Just 3)

1
• replace [(’a’, 3)] (Add (Var ’a’) (Var ’b’)) = Add (Var (Just 3)) (Var Nothing)

You should use the functionality of the Expr -monad to implement


replace. You can use

lookup :: Eq a ⇒ a → [(a, b)] → Maybe b

from the Prelude in your implementation of replace.

3. Now we would like to make a function

convert :: Expr (Maybe a) → Maybe (Expr a)

which returns Nothing if there is an occurrence of Nothing inside the


input expression e, otherwise it returns Just e 0 , where e 0 is a new
expression where the internal values of type a are not wrapped in Just.
You should use the functionality of the Maybe monad to implement
your convert function.

2. Random numbers and the State Monad


Functions involving randomness in Haskell take a seed g :: StdGen as input,
and returns an output and a new seed g 0 :: StdGen.
As an example, the built-in function

randomR :: (Int, Int) → StdGen → (Int, StdGen)

on inputs randomR (a, b) g, returns (x , g 0 ) (an integer x and a new seed g 0 ),


where x is chosen uniformly, with the condition a 6 x 6 b.
To get a random seed, one needs the IO environment.
A complete program to simulate two die rolls and return the sum of the
die-values is given below. Make sure that you understand how this works,
before going on to the rest of the exercise.

import [Link]
die6 :: StdGen → (Int, StdGen)
die6 g = randomR (1, 6) g
twoDie :: StdGen → (Int, StdGen)
twoDie g = let (d1 , g 0 ) = die6 g
(d2 , g 00 ) = die6 g 0
in (d1 + d2 , g 00 )
test :: IO (Int, StdGen)

2
test = do g ← newStdGen
return (twoDie g)

We would like to give a nicer definition for twoDie which does not explic-
itly handle the random seed.
The State-monad libary provides the following functions to wrap and
unwrap functions in the state monad.

state :: (s → (a, s)) → State s a


runState :: State s a → s → (a, s)

You are provided the following stub of a program:

import Control .Monad .State


die6 0 :: State StdGen Int
die6 0 = ⊥
twoDie 0 :: State StdGen Int
twoDie 0 = ⊥
test 0 :: IO (Int, StdGen)
test 0 = do g ← newStdGen
return (runState twoDie 0 g)

1. Using the function state and your definition die6 , provide a definition
of die6 0 .

2. Implement twoDie 0 only referring to die6 0 and the monadic functional-


ity of State Monad.

Common questions

Powered by AI

By leveraging the Maybe monad alongside the State monad, Haskell can handle operations involving randomness and potential failure more robustly. The State monad manages and propagates changes in state, such as updating random seeds, while the Maybe monad can encapsulate successful or unsuccessful outcomes. Together, they streamline logic where computations may rely on random values and may need to account for scenarios like missing data, ensuring clean, efficient code execution .

In Haskell, IO actions are segregated to maintain purity of functions. Random seed generation involves IO, introducing impure elements due to its dependency on system state or time. These actions, while necessary for replicating certain real-world operations within the computational model, inherently obscure functional purity. By separating them within the IO monad, Haskell preserves functional integrity elsewhere, but developers must be aware of this impurity when incorporating random behavior .

The state monad abstracts the handling of state (such as a random seed) within a computation, simplifying functions like 'twoDie'. Instead of manually passing the seed between function calls, the state monad encapsulates this behavior. The rewritten 'twoDie′' uses the 'State' type transformer with bindings to sequentially process stateful operations. 'runState' applies these operations while maintaining the seed implicitly. This leads to cleaner, more modular code that focuses on the logic rather than administrative state management .

Monads, like the Maybe monad, allow us to handle computations which may fail. In the convert function, we can traverse an expression of type Expr (Maybe a) and check for the presence of 'Nothing'. If 'Nothing' is found, the result is Nothing. Otherwise, it strips away the Just wrappers, producing an Expr a. This functionality ensures that any uncertainty or potential failure (encoded as 'Nothing') is accounted for before converting to a safer, non-maybe expression .

'runState' serves to execute a stateful computation encapsulated within the State monad. It applies the State computation to an initial state, such as a random seed, and returns a tuple: a result along with a new state. In applications like dice rolls, this facilitates seamless state (seed) propagation and result extraction without explicit state passing, streamlining operations like generating sequential random numbers .

The key consideration in implementing 'convert' is ensuring that any occurrence of 'Nothing' in the expression results in an overall result of Nothing. The process involves checking each part of the expression; if all values are 'Just a', it recreates the expression without the Just wrapper in 'Expr a'. The Maybe monad facilitates clean handling by allowing this traversal and immediate quitting upon encountering Nothing, leveraging its encapsulated failure handling .

Using the Maybe monad for transformations provides a safe way to handle missing data by encoding absence with 'Nothing' and presence with 'Just a'. This allows chain-safe evaluations where potential absence is gracefully handled, preventing runtime errors. However, excessive use may complicate code, requiring multiple checks or transformations for wrapped data handling, potentially leading to verbose code if not well-structured .

The 'replace' function uses the provided list of replacements and the lookup function from Prelude to map values of type 'a' to expressions of type 'Expr (Maybe b)'. For an expression such as Var a, it checks the list of replacements for a corresponding value. If found, Var (Just b) is returned; otherwise, Var Nothing is returned. For compound expressions like Add, it recursively applies the replacement on both sub-expressions .

The 'randomR' function uses a seed (StdGen) as state to produce a random number and a new seed as output, following the state-transition paradigm. This ensures that each call to 'randomR' with a given seed results in the same sequence of random numbers, adding predictability to randomness. The necessity of the IO environment for seed generation arises from the need for external and unpredictable input, which can't be purely achieved within Haskell's functional paradigm, hence relying on I/O operations .

Monadic structures, such as those represented by the Maybe or State monad, offer several advantages for manipulating expression trees. They provide a coherent framework for chaining operations with context management, such as error handling (Maybe) or state threading (State), without deeply nesting functions. This modular approach eases transformations, support reusable patterns, and manage side effects cleanly, critical for complex tree evaluations or transformations .

You might also like