!!! USING FUNCTIONAL F# !!!

!!! DO NOT USE LOOPS, MUTABLE VARIABLES, PATTERN MATCHING OR LIBRARY FUNCTIONS. ONLY RECURSION IS ALLOWED.!!!

• Allowed functions: List.head, List.tail, List.isEmpty

Problem 1

The formula for the nth Tribonacci numbers T_n is defined as follows:

• T_0 = 0
• T_1 = 1
• T_2 = 1
• T_n = T_{n-1} + T_{n-2} + T_{n-3}

Your task is to implement a recursive function tribn which accepts an integer n (you may assume that n >= 0), and computes the nth Tribonacci number (dont worry about efficiency, only about making the definition as simple as possible).

Problem 2

A more efficient version of the function for computing Tribonacci numbers can be defined by following three steps:

1. Implement a function which takes a list of integers and adds the sum of the top four elements to the head of the list (e.g., in F#, 1::1::1::[] should become 3::1::1::1::[]).
2. Implement a recursive function which computes the nth Tribonacci number in linear time. This function may use a linear amount of space to compute its result, but the number of recursive calls it makes must be linear in n.

Your task is to follow the three steps above, in order to implement the recursive function tribn2 in F#.

• Hint: Try to define auxiliary functions first before taking on tribn2 function. You do not have to use auxiliary functions in your tribn2, but they provide an insight on how to implement the tribn2 function.

Problem 3

Write a function last that returns the last element of a list. Your function may assume that the list is non-empty.

Problem 4

Write a function fourth int list -> int that takes an int list and returns the fourth element of that list, if such an element exists. If the list has fewer than four elements, return 0.

Problem 5

Write a function everyfourth : int list -> int list that takes an int list and returns every fourth element of that list, if such an element exists. If the list has fewer than four elements, return empty list.

Problem 6

Write a function take : int -> int list -> int list such that take n lst returns the first n elements of lst. If lst has fewer than n elements, return all of them.

Problem 7

Write a function drop : int -> int list -> int list such that drop n lst returns all but the first n elements of lst. If lst has fewer than n elements, return the empty list.