Written Assignment 3

Description

• Practicing do-notation (15)

These exercises give you practice with working with Haskell’s do-notation. We will work with several monads we have seen in class: Maybe, OrErr, and WithLog. Take a look at the lecture slides for the de nitions of these types and their monad instances.

1.1 Using >>=

Translate the following examples using >>=, eliminating the do-notation. Simplify as far as you can.

1. do ns <- Right 17

ls <- return [ns, 2]

Right (7:ls)

2. do s1 <- MkWithLog (10 – 1, “Subtract 1”) tn <- MkWithLog (s1 * 10, “Times n”) return tn

2. do rc <- if 3 /= 0 then Just (1 / 3) else Nothing Just (4 * rc)

1.2 Using >>

Translate the following examples using >>, eliminating the do-notation. Simplify as far as you can.

1. do return “hello” Nothing

Just “world”

2. do MkWithLog (n, “First”) MkWithLog (37, “Second”) return 12

1.3 Nested do-blocks

Translate the following examples using >>=, eliminating the do-notation. Simplify as far as you can.

1. do c <- Just 3

let f n = do m <- Just (n – 7)

Just (m * 3)

in (f c)

2. do nnn <- Right [0, 3, 2, 1]

case nnn of

[]	->	Left	“empty list”
(n:_) ->		if n	/= 0
		then	(do r <- Right (1/n)

return r)

else Left “division by zero”

1.4 More simplifying

Simplify the following expressions. Begin by replacing the do-notation by >>= and >>, then unfold de nitions and simplify. Show a few intermediate steps and the nal expression you reach.

1. do if True

then MkWithLog (5, “First”)

else MkWithLog (37, “Second”)

return 12

2. do MkWithLog (5, “badger”) return 4

return 3

2. do k <- Right [4, 7, 6]

v <- Left “fail 1”

w <- Left “fail 2”

Right $ \x -> 9:k

• Lazy datatypes (15)

In class so far, we have seen how to model eager datatypes. Roughly speaking, eliminating these types (via projection or pattern matching) requires evaluating all of their components to values. As we have mentioned, Haskell’s datatypes are lazy, not eager. In this exercise, we will see how to model lazy datatypes. Since we are focusing on the operational behavior (eager versus lazy), we will not be working with typing rules.

To start, we will work with the lambda calculus with booleans and recursion. The syntax of values and expressions are as follows:

v ::= x j true j false j x: e

e ::= x j true j false j x: e j e₁ e₂ j if e₁ then e₂ else e₃ j x x: e

Throughout this section, we use speci c letters to represent di erent kinds of programs:

The letter e stands for any expression (any program) The letter x stands for any variable

The letter v stands for any value

We will work with a small-step semantics. Function application will be lazy (call-by-name):

e1

! e10

e

e

!

e0

e

2

( x: e ) e

2 !

e

[x

e

]

1 2

1

1

1

7!2

In particular, note that the argument of a function is not evaluated to a value before it is plugged into the function. As we have seen in class, the xed-point construct steps by unfolding:

x x: e ! e[x 7!( x x: e)]

As always, e[x 7!e⁰ ] stands for the expression e where all free occurrences of variable x have been replaced by e⁰ .

2.1 Lazy products

Let’s start with lazy products, also known as tuples. We start by extending the expression grammar:

e ::= j (e₁; e₂) j f st(e) j snd(e)

For the eager tuples we saw in class, we added a new value of the form (v₁; v₂). For lazy tuples, we will add something slightly di erent:

• ::= j (e₁; e₂)

In particular, note that a tuple of two expressions (e₁; e₂) is a value, even if e₁ and e₂ are not values.

1. Write out the small-step rules for the three new constructs. Hint: you will need four rules, two for f st(e) and two for snd(e)|these should be almost exactly the same as the rules we saw in class for eager tuples, only now we have de ned values di erently. You do not need a rule to step tuples, since tuples are values now.

2. Consider the following bit of Haskell code using lazy tuples:

loopForever :: Bool loopForever = loopForever

getFst :: Bool

getFst = fst (True, loopForever)

getSnd :: Bool

getSnd = snd (True, loopForever)

Translate each de nition into the lambda calculus, and show how the three expressions step. You should con rm that getFst terminates, while getSnd does not. Hint: a quick way to write a non-terminating expression is x x: x.

2.2 Lazy lists

Now, let’s add lazy lists. We start by extending the expression grammar:

e ::= j nil j cons(e₁; e₂) j case e of fnil ! e₁; cons(x₁; x₂) ! e₂g

There are two constructors for lists: nil is empty list, and cons(e₁; e₂) is a non-empty list with head e₁ and tail e₂. Lists are eliminated/destructed by pattern matching|the case expression has two cases, one for empty list and one for non-empty lists. Note that in the second case, the body e₂ can use the newly bound variables x₁ and x₂, which name the rst and tail elements of e.

We’ll extend the values of our language as follows:

v ::= j nil j cons(e₁; e₂)

In particular, note that the cons of two expressions cons(e₁; e₂) is a value, even if e₁ and e₂ are not values.

1. Write out the small-step rules for the three new constructs. Hint: you will need three rules, all for the pattern match. You do not need a rule to step nil and cons(e₁; e₂), since these are values now.

2. Consider the following bit of Haskell code using lazy lists:

allTrue :: [Bool]

allTrue = True : allTrue

negate :: Bool -> Bool

negate b = if b then False else True

myMap :: (Bool -> Bool) -> [Bool] -> [Bool]

myMap f ls = case ls of

[] -> []

(b:bs) -> (f b) : (myMap f bs)

isEmpty :: Bool

isEmpty = case (myMap negate allTrue) of

[] -> True

(b:bs) -> False

Translate each de nition into the lambda calculus, and show how allTrue steps. Then, show how isEmpty steps. You should con rm that these two expressions both terminate.

As we saw in class, myMap can also be de ned using \accumulating” recursion; this leads to a tail-recursive function and is often more e cient. What would happen if we de ned myMap this way?

myAccMap :: (Bool -> Bool) -> [Bool] -> [Bool] myAccMap f ls = go f ls []

where go f ls acc = case ls of

[] -> acc

(b:bs) -> go f bs (acc ++ [f b])

isAccEmpty :: Bool

isAccEmpty = case (myAccMap negate allTrue) of [] -> True

(b:bs) -> False

Would isAccEmpty still terminate? You don’t need to translate these de nitions to the lambda calculus (and it’s not important how ++ is de ned), but you can check your predictions with GHCi.

4