Module 12 Lab

Create a directory named lab12 and a file in it named lab12.hs.
In your file, write a function called listOf4 that takes four parameters and combines them into a list, so that, for example, listOf4 3 1 6 7 is [3,1,6,7]. Load this file into ghci and make sure it works, then use :t to determine its type. Unsurprisingly, it should be listOf4 :: a -> a -> a -> a -> [a]. We have talked before about how in the type signature, the last type is the function result and all the rest are the parameter types. But why all the arrows? Actually, the arrows indicate functions, and they are right associative. Thus the type of listOf4 is really a -> (a -> (a -> (a -> [a]))), and this says that listOf4 takes a parameter of type a and returns a function. This result function takes a parameter of type a and returns a function. This result function takes a parameter of type a and returns a function. This result function takes a parameter of type a and returns a list of values of type a. This idea of thinking of a function of multiple parameters as really a function of a single parameter returning another function of a single parameter, which itself returns a function of a single parameter, and so on, is called currying, named after Haskell Curry (yes, that Haskell). (Curry did not actually come up with currying, but it is named after him anyway.)
Functions are represented internally in Haskell as curried functions. So, for example, listOf4 8 returns a function. This function tacks on an 8 at the start of a list of three elements that it makes into a list. So we could define the function listOf4With8 = listOf4 8; similarly, we can make the function listOf4With88 = listOf4 8 8. And so on. Try them and see. To call the functions in ghci, you’ll need to supply all “missing” elements.
So what? This has a consequence that is useful for defining functions. If we have a function of several parameters and need a function just like it but with some of the parameters fixed, we can make one out of it by currying. For example, we might define a double function as double n = 2*n. But with currying, we can just define this as double = (2*). Try it.
Functions are first-class entities in Haskell. This means that they can be returned as results (which is what currying does). This also means that they can be parameters. Suppose we want to do something to every element of a list. For example, suppose we want to double every element of a list. We could make the following definition.
```
doubleList [] = []
doubleList (n:ns) = double n : doubleList ns
```
This works fine, as you will see if you try it.
But suppose we want to triple every element of a list, or do something else to every element of a list? Then we have to write another function every time. But what if defined a function like the following?
```
applyToList :: (a -> a) -> [a] -> [a]
applyToList _ [] = []
applyToList f (n:ns) = f n : applyToList f ns
```
Notice the type signature: applyToList takes a function as its first argument, followed by a list, and returns a list. The definition makes clear that applyToList forms a new list by applying the argument function f to every element of the argument list. Now we can evaluate the expressions applyToList double list, applyToList triple list, and so forth, in ghci.
We don’t need to write our own functions to do this. And since we have currying, we don’t even have to write the double and triple functions. We can write things like the following.
```
applyToList (2*) [1..10]
applyToList (3*) [1..10]
```
Try these expressions in ghci and see. Write code to generate the remainder of the numbers from 1 to 20 when divided by three.
It should not be a surprise that Haskell already has a function like applyToList. It is called map. Use :t to find the type of map. Note that it has a slightly different type than applyToList. This is because you can map a function that produces values of a type different from its argument type. For example, try map odd [1..10] in ghci.
Use map to generate a list of the lengths of a list of strings.
Haskell has other very useful functions that have functions as arguments (sometimes called higher-order functions). You’ve already seen filter, which selects elements from a list based on a test function. The built-in filter function has type filter :: (a -> Bool) -> [a] -> [a]. The first argument is a test function (or predicate) applied to every element of a list. If this test function returns True, then the element is part of the result list; otherwise it is tossed out. For example, filter odd [1..10] returns a list of odd numbers between 1 and 10.
Write a function partitionLess :: Ord a => a -> [a] -> [a] that takes a value v and a list t and returns a list of elements of t that are less than or equal to v. Now write a function partitionMore :: Ord a => a -> [a] -> [a] that returns the elements of t greater than v.
Now write quicksort using your partition functions. Recall that quicksort operates by selecting one of the elements to be a pivot and partitioning the remaining elements into two groups: those smaller than the pivot and those larger. Quicksort then recursively sorts those two lists and then assembles a final (sorted) list using the results of those recursive sorts and the original pivot element. Implement quicksort using your partition functions (hint: just use the head of the list as the pivot).
Haskell function bodies are a single expression. This is very different from what you’ve experienced in imperative languages in which you can write long sequences of statements. When you are constrained to a single line, the code can become hard to read. Restore readability using Haskell’s where clause. With where, you factor out subexpressions and assign their values to local variables. Consider this function that computes the average of a list of numbers and does not use where:
```
average xs = sum xs / (fromIntegral (length xs))
```
Contrast this implementation that uses where to introduce local variables total and n:
```
average xs = total / n
  where total = sum xs
        n = fromIntegral (length xs)
```
The indentation is significant.

The partitionLess and partitionMore functions do not need to be global. Rewrite your quicksort function so that they are local.
Rewrite quicksort so that it uses operators and currying instead of named partition functions.
We have discussed various types, and sometimes they can be quite complicated. Haskell provides a way to abbreviate types for ease of typing and documentation purposes. The statement type T = <def> can be used to define a new type. For example, type String = [Char] defines a String to be a list of Char. This definition is already built into Haskell, so we could have been doing this all along.
Type definitions can also have parameters. For example, type Pair a = (a,a) defines Pair to be a two-tuple of something (because we used a type variable, the contained type is not constrained). Pair Int would then be an abbreviation for (Int,Int), Pair String an abbreviation for (String,String), etc.
We can get values “out of” a composite data type using pattern matching. For example, the pattern (p, q) would match an instance of Pair, and we can use p and q to refer to the values “inside” the Pair. Note that we have already been using patterns ([] and (x:xs)) to write list-based functions.
Write a function pairToList :: Pair a -> [a] to convert a pair of two items to a list containing those two items.
Write a function pairUp :: Pair [a] -> [Pair a] to convert a pair of lists into a list of pairs. For example, pairUp ([1,2,3],[4,5,6]) should return [(1,4),(2,5),(3,6)].
Function application has high precedence and it is left associative. This can lead to lots of parentheses, such as odd (mod 8 (div 9 3)). The $ operator is right associative, has lower precedence than function application, but means the same as function application (so f $ x means the same as f x). Since we have currying, we can use it to eliminate some parentheses: odd $ mod 8 $ div 9 3.
We can also define new types in Haskell using algebraic data types. For instance, we could define a type that is either a single number or a range using the following declaration.
```
data Movement
  = North Int
  | South Int
  | East Int
  | West Int
  deriving (Show)
```
Here, North, East, South, and West are called value constructors and are essentially functions that can be used to create new values of type Movement. What is the type of North? What is the type of North 5?

You can use the case structure to pattern-match against algebraic data types. Consider this function move, which updates an xy-coordinate pair based on the movement:

move :: (Int, Int) -> Movement -> (Int, Int)
move (x, y) movement = case movement of
  North delta -> (x, y + delta)
  South delta -> (x, y - delta)
  East delta  -> (x + delta, y)
  West delta  -> (x - delta, y)

Alternatively, you can write this using pattern-matching in the movement parameter:

move :: (Int, Int) -> Movement -> (Int, Int)
move (x, y) (North delta) = (x, y + delta)
move (x, y) (South delta) = (x, y - delta)
move (x, y) (East delta)  = (x, y + delta)
move (x, y) (West delta)  = (x, y - delta)

Write function mirror that flips a movement to its opposite. For example, mirror (North 5) yields South 5.
Data types in Haskell can be recursive, which means that they can contain nested values. Here is an example.
```
data Tree
  = Empty
  | Node Int Tree Tree
  deriving (Show, Eq)
```
In other words, a Tree is either empty or it is a binary tree node that contains an integer and two more (sub) Trees. Here the deriving (Show, Eq) indicates that we would like default definitions provided so that we can call show (for string output) and use the equality operator.

Now we can define a function that generates a binary search tree from a list as follows.

toBst :: [Int] -> Tree
toBst [] = Empty
toBst (x:xs) = Node x (toBst smallers) (toBst biggers)
  where smallers = filter (<= x) xs
        biggers = filter (> x) xs

Run toBst [1,2,3,4] and observe how its output is different from toBst [4,3,2,1].

Write a function find :: Int -> Tree -> Bool that takes an integer and a binary search tree and returns True or False indicating whether or not the integer is present in the tree. This routine should run in O(log n) time if the tree is balanced, and should be considerably simpler than toBst.
Write a function sorted :: Tree -> [Int] that takes a binary search tree and returns a sorted list of integers in the tree.
Write a function countNodes :: Tree -> Int that takes a binary search tree and returns the number of integer nodes in the tree.
Write a function countInternalNodes :: Tree -> Int that takes a binary search tree and returns the number of internal nodes in the tree. An internal node has at least one child. The empty sentinel nodes do not count as children.

This lab was originally written by Dr. Chris Fox and expanded by Dr. Mike Lam and Dr. Chris Johnson.

JMU CS 430 Spring 2022

Programming Languages

Module 12 Lab