COMPSCI 220 Programming Methodology

Name: _________________________________________________________________

ID #: ___________________________________________________________________

Exercise Assignment 05: Either, Sequence and Traverse

In this exercise, we will be writing two functions that operate on the Either data type: sequence and traverse. As before, you should implement these functions in the functional style, using pattern matching. You may use any List functions you find necessary.

Use of laptops or other electronic devices is FORBIDDEN for this assignment.

Matching Either:

• case Left(l) will match a single Left value
• case Right(r) will match a single Right value

Matching Lists:

• case h :: t will split the list at the first element
• case Nil will only match an empty list

Part 1: Sequence

def sequence[L,R](es: List[Either[L,R]]): Either[L, List[R]]

sequence combines a list of Either into one Either containing all the Right values in the original list. However, if the list contains any Lefts, sequence will return the first Left it encounters instead.

For example:

sequence(List(Right(1), Left("error"), Right(2), Left("more error"))) == Left("error") 
sequence(List(Right(1), Right(2), Right(3))) == Right(List(1,2,3))

Part 2: Traverse

def traverse[A,L,R](as: List[A])(f: A => Either[L,R]): Either[L, List[R]]

traverse is basically map: It takes a list of type A and a function f : A => Either[L,R], and produces an Either[L, List[R]]. That is, if f returns a Left at any point, traverse returns a Left. Otherwise, it returns a Right containing the List generated by applying f to the elments of the input list.

Please implement this efficiently – try to traverse the list only once.