# Exercise 4

For this exercise, put all of your function definitions in a file exer4.hs.

You must include an appropriate type declaration (::) for each function you define in your exer4.hs.

## Hailstone, Again

Let's look once more at the hailstone function from exercise 1. The one thing we haven't done is actually generate the sequence. Write a recursive function hailSeq that uses your hailstone function and generates the hailstone sequence starting with its argument and ending with one.

*Main> hailSeq 1
[1]
*Main> hailSeq 11
[11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> hailSeq 6
[6,3,10,5,16,8,4,2,1]


### Non-recursive

Write another implementation, hailSeq' that produces the same results. It must not be recursive and use the iterate function (and whatever else you need to get the results).

## Joining Strings, Again

Rewrite your function join from exercise 2 so that it uses a fold operation (foldr or foldl or maybe foldl1 function or foldr1 function) and is not recursive. It should still behave the same in all cases:

*Main> join ", " ["one","two","three"]
"one, two, three"
*Main> join "+" ["1","2","3"]
"1+2+3"
*Main> join "X" ["abc"]
"abc"
*Main> join "X" []
""


The empty list might have to be a special case, or you might have to use a fold and then clean up the result.

## Merge Sort

Use your merge function from exercise 3 to implement merge sort. That is, split the list you are given into two halves, recursively sort each half, and merge the halves.

*Main> mergeSort [1,9,3,2,7,6,4,8,5]
[1,2,3,4,5,6,7,8,9]
*Main> mergeSort [6,2,4,8,9,5,3,1,7,10]
[1,2,3,4,5,6,7,8,9,10]
*Main> mergeSort []
[]
*Main> mergeSort [4]
[4]
*Main> mergeSort "The quick brown fox jumps over the lazy dog."
"        .Tabcdeeefghhijklmnoooopqrrstuuvwxyz"


## Searching? Maybe?

In this question, you will explore the Maybe type (which you need for assignment 1). A Maybe can be wrapped around any type and the values can either be Nothing or Just a value of that type. For example, these are some values of type Maybe Int:

Just 6
Just (-34)
Nothing


The idea behind Maybe is to handle things that might cause errors/null pointers in other languages. Basically, a function that returns a Maybe is saying “if I find an answer, I'll give it to you (wrapped in Just), but I might not find anything (Nothing)”.

Write a function findElt that returns (Just) the first position of an element in a list if it's there, and Nothing if it's not:

*Main> findElt 8 [4,5,2,8,7,3,1]
Just 3
*Main> findElt 6 [4,5,2,8,7,3,1]
Nothing
*Main> findElt 'o' "Hello World!"
Just 4
*Main> findElt 'q' "Hello World!"
Nothing


The Data.Maybe library library has some functions that might be useful. Also note that you can pattern-match on Just/Nothing values, so this is possible:

case maybeValue of
Nothing -> …
Just x -> …


(That might be useful, or not. I have a possible solution that uses a case, and another that uses functions from Data.Maybe. There are plenty of ways to do this.)

For this question, you have to actually do the searching yourself. i.e. no cheating with element-finding functions from Data.List or anywhere else.

## Submitting

Submit your files through CourSys for Exercise 4.

Updated Fri April 17 2020, 09:40 by ggbaker.