The overall objective of this assignment is to get some experience using the core features of functional programming, namely, Recursion, Datatypes and Higher-Order functions.
The assignment is in the following files that you will modify
Finally, Test.hs has some sample tests to be used
to check your assignments before submitting.
You should only modify the parts of the files which say:
error "fill this in"with suitable Haskell implementations.
You are free to write and use any helper functions.
Most of the points, will be awarded automatically, by evaluating your functions against a given test suite.
Tests.hs contains a very small suite of tests which gives you a flavor of of these tests. When you run
$ make testYour last lines should have
All N tests passed (...)
OVERALL SCORE = ... / ...
or
K out of N tests failed
OVERALL SCORE = ... / ...
If your output does not have one of the above your code will receive a zero
If for some problem, you cannot get the code to compile,
leave it as is with the error "fill me in" with your
partial solution enclosed below as a comment.
The other lines will give you a readout for each test. You are encouraged to try to understand the testing code, but you will not be graded on this.
To submit your code, just do:
$ make turninIf you are working in a group, make sure to update the file COLLABORATORS.md
with your group members, but each person must submit on their own.
In this problem, you can use only the following two library functions on lists: (++) and length.
(Feel free to use any library function that does not operate on lists.)
Fill in the implementation of clone such that clone n x returns
a list of n copies of x. When you are done, you should see the
following behavior:
>>> clone 5 'a'
"aaaaa"
>>> clone 3 "cat"
["cat","cat","cat"]Fill in the implementation of pad such that pad dir n x ys
"pads" the list ys with as many copies of x as needed to make
it exactly of size n. The dir parameter specifies whether the
copies of x should be added at the beginning (DirL) or at the
end (DirR).
When you are done, you should see the following behavior:
>>> pad DirL 10 0 [1,2,3,4,5]
[0,0,0,0,0,1,2,3,4,5]
>>> pad DirR 10 0 [1,2,3,4,5]
[1,2,3,4,5,0,0,0,0,0]
>>> pad DirL 3 0 [1,2,3,4,5]
[1,2,3,4,5]
>>> pad DirR 3 0 [1,2,3,4,5]
[1,2,3,4,5]Fill in the definition of isSubsequence such that
isSubSequence s1 s2 returns True if s1 can be
obtained by deleting some elements of s2.
When you are done, you should see the following behavior:
>>> isSubSequence "cat" "dog"
False
>>> isSubSequence "cat" "craptasticdog"
TrueFill in the implementation of maximum so that maximum d xs
returns the largest of d:xs.
When you are done, you should see the following behavior:
>>> maximum 99 []
99
>>> maximum 99 [90, 100, 200, 52]
200Fill in the definition of intersp such that
intersp s [x1,x2,...,xn] returns the list
[s, x1, s, x2, s, ..., xn, s].
When you are done, you should see the following behavior:
>>> intersp '|' "chewbacca"
"|c|h|e|w|b|a|c|c|a|"
>>> intersp "yo!" ["which", "way", "is", "the", "park"]
["yo!","which","yo!","way","yo!","is","yo!","the","yo!","park","yo!"]Fill in the definition of iter such that iter n f x
returns the result of calling f on x exactly n times, e.g.
iter 3 f xreturnsf (f (f x)), anditer 5 f xreturnsf (f (f (f (f x)))).
When you are done you should get the following behavior:
>>> iter 10 (\x -> 2 * x) 1
1024From this problem on, you are allowed to use any library functions you want.
You can also use functions you have implemented in previous problems.
However, please do not change the import statements at the top of the file:
we have already imported all the functions you need.
Fill in the implementation of rainbow so that when you
are done, running
>>> mkRainbowcreates a file img/rainbow.png that looks identical to
HINT: Read the documentation for overlay and circle from
the Graphics.Htdp library.
Fill in the implementation of chessBoard2 so that when you
are done, running
>>> mkChess2creates a file img/chess2.png that looks identical to
HINT: Make sure you understand the API in chessBoard1.
Fill in the implementation of triRec so that when you
are done, running
>>> mkTriangle1creates a file img/triangle1.png that looks identical to
HINT: You may find the Graphics.Htdp functions above and beside useful.
Fill in the implementation of sierpinskiTriangle2 so that when you
are done, running
>>> mkTriangle2creates a file img/triangle2.png that looks identical to
HINT: Make sure you understand the relation between iter and recursion.
Fill in the implementation of sierpinskiCarpet so that when you
are done, running
>>> mkCarpetcreates a file img/carpet.png that looks identical to
For this problem you will write a simple document layout engine, that allows the pretty printing of nested documents.
Thus, a document is a list of lines, each of which is a string. For example, the document
a
aa
aaa
aaaa
is represented as
>>> D ["a", "aa", "aaa", "aaaa"]We have also provided implementations of methods for computing
- the
heightof a document (the number of lines) - the
widthof a document (the maximum number of characters in a line)
Fill in the implementation of vcatL such that vcatL d1 d2
vertically concatenates the documents d1 and d2 aligning
their left sides.
When you are done, you should see the following behavior:
>>> (doc "cat") `vcatL` (doc "horse") `vcatL` (doc "mongoose")
cat
horse
mongooseFill in the implementation of vcatR such that vcatR d1 d2
vertically concatenates the documents d1 and d2 aligning
their right sides.
When you are done, you should see the following behavior:
>>> (doc "cat") `vcatR` (doc "horse") `vcatR` (doc "mongoose")
cat
horse
mongooseFill in the implementation of hcatT such that hcatT d1 d2
horizontally concatenates the documents d1 and d2 aligning
their top sides.
Suppose you have the following Doc values:
>>> aDoc
a
aaa
aaaaa>>> bDoc
b
bbb>>> lineDoc
<----- HEREWhen you are done with hcatT, you should see the following behavior:
>>> hcatT aDoc lineDoc
a <----- HERE
aaa
aaaaaand
>>> hcatT aDoc bDoc
a b
aaa bbb
aaaaaFill in the implementation of hcatB such that hcatB d1 d2
horizontally concatenates the documents d1 and d2 aligning
their bottom sides.
When you are done you should see the following behavior:
>>> hcatB aDoc lineDoc
a
aaa
aaaaa<----- HEREand
>>> hcatB aDoc bDoc
a
aaa b
aaaaabbbFinally, we will use Doc to build a command-line tool
called htree which does two tasks.
1. Showing the Sub-Directories
At the shell, executing
$ htree -ls src
produces the following tree-representation of the src
directory (of this repo).
src
├── CSE230
│ ├── Directory.hs
│ ├── Doc.hs
│ ├── Graphics.hs
│ ├── List.hs
│ └── Shapes.hs
├── Htdp
│ ├── Combinator.hs
│ ├── Data
│ │ └── Image.hs
│ ├── README.md
│ └── Shape.hs
└── Main.hs
2. Finding Files Matching a Pattern
At the shell, executing
$ htree -find src .hs
prints out the list of all the files (recursively) inside src
that match the substring .hs:
src/CSE230/Directory.hs
src/CSE230/Doc.hs
src/CSE230/Graphics.hs
src/CSE230/List.hs
src/CSE230/Shapes.hs
src/Htdp/Combinator.hs
src/Htdp/Data/Image.hs
src/Htdp/Shape.hs
src/Main.hs
We represent a directory via a datatype
data Dir a
= Fil a -- ^ A single file named `a`
| Sub a [Dir a] -- ^ A sub-directory name `a` with contents `[Dir a]`For example, the files in the src directory can be represented as:
srcDir :: Dir FilePath
srcDir = Sub "src"
[ Sub "CSE230" [ Fil "Directory.hs"
, Fil "Doc.hs"
, Fil "Graphics.hs"
, Fil "List.hs"
, Fil "Shapes.hs"
]
, Sub "Htdp" [ Fil "Combinator.hs"
, Sub "Data" [ Fil "Image.hs" ]
, Fil "README.md"
, Fil "Shape.hs"
]
, Fil "Main.hs"
]HINT: Take a look at the functions that Directory.hs imports from System.FilePath and System.Directory;
they will help you with some tasks in this problem.
Fill in the implementation of dirDoc that converts a Dir FilePath,
i.e. a directory where each name is a FilePath (i.e. String) into
a Doc value (from the previous problem). Your code should only use
the exported functions of the Doc module, i.e.
- the
docconstructor, and - the combinators
hcatT,hcatB,vcatLandvcatR.
HINT: You may find dash, stile , angle and bar useful.
When you are done, you should see the following behavior:
>>> dirDoc srcDir
src
├── CSE230
│ ├── Directory.hs
│ ├── Doc.hs
│ ├── Graphics.hs
│ ├── List.hs
│ └── Shapes.hs
├── Htdp
│ ├── Combinator.hs
│ ├── Data
│ │ └── Image.hs
│ ├── README.md
│ └── Shape.hs
├── Htdp.hs
└── Main.hs>>> dirDoc example
.
├── COLLABORATORS.md
├── LICENSE
├── Makefile
├── README.md
├── cse230-tree.cabal
├── out
│ ├── carpet.png
│ ├── chess1.png
│ ├── chess2.png
│ ├── rainbow.png
│ ├── triangle1.png
│ └── triangle2.png
├── src
│ ├── CSE230
│ │ ├── Directory.hs
│ │ ├── Doc.hs
│ │ ├── Graphics.hs
│ │ ├── List.hs
│ │ └── Shapes.hs
│ ├── Htdp
│ │ ├── Combinator.hs
│ │ ├── Data
│ │ │ └── Image.hs
│ │ ├── README.md
│ │ └── Shape.hs
│ ├── Htdp.hs
│ └── Main.hs
└── stack.yamlUnderstand and use foldDir to fill in the implementation
of allFiles dir which returns a list of all the files
in the directory dir.
When you are done, you should see the following behavior:
>>> allFiles example
["COLLABORATORS.md","LICENSE","Makefile","README.md","cse230-tree.cabal","carpet.png","chess1.png","chess2.png","rainbow.png","triangle1.png","triangle2.png","Directory.hs","Doc.hs","Graphics.hs","List.hs","Shapes.hs","Combinator.hs","Image.hs","README.md","Shape.hs","Htdp.hs","Main.hs""stack.yaml"]Understand and use foldDir to fill in the implementation of
allDirs dir which returns a list of all the sub-directories
in the directory dir.
When you are done, you should see the following behavior:
>>> allDirs example
[".","out","src","CSE230","Htdp","Data"]Understand and use foldDir to fill in the implementation of
findFiles sub dir which returns a list of all the files
in the directory dir such that sub is a subsequence
of the files' names.
When you are done, you should see the following behavior:
>>> findFiles ".hs" example
["./src/CSE230/Directory.hs","./src/CSE230/Doc.hs","./src/CSE230/Graphics.hs","./src/CSE230/List.hs","./src/CSE230/Shapes.hs","./src/CSE230/Directory.hs","./src/Htdp/Combinator.hs","./src/htdp/Data/Image.hs","./src/Htdp/README.md","./src/htdp/Shape.hs","./src/Htdp.hs","./src/Main.hs"]
Finally, complete the implementation of the function
build path that recursively traverses the filesystem
starting at path to build the Dir FilePath object
describing the filesystem's contents at path. (You
can ignore complexities like symbolic links etc.)
When you are done, you should see the following
behavior (assuming you have not added extra files
in your src/ directory!)
>>> build "src"
Sub "src" [Sub "CSE230" [Fil "Directory.hs", Fil "Doc.hs", Fil "Graphics.hs", Fil "List.hs", Fil "Shapes.hs"], Sub "Htdp" [Fil "Combinator.hs", Sub "Data" [Fil "Image.hs"], Fil "README.md", Fil "Shape.hs"], Fil "Htdp.hs", Fil "Main.hs"]Notice that the directories and files are listed in lexicographic order!
Finally, at this point, stack install should build and
install a standalone executable htree that you can then
run as described above:
$ htree -ls src
and
$ htree -find src .hs