$29
MP1 Basic Haskell Solution
Objectives
==========
We will be using Haskell throughout the course to implement other programming
languages. That being said, the focus of this course is *not* on Haskell, but
rather on studying programming languages in general. You need to understand
basic Haskell before we can proceed with the rest of the course though; this MP
will test that understanding.
Goals
-----
- Part 1:
- Write recursive functions and definitions.
- Implement some set-theoretic functionality using Haskell lists.
- Use higher-order functions to compactly represent common code patterns.
- Part 2: Use and write Algebraic Data Types (ADTs) with some associated
operators.
- Manipulate linked lists and simple arithmetic expressions defined using
ADTs
- Define a binary tree ADT and implement a function on binary trees.
- Define a constant value ADT for a simple programming language and a
higher order function to manipulate those values.
Useful Reading
--------------
If you are stuck on some problems, perhaps it's time to read some of [Learn You
a Haskell for Great Good](http://learnyouahaskell.com/chapters). I would
recommend reading the whole book eventually, but if you're crunched for time
Chapter 3 on Types and Typeclasses, Chapter 4 on Syntax in Functions, and
Chapter 8 on Making Your Own Types and Typeclases seem the most relevant. If
you're still stuck on recursion problems, check out Chapter 5 on Recursion.
Getting Started
===============
Relevant Files
--------------
In the directory `recursion/src` you'll find `Lib.hs` with all the relevant code
for Part 1. In the directory `adt/src` you'll find a file of the same name with
all the relevant code for Part 2. In each file, the first line `module Lib where`
says that what follows (the rest of the file in this case) belongs to the `Lib`
module. Haskell has a module system which allows for extensive code re-use.
Saying something like `import Data.List` imports the `List` module, for example.
Running Code
------------
First, you have to `stack init` (you only need to do this once):
``` {.sh}
$ stack init
```
To run your code, start GHCi with `stack ghci`:
``` {.sh}
$ stack ghci
- more output -
Ok, modules loaded: Lib.
*Lib
```
Testing Your Code
-----------------
You can run the test-suite as you fill in the solutions for Part 1.
The following ensures the file will type-check, but the
corresponding `myFunction` test will fail.
``` {.haskell}
myFunction = undefined
```
In Part 2, you must supply the Algebraic Data Type declarations at the end of the
problem-set correctly in order to compile the tests. If you are having trouble with
one declaration in particular, use the interpreter to define and debug each ADT
individually.
In each part, the test suite is compiled and executed by running `stack test`
in the project directory. `recursion` and `adt` for parts 1 and 2 respectively.
``` {.sh}
$ stack test
```
It will tell you which test-suites you pass, fail, and have exceptions on. To
see an individual test-suite (so you can run the tests yourself by hand to see
where the failure happens), look in the file `test/Tests.hs`.
I Can't Do Problem X
--------------------
You can ask for help on Piazza or in office hours. If you're really stuck and
don't have time to fix it, you *must* still put in the type declaration and
define it as `undefined` so that it still compiles with our autograder. Not
doing so will result in loss of extra points from your total score. Remember
that course policy is that code which doesn't compile receives a zero.
For example, if you cannot complete problem `app :: [a] - [a] - [a]`, make
sure you put the following code into your submission:
``` {.haskell}
app :: [a] - [a] - [a]
app = undefined
```
Problems
========
Builtins:
: In general you cannot use the Haskell built-in functions. Especially if we
say that a function "should behave exactly like the Haskell built-in", *you
cannot use that Haskell built-in*.
__If you modify or remove the following two import statements your submission
will not be scored!__
```{.haskell}
import qualified Prelude as P
import Prelude hiding ( take, drop, ... etc ...
```
Pattern-matching:
: You should try to use pattern-matching whenever possible (it's more
efficient and easier to read). If you are using the functions\
`fst :: (a,b) - a` or `snd :: (a,b) - b` (for tuples)\
`head :: [a] - a` or `tail :: [a] - [a]` (for lists)\
chances are you can do it with pattern matching. We will take off points if
you use built-ins when it's possible to pattern-match.
Helpers:
: You may write your own helper functions (inside or outside a
`where` clause). All the restrictions about allowable code (no
built-ins/using pattern matching) still apply to your helper functions.
Part 1: Recursion and Higher-Order Functions
============================================
_include your definitions for the following problems in `mp1a-recursion/src/Lib.hs`_
Recursion
---------
For these problems, you *may not* use higher-order functions. Instead, you
should use recursion to implement the stated functionality. If you do use
higher-order functions (or do not use recursion), you will receive no points.
mytake
Write a function `mytake :: Int - [a] - [a]` which takes the first `n`
elements of a list, or the whole list if there are not `n` elements. It should
behave exactly like the Haskell built-in `take :: Int - [a] - [a]`.
``` {.haskell}
*Main mytake 4 [2,4,56]
[2,4,56]
*Main mytake 3 []
[]
*Main mytake 1 ["hello", "world"]
["hello"]
*Main mytake (-3) [1,2,3]
[]
```
mydrop
Write a function `mydrop :: Int - [a] - [a]` which drops the first `n`
elements of a list, or the whole list if there are not `n` elements. It should
behave exactly like the Haskell built-in `drop :: Int - [a] - [a]`.
``` {.haskell}
*Main mydrop 3 [2,4,56,7]
[7]
*Main mydrop 3 []
[]
*Main mydrop 1 ["hello", "world"]
["world"]
*Main mydrop (-3) [1,2,3]
[1,2,3]
```
rev
Write a function `rev :: [a] - [a]` which reverses the input list. To get
credit, your solution must run in linear time. If you use the `(++)` list append
operator, chances are your solution is running in quadratic time. This function
should behave exactly like the Haskell built-in `reverse :: [a] - [a]`.
``` {.haskell}
*Main rev [1,2,3]
[3,2,1]
*Main rev []
[]
*Main rev ["hello", "world"]
["world","hello"]
```
app
Write a function `app :: [a] - [a] - [a]` which appends two lists. This
function should behave like the Haskell built-in `(++) :: [a] - [a] - [a]`,
and should run in linear time (in the size of the first list).
``` {.haskell}
*Main app [] [1,2,3]
[1,2,3]
*Main app [1,2,3] []
[1,2,3]
*Main app [4,5] [1,2,3]
[4,5,1,2,3]
*Main app ["hello", "world"] ["and", "goodbye"]
["hello","world","and","goodbye"]
*Main app "hello" "world"
"helloworld"
```
inclist
Write a function `inclist :: Num a = [a] - [a]` which adds `1` to each element
of the input list.
``` {.haskell}
*Main inclist [1,2,3,4]
[2,3,4,5]
*Main inclist [-2,4,5,1]
[-1,5,6,2]
*Main inclist []
[]
*Main inclist [2.3, 4.5, 7.6]
[3.3,5.5,8.6]
```
sumlist
Write a function `sumlist :: Num a = [a] - a` which adds all the elements of
the input list.
``` {.haskell}
*Main sumlist []
0
*Main sumlist [1,2,3]
6
*Main sumlist [-3,2,5]
4
*Main sumlist [3.3,2.8,-1.2]
4.8999999999999995
```
myzip
Write a function `myzip :: [a] - [b] - [(a,b)]` which zips up the elements of
two lists. The resulting list should be the same length as the shorter of the
two input lists.
``` {.haskell}
*Main myzip [1,2,3] []
[]
*Main myzip [] [1,2,3]
[]
*Main myzip [1,2,3] ["hello", "world"]
[(1,"hello"), (2,"world")]
```
addpairs
Write a function `addpairs :: (Num a) = [a] - [a] - [a]` which zips up two
lists using the addition operator `(+)`. You *must use* your function `myzip`.
``` {.haskell}
*Main addpairs [1,2,3] []
[]
*Main addpairs [1,2,3] [4,5,6]
[5,7,9]
*Main addpairs [1.2,3.4] [-1.2,8.9,7.6]
[0.0,12.3]
```
ones
Write a (constant) function `ones :: [Integer]` which produces an infinite list
of the integer `1`.
``` {.haskell}
*Main take 15 ones
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
*Main take 0 ones
[]
```
nats
Write a (constant) function `nats :: [Integer]` which produces an infinite list
of all the natural numbers starting at `0`. It is OK for this function if you do
not use recursion.
``` {.haskell}
*Main take 15 nats
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
*Main take 0 nats
[]
```
fib
Write a (constant) function `fib :: [Integer]` which produces an infinite list
of the Fibonacci series starting with numbers `0` and `1`. You can (and should)
use your `addpairs` function here. This is the one place in the assignment where
it really makes sense to use `tail :: [a] - [a]`.
``` {.haskell}
*Main take 10 fib
[0,1,1,2,3,5,8,13,21,34]
*Main take 0 fib
[]
```
Set Theory
----------
We will be using Haskell lists to represent abstract mathematical sets. Recall
that in a set there are no duplicates, which means that our lists should have
that property as well. To make this simpler, we'll be storing *sorted* lists,
which means we can only create sets of things that are orderable (notice the
`Ord a` *type constraint* in the type declarations).
As long as your set-theoretic interface functions do not create duplicates and
always return sorted lists, then all of our nice set-theoretic properties will
hold. You may assume that the input sets (Haskell lists) to these functions will
also be sorted and will not contain duplicates.
You may use higher-order functions or recursion as you see fit in this section.
add
Write a function `add :: Ord a = a - [a] - [a]` which will add an element to
the set. Remember that it must add it in the correct place to ensure that the
list remains sorted. It should run in linear time (in the size of the list).
``` {.haskell}
*Main add 3 []
[3]
*Main add 3 [1,2]
[1,2,3]
*Main add 3 [1,3,5]
[1,3,5]
*Main add 3 [1,5,8,9]
[1,3,5,8,9]
*Main add "hello" ["goodbye", "world"]
["goodbye", "hello", "world"]
```
union
Write a function `union :: Ord a = [a] - [a] - [a]` which unions two input
sets (Haskell lists). This should look similar to the "merge" step of
merge-sort, and should run in linear time (in the added sizes of the input
sets). You *may* use the `add` function defined above, but if you do it probably
will *not* run in linear time, so it's probably better not to.
``` {.haskell}
*Main union [] []
[]
*Main union [1,2,3] []
[1,2,3]
*Main union [] [1,2,3]
[1,2,3]
*Main union [1,2,3] [1,2,3]
[1,2,3]
*Main union ["goodbye", "world"] ["humans", "smell"]
["goodbye", "humans", "smell", "world"]
```
intersect
Write a function `intersect :: Ord a = [a] - [a] - [a]` which intersects two
input sets. This should run in linear time (in the size of the input sets).
``` {.haskell}
*Main intersect [] [1,2,3]
[]
*Main intersect [1,2,3] []
[]
*Main intersect [1,2,3] [3,4,45,89]
[3]
*Main intersect ["cruel", "hello", "world"] ["good", "hello", "world"]
["hello", "world"]
```
powerset
Write a function `powerset :: Ord a = [a] - [[a]]` which calculates the
powerset of the input set. Because the output is also a set, it *must preserve
our set properties*, including that there are no duplicate elements and the
elements are lexicographically sorted. Using the functions `union` and `add`
that you've already defined is useful here.
``` {.haskell}
*Main powerset []
[[]]
*Main powerset [1,2]
[[],[1],[1,2],[2]]
*Main powerset ["goodbye", "hello", "world"]
[ [], ["goodbye"], ["goodbye", "hello"], ["goodbye", "hello", "world"]
, ["goodbye", "world"], ["hello"], ["hello", "world"], ["world"]
]
```
Higher Order Functions
----------------------
For these problems, you *must* use higher-order functions. No recursion allowed!
inclist'
Write a function `inclist' :: Num a = [a] - [a]` which increments each element
of an input list.
``` {.haskell}
*Main inclist' [1,2,3,4]
[2,3,4,5]
*Main inclist' [-2,4,5,1]
[-1,5,6,2]
*Main inclist' []
[]
*Main inclist' [2.3, 4.5, 7.6]
[3.3,5.5,8.6]
```
sumlist'
Write a function `sumlist' :: (Num a) = [a] - a` which adds all the elements
of the input list.
``` {.haskell}
*Main sumlist' []
0
*Main sumlist' [1,2,3]
6
*Main sumlist' [-3,2,5]
4
*Main sumlist' [3.3,2.8,-1.2]
4.8999999999999995
```
Part 2: Algebraic Data Types
============================
_include your definitions for the following problems in `mp1b-adts/src/Lib.hs`_
Algebraic Data Types
--------------------
If you haven't already you may want to read Chapter 8 of Learn you a Haskell,
[Making Our Own Types and
Typeclasses](http://learnyouahaskell.com/making-our-own-types-and-typeclasses).
If Chapter 8 is a little bit over your head, try out Chapter 3 [Types and
Typeclasses](http://learnyouahaskell.com/types-and-typeclasses) first.
We won't be making any Typeclasses in this MP, but we will be using and making
Types. Specifically, we'll be making Algebraic Data Types, because that's what
Haskell supports. Below are two Algebraic Data Types we supply for you to use in
this assignment.
``` {.haskell}
data List a = Cons a (List a)
| Nil
deriving (Show, Eq)
data Exp = IntExp Integer
| PlusExp [Exp]
| MultExp [Exp]
deriving (Show, Eq)
```
The above code declares two new *type constructors*, `List` and `Exp`. `List` is
a type constructor that takes one type as an argument (for example, if you said
`List Int` that would be a different type than `List String` or `List Double`).
`Exp` takes no type arguments.
It also declares several *data constructors*, two for `List a` and three for
`Exp`. Their types are given below:
``` {.haskell}
-- List data constructors
Cons :: a - List a - List a
Nil :: List a
-- Exp data constructors
IntExp :: Integer - Exp
PlusExp :: [Exp] - Exp
MultExp :: [Exp] - Exp
```
Notice how the above type declarations are written as if the data constructors
are *functions*. In fact, you can think of them as functions! `Cons` is a
function that takes two arguments, (an `a` and a `List a`) and constructs a
`List a`. If that doesn't make sense to you, perhaps you need to read Chapters 3
and 8 of Learn You a Haskell as mentioned above.
The nice thing about algebraic data-constructors is that we can *pattern match*
on them (see Chapter 4 of Learn You a Haskell for pattern matching). Suppose we
wanted to make a function `double :: List Int - List Int` which doubles each
element of the input list. We can just ask ourselves "what should we do for each
of the ways that a `List Int` can be constructed?"
``` {.haskell}
double :: List Int - List Int
double Nil = Nil
double (Cons i l) = Cons (2*i) (double l)
```
Notice here that I've told Haskell "if the list is constructed as a `Nil`, then
just produce `Nil` again" (this is the base-case). I've also told Haskell, "if
the list is constructed as a `Cons i l` (where `i :: Int`, `l :: List Int`),
then multiply the `i` by `2` and `double` the rest of the list" (the recursive
case). Because I've *exhausted* all of the data-constructors for `List Int`, I
*know* that Haskell will be able to apply `double` to any `List Int`. If you get
a "non-exhaustive patterns" error, it means you haven't told Haskell how to
handle all of the ways something of your input type can be constructed.
You'll be writing a few functions which manipulate the ADTs given above.
list2cons
Write a function `list2cons :: [a] - List a` which converts a Haskell list into
our `List` type. Do this recursively (not using higher-order functions).
``` {.haskell}
*Main list2cons []
Nil
*Main list2cons [3,2,5]
Cons 3 (Cons 2 (Cons 5 Nil))
*Main list2cons ["hello", "world"]
Cons "hello" (Cons "world" Nil)
*Main list2cons "hello"
Cons 'h' (Cons 'e' (Cons 'l' (Cons 'l' (Cons 'o' Nil))))
```
cons2list
Write a function `cons2list :: List a - [a]` which converts our `List` type
into the Haskell list type. Do this recursively.
``` {.haskell}
*Main cons2list Nil
[]
*Main cons2list (Cons 3 (Cons 4 Nil))
[3,4]
*Main cons2list (Cons "goodbye" (Cons "world" Nil))
["goodbye", "world"]
```
eval
Write a function `eval :: Exp - Integer` which evaluates the integer expression
represented by its input. You may use recursion and higher-order functions.
``` {.haskell}
*Main eval (IntExp 3)
3
*Main eval (PlusExp [])
0
*Main eval (MultExp [])
1
*Main eval (PlusExp [MultExp [IntExp 3, IntExp 5], PlusExp [IntExp 3], IntExp 5])
23
*Main eval (MultExp [IntExp 3, IntExp 45, IntExp (-2), PlusExp [IntExp 2, IntExp 5]])
-1890
```
list2cons'
Write a function `list2cons' :: [a] - List a` which converts a Haskell list
into our `List` type. You are required to use higher-order functions for this,
*no recursion*.
``` {.haskell}
*Main list2cons' []
Nil
*Main list2cons' [3,2,5]
Cons 3 (Cons 2 (Cons 5 Nil))
*Main list2cons' ["hello", "world"]
Cons "hello" (Cons "world" Nil)
*Main list2cons' "hello"
Cons 'h' (Cons 'e' (Cons 'l' (Cons 'l' (Cons 'o' Nil))))
```
BinTree
Write an ADT `BinTree a` which represents a binary tree that stores things of
type `a` at internal nodes, and stores nothing at the leaves.
You must add `deriving (Show)` to the `data` declaration so that GHCi can print
your datatype (as we've done above for `List a` and `Exp`). Not doing so will
result in a loss of points.
The data-constructors must have the following types (and names):
``` {.haskell}
Node :: a - BinTree a - BinTree a - BinTree a
Leaf :: BinTree a
```
sumTree
Write a function `sumTree :: Num a = BinTree a - a` which takes a `BinTree a`
(where `a` is a `Num`) from the previous problem and sums all the elements of
its nodes.
``` {.haskell}
*Main sumTree Leaf
0
*Main sumTree (Node 3 Leaf (Node 5 (Node 8 Leaf Leaf) Leaf))
16
*Main sumTree (Node (-4) Leaf Leaf)
-4
```
SimpVal
Write an ADT `SimpVal` which represents the values that a simple programming
language can have. We'll have `IntVal` for integers, `BoolVal` for booleans,
`StrVal` for strings, and `ExnVal` for exceptions.
You must add `deriving (Show)` to the `data` declaration so that GHCi can print
your datatype (as we've done above for `List a` and `Exp`). Not doing so will
result in a loss of points.
The data-constructors must have the following types (and names):
``` {.haskell}
IntVal :: Integer - SimpVal
BoolVal :: Bool - SimpVal
StrVal :: String - SimpVal
ExnVal :: String - SimpVal
```
liftIntOp
Write a function\
`liftIntOp :: (Integer - Integer - Integer) - SimpVal - SimpVal - SimpVal`\
which will take an operator over integers (like
`(+) :: Integer - Integer - Integer`) and turn it into an operator over
`SimpVal`s. If the inputs are not `IntVal`, raise an exception by returning
`ExnVal "not an IntVal!"`.
``` {.haskell}
*Main liftIntOp (+) (IntVal 3) (IntVal 4)
IntVal 7
*Main liftIntOp (*) (IntVal 2) (IntVal (-5))
IntVal (-10)
*Main liftIntOp (+) (BoolVal True) (IntVal 3)
ExnVal "not an IntVal!"
*Main liftIntOp (+) (IntVal 5) (StrVal "hello")
ExnVal "not an IntVal!"
*Main liftIntOp (+) (StrVal "hello") (ExnVal "not an IntVal!")
ExnVal "not an IntVal!"
```
