CSCI 312 Assignment #1
This assignment is a modified version of the Haskell warmup exercise from Prof. Michael Greenberg’s syllabus. I’ve included only those problems that I was able to complete in a reasonable amount of time. If you’re feeling ambitious, you might try some of the omitted problems for extra credit. Following Prof. Greenberg’s convention, I’ve used undefined
to indicate the code you need to write yourself.
Problem 1: natural recursion
Please don’t use any Prelude functions to implement these—just write natural recursion, like we did in class.
Write a function called sumUp
that sums a list of numbers.
sumUp :: [Int] > Int
sumUp [] = undefined
sumUp (x:xs) = undefined
Write a function called evens
that selects out the even numbers from a list. For example, evens [1,2,3,4,5]
should yield [2,4]
. You can use the library function even
.
evens :: [Int] > [Int]
evens [] = undefined
evens (x:xs) = undefined
Write a function called incAll
that increments a list of numbers by one. You’ll have to fill in the arguments and write the cases yourself.
incAll :: [Int] > [Int]
incAll = undefined
Now write a function called incBy
that takes a number and increments a list of numbers by that number.
incBy :: Int > [Int] > [Int]
incBy = undefined
Write a function append
that takes two lists and appends them. For example, append [1,2] [3,4] == [1,2,3,4]
. (This function is called (++)
in the standard library… but don’t use that to define your version!)
append :: [Int] > [Int] > [Int]
append = undefined
Problem 2: data types
Haskell (and functional programming in general) is centered around datatype definitions. Here’s a definition for a simple tree:
data IntTree = Empty  Node IntTree Int IntTree deriving (Eq,Show)
Write a function isLeaf
that determines whether a given node is a leaf, i.e., both its children are Empty
.
isLeaf :: IntTree > Bool
isLeaf Empty = undefined
isLeaf (Node l x r) = undefined
Write a function sumTree
that sums up all of the values in an IntTree
.
sumTree :: IntTree > Int
sumTree = undefined
Write a function fringe
that yields the fringe of the tree from left to right, i.e., the list of values in the leaves of the tree, reading left to right.
For example, the fringe of Node (Node Empty 1 (Node Empty 2 Empty)) 5 (Node (Node Empty 7 Empty) 10 Empty)
is [2,7]
.
fringe :: IntTree > [Int]
fringe = undefined
Problem 3: binary search trees
Write a function isBST
to determine whether or not a given tree is a strict binary search tree, i.e., the tree is either empty, or it is node such that:

 all values in the left branch are less than the value of the node, and
 all values in the right branch are greater than the value of the node,
 both children are BSTs.
Problem 4: map and filter
We’re going to define each of the functions we defined in Problem 1, but we’re going to do it using higherorder functions that are built into the Prelude. In particular, we’re going to use map
, filter
, and the two folds, foldr
and foldl
. To avoid name conflicts, we’ll name all of the new versions with a prime, '
.
Define a function sumUp'
that sums up a list of numbers.
sumUp' :: [Int] > Int
sumUp' l = undefined
Define a function evens'
that selects out the even numbers from a list.
evens' :: [Int] > [Int]
evens' l = undefined
Define a function incAll'
that increments a list of numbers by one.
incAll' :: [Int] > [Int]
incAll' l = undefined
Define a function incBy'
that takes a number and then increments a list of numbers by that number.
incBy' :: Int > [Int] > [Int]
incBy' n l = undefined
Problem 5: defining higherorder functions
We’re going to define our own versions of the map
and filter
functions manually, using only natural recursion and folds—no using the Prelude or list comprehensions. Note that I’ve written the polymorphic types for you.
Define map1
using natural recursion.
map1 :: (a > b) > [a] > [b]
map1 = undefined
Define filter1
using natural recursion.
filter1 :: (a > Bool) > [a] > [a]
filter1 = undefined
Problem 6: Maybe
and Either
Python and Java allow for null values (None
in Python and null
in Java) as a convenient way of indicating the absence of a result. In a famous 2009 lecture, computer scientist Tony Hoare (inventor of Quicksort) called the use of such values a Billion Dollar Mistake, citing the hidden costs that they can incur by allowing you to ignore exceptional situations.
Instead of relying on null values, Haskell provides a special datatype called Maybe
. This datatype allows you to “wrap” a result value in a way that forces you to deal with exceptional situations.
Consider, for example, the classic squareroot function, which is defined only for nonnegative numbers. In Java or Python, passing a negative value to such a function would be handled by throwing (raising) an exception. In Haskell, by contrast, we could make this function return the type Maybe Float
, defined as:
data Maybe Float = Nothing  Just Float
Values of the type Maybe a
can be Nothing
or Just x
, where x
is a value of type a
. Note that Maybe
is polymorphpic: we can choose whatever type we want for a
, e.g., Just 5 :: Maybe Int
, or we can leave a
abstract, e.g., Just x :: Maybe a
iff x :: a
.
Write a function sqrt'
that returns Just x
if its input value x
is nonnegative, and returns Nothing
otherwise:
sqrt' :: Float > Maybe Float
sqrt' = undefined
The test code for this function will use Haskell’s mapMaybe
function to ignore Nothing results in a list of numbers when computing their square roots.
This trick – using a dataype to handle exceptional situations – also comes in handy when you want to report an exceptional situation without resorting to an exception. For example, consider another classic “gotcha”, dividebyzero. For reporting a dividebyzero, we might want to have function that returns the result of a division if the denominator is nonzero, and returns an error message (string) otherwise. Haskell’s Either
datatype supports this:
data Either a b = Left a  Right b
Typically, the error result (e.g., an error message) is associated with the Left
option, and the nonerror result is associated with the Right
option (presumably because right also means correct.)
To finish this problem, write a function div’ that returns either an error message or correct value, depending on whether its second input is zero:
div' :: Float > Float > Either String Float
Problem 7: Creating polymorphic datatypes
Haskell’s Maybe
and Either
are polymorphic datatypes; i.e., they support working simultaneously with values of different types. You are already familiar with polymorphic types from Python, in the form of tuples. Like Python, Haskell has a tuple datatype that allows us to aggregate values: values of type (a,b)
will have the form (x,y)
, where x
has type a
and y
has type b
.
Write a function swap
that takes a pair of type (a,b)
and returns a pair of type (b,a)
.
swap :: (a,b) > (b,a)
swap = undefined
Write a function pairUp
that takes two lists and returns a list of paired elements. If the lists have different lengths, return a list of the shorter length. (This is called zip
in the prelude. Don’t define this function using zip
!)
pairUp :: [a] > [b] > [(a,b)]
pairUp = undefined
Write a function splitUp
that takes a list of pairs and returns a pair of lists. (This is called unzip
in the prelude. Don’t define this function using unzip
!)
splitUp :: [(a,b)] > ([a],[b])
splitUp = undefined
Write a function sumAndLength
that simultaneously sums a list and computes its length. You can define it using natural recursion or as a fold, but—traverse the list only once!
sumAndLength :: [Int] > (Int,Int)
sumAndLength l = undefined
Problem 8: maps and sets
Like Python, Haskell has many convenient data structures in its standard library. In this problem we’ll be working with sets and maps. Data.Map (like Python dictionary) and Data.Set (like Python sets). Specifically, we’ll use maps and sets to code up the directed acyclic graph (DAG) structure that you learned about in CSCI 112. The code shown in the instructions below is already written for you in the Hw01.hs file you downloaded, so for now you can just read over the code below and make sure you understand it.
We can start by defining what we mean by the nodes of the DAG: we’ll have them just be strings. We can achieve this by using a type synonym.
type Node = String
To create a Node
, we can use the constructor, like so:
a = "a"
b = "b"
c = "c"
d = "d"
e = "e"
We can define a DAG now as a map from Node
s to sets of Node
s. The Map
type takes two arguments: the type of the map’s key and the type of the map’s value. Here the keys will be Node
s and the values will be sets of nodes. The Set
type takes just one argument, like lists: the type of the set’s elements.
type DAG = Map Node (Set Node)
Let’s start by building a simple DAG g
to represent the graph below:
g = Map.fromList [(a, Set.fromList [b,c]),
(b, Set.fromList [d]),
(c, Set.fromList [d]),
(d, Set.fromList []),
(e, Set.fromList )]
Now write a function hasPath
that takes a DAG and two nodes and returns True if there is a path from the first to the second in the DAG:
hasPath :: DAG > Node > Node > Bool
To write this function I implemented a simple algorithm: if the second node is a member of the first node’s neighbors, return True; otherwise, recur on each of the neighbors and the second node and return whether any of the results is True. To support this algorithm I found it useful to write the following two helper functions:
neighbors :: DAG > Node > Set.Set Node
any' :: Set.Set Bool > Bool
The neighbors
function returns the neighbors of a node, and the any'
function returns True if any members of a set are True, and False otherwise.