Spring 2024 Haskell Exam

Problem 1

Write pure function pick that accepts a predicate, a first value, a second value, and a list. It applies the predicate to each element of the list. Those elements for which the predicate is true are replaced by the first value. The others are replaced by the second value. It returns the list of replacements. For example:

GHCi

> pick even "even" "odd" [1..5]
["odd", "even", "odd", "even", "odd"]
> pick isDigit '0' '_' "June 14, 2003" 
"_____00__0000"

> pick even "even" "odd" [1..5]
["odd", "even", "odd", "even", "odd"]
> pick isDigit '0' '_' "June 14, 2003" 
"_____00__0000"

Problem 2

Write pure function crossref that accepts two lists whose elements may be compared with ==. It locates each element in the other list. It returns a pair of lists that are like the two parameters, but each element is now a pair of the original element and the first possible index of the original element in the other list. For example:

GHCi

> crossref [17] [23, 17]
([(17, Just 1)], [(23, Nothing), (17, Just 0)])

> crossref [17] [23, 17]
([(17, Just 1)], [(23, Nothing), (17, Just 0)])

The first list in the returned pair indicates that value 17 appears at index 1 in the second list. The second list indicates that 23 doesn't occur in the first list and value 17 appears at index 0.

Function elemIndex in Data.List is useful.

Problem 3

Write a main function that prints the strings provided as command-line arguments in a stair pattern, with one word picking up where the previous left off. For example:

$ runhaskell stairs.hs burnt swim canary glimmer yarn
burnt
     swim
         canary
               glimmer
                      yarn

$ runhaskell stairs.hs burnt swim canary glimmer yarn
burnt
     swim
         canary
               glimmer
                      yarn

A recursive helper function and replicate are useful here.

Problem 4

Model a family of expressions with a data type named Expression. Have the compiler generate a show function, and give it the following constructors:

Literal, which accepts an Int
Increment, which accepts an expression to be increased by 1
Negate, which accepts an expression to be arithmetically negated
Add, which accepts two expressions to sum
Mod, which accepts two expressions whose remainder is to be computed

Define also a compute function that accepts an Expression and evaluates it to an Int, as demonstrated in these calls:

> compute $ Literal 12
12
> compute $ Add (Literal 12) (Literal 14)
26
> compute $ Mod (Literal 27) (Literal 5)
2
> compute $ Increment $ Increment $ Literal 6
8

> compute $ Literal 12
12
> compute $ Add (Literal 12) (Literal 14)
26
> compute $ Mod (Literal 27) (Literal 5)
2
> compute $ Increment $ Increment $ Literal 6
8

Problem 5

There are two common sequences that we all learn about: arithmetic sequences and geometric sequences. Arithmetic sequences are defined by a starting number and an additive offset. The sequence \([2, 6, 10, 14, 18, \ldots]\) starts at 2 and has an offset of 4. Geometric sequences are defined by a starting number and a multiplicative ratio. The sequence \([3, 6, 12, 24, 48, \ldots]\) starts at 3 and has a ratio of 2.

Define a type Arithmetic with a single constructor that accepts the sequence's start and offset, both as Integer. Define also a type Geometric with a single constructor that accepts the sequence's start and ratio, both as Integer. Have the compiler generate a show function for each type.

We'd like a uniform way of asking these sequences for their \(i^\mathrm{th}\) term. Define a typeclass named Sequence that imposes a pure function named ith. Given a sequence and i as parameters, it returns term i of the sequence as an Integer. Make Arithmetic and Geometric instances of this typeclass. Then we can make calls like these:

> ith (Arithmetic 2 4) 0
2
> ith (Arithmetic 2 4) 1
6
> ith (Geometric 3 2) 4
48

> ith (Arithmetic 2 4) 0
2
> ith (Arithmetic 2 4) 1
6
> ith (Geometric 3 2) 4
48

Problem 6

Write a main that reads in a dictionary and displays it in a friendlier form. The path to the dictionary file is passed as a command-line argument. Each pair of lines in the file is a word and its definition. For example, the file may have these three definitions:

robot
a machine that walks or talks
talent
skill developed when no one's looking
politics
when you throw away half the data

robot
a machine that walks or talks
talent
skill developed when no one's looking
politics
when you throw away half the data

The program outputs this more readable and sorted representation for this dictionary:

politics: when you throw away half the data
robot: a machine that walks or talks
talent: skill developed when no one's looking

politics: when you throw away half the data
robot: a machine that walks or talks
talent: skill developed when no one's looking

The sort function from Data.List and the chunksOf function from Data.List.Split are useful here.