Homework 8 — Programming Language Paradigms

Objective

Practice with functional programming in Haskell.

Due Date

Beginning of class session 19.

Tasks

Your programming for this assignment must be done in the folder HaskellFolding, in the file folders.hs, within your local copy of your SVN repository. For each task you must use exactly the function names given. This is so we can efficiently grade your and your classmates' work.

A testing function, test, is provided. Uncomment lines in the body of this function as you complete your work.

Trees and the Maybe type:

Implement and test a function, depth, that finds the first node whose value satisfies the predicate in a pre-order traversal of the tree. It then returns the depth of that node. It returns Nothing if the node isn't found. For example:

depth odd (buildTree [] []) == Nothing
depth odd (buildTree [1] [1]) == Just 0
depth odd (buildTree [2,1] [1,2]) == Just 1

depth odd (buildTree [0,1,2,3] [1,0,3,2]) == Just 1
depth odd (buildTree [0,4,2,3] [4,0,3,2]) == Just 2

depth (>5) (buildTree [0,4,2,3] [4,0,3,2]) == Nothing
depth (>0) (buildTree [0,4,2,3] [4,0,3,2]) == Just 1

depth (==0) (buildTree [0,4,2,3] [4,0,3,2]) == Just 0
depth (==2) (buildTree [0,4,2,3] [4,0,3,2]) == Just 1
depth (==3) (buildTree [0,4,2,3] [4,0,3,2]) == Just 2
depth (==1) (buildTree [0,4,2,3] [4,0,3,2]) == Nothing
depth (==4) (buildTree [0,4,2,3] [4,0,3,2]) == Just 1

Don't actually change the code, but explain (in a comment added to your program) how you could change your solution to return the depth of the shallowest matching node.

Implement and test a function, factors, that takes a list of integers and returns a list of lists, where each sublist contains the factors of the corresponding value from the original list. For example:
```
factors [10] == [[1,2,5,10]]
factors [3..9] == [[1,3],[1,2,4],[1,5],[1,2,3,6],[1,7],[1,2,4,8],[1,3,9]]
factors [] == []
```
Hints: Try to use library functions (like map, filter, and others) to your advantage. Think about helpers with names like factor or evenlyDivides. You may find you can simplify to eliminate some of these helpers once you've worked out the logic.
BONUS: Use your factors function to create a new function, primes, that generates an infinite list of prime numbers. Can you do it with a single line of library functions? My definition is 59 characters long, with reasonable spaces to make it readable.
Consider the library function, intersperse, that takes an element and a list and returns a new list where every other element is from the original list or is the new element. For example:
```
intersperse ',' "" == ""
intersperse ',' "abcd" == "a,b,c,d"
```
1. Implement and test a recursive (but not tail recursive) version of intersperse, call it intersperseR
2. Implement and test a tail-recursive version of intersperse, call it intersperseTR
3. Implement and test a version of intersperse using foldr, call it intersperseFR. Here's a skeleton that you can use:
```
intersperseFR :: a -> [a] -> [a]
intersperseFR i xs = case (foldr op [] xs) of
                         [] -> []
                         r -> init r
                     where op x acc = -- To be completed --
```
The library function dropWhile takes a predicate function and a list. It discards elements from the head of the list that match the predicate. When a non-matching element is found, the remainder of the list, including that element, is returned. For example:
```
dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3]
dropWhile (< 9) [1,2,3] == []
dropWhile (< 0) [1,2,3] == [1,2,3]
```
1. Implement and test a recursive version of dropWhile, call it dropWhileR.
2. Implement and test a version of dropWhile using foldl, call it dropWhileFL. Here's a sample derivation of my implementation that might be informative:
```
dropWhileFL odd [1,4,7]
	== reverse (foldl op [] (1:4:7:[]))
	== reverse (foldl op (op 1 []) (4:7:[]))
	== reverse (foldl op (op 4 (op 1 [])) (7:[]))
	== reverse (foldl op (op 7 (op 4 (op 1 []))) [])
	== reverse (          op 7 (op 4 (op 1 [])))
	== reverse (          op 7 (op 4 []))
	== reverse (          op 7 (4:[]))
	== reverse (          7:4:[])
	== [4,7]
```
3. Could one implement a version of dropWhile using foldr? What's the issue with trying to do so? (Put your answer in a comment in the file.)

Turn-in Instructions

Turn in your work by committing it to your SVN repository.