Question $5$

Write each of the following functions on linked lists in Haskell or Julia using recursion. No

loops, higher$-$order functions, or list comprehensions can be used in the implementations. For

Julia, the linked list data structure is defined as follows:

mutable struct ListNode

data

next: :Union$\{$Nothing$,$ ListNode$\}$

end

LinkedList $=$ Union$\{$Nothing$,$ ListNode$\}$

harmonic$($n$)$: This function returns a list that contains the first $n$ items in the harmonic

series: $1,\frac{1}{2},$dots,$\frac{1}{n}.$

iterate$\_$upto$(f,a,n)$: The $($iterate $f$ a$)$ function in Haskell generates an infinite

list, where the first item is a$,$ the next one is calculated by applying the function $f$ on

the previous item, and so on$.$ The function iterate$\_$upto $(f,a,n)$ is similar to the

iterate function except that it only returns the first $n$ items. For example, the function

defined below returns the first $n$ rows of the Pascal's triangle:

draw$\_$pascal $n=$

iterate$\_$upto $(1$ row $$ zipWith $(+)(0$:row$)($row $++[0]))[1]$ n

gen $($int $n)($extra $5$ points$)$: This function returns a list of all possible $n-$character strings

of a$\text{'}$s and b$\text{'}$s that do not contain the substring aaa. The order of the strings in the list

is not important.