A good way to get the workings of functions, particularly recursive functions, e

Question

A good way to get the workings of functions, particularly recursive functions, established in one’s mind is to walk through the function evaluation step by step. For example, consider the code shown in class for the function to compute the length of a list:

let rec length l =

                match l with

                | [ ] -> 0

                | _::t -> 1 + length t;;

Below are the steps taken in evaluating this function for a particular list:

length [1; 2; 3]

=>           1 + length [2; 3]

=>           1 + (1 + length [3])

=>           1 + (1 + (1 + length [ ]))

=>           1 + (1 + (1 + 0))

=>           1 + (1 + (1))

=>           1 + (2)

=>           3

Now consider an alternate form of the length function:

let rec length_inner l n =

                match l with

                | [ ] -> n

                | h::t -> length_inner t (n + 1);;

let length l = length_inner l 0;;

The steps taken in evaluating this function for the same list as above are:

length [1; 2; 3]

=>           length_inner [1; 2; 3] 0

=>           length_inner [2; 3] 1

=>           length_inner [3] 2

=>           length_inner [ ] 3

=>           3

Q1. Consider this pair of functions which we also discussed in class:

let rec merge x y =

                match x, y with

                | [], l -> l

                | l, [] -> l

                | hx::tx, hy::ty ->

                                if hx < hy

                                then hx :: merge tx (hy :: ty)

                                else hy :: merge (hx :: tx) ty;;

let rec msort l =

                match l with

                | [] -> []

                | [x] -> [x]

                | _ ->

                                let left = take ((length l) / 2) l in

                                                let right = drop ((length l) / 2) l in

                                                                merge (msort left) (msort right);;

Write out the step-by-step evaluation of the following expression:

msort [ 27; 13; 3; 9; 17]

Do not show the steps in evaluating the length, take, and drop functions (the code for which is on the slides presented in class). Simply use the results of those functions but show all the steps in the evaluation of the merge and msort functions. Type out each step of the evaluation in the same format as the examples shown on the previous pages.

Q2 START HERE

Q2. Consider the function below which reverses the ordering of a list. It was provided by some you in as response to an earlier homework question.

let rev list =

let rec aux acc = function

    | [ ] -> acc

    | h::t -> aux (h::acc) t in

aux [ ] list;;

Show the step-by-step evaluation of this function for the expression below. Within this evaluation, include the step-by-step evaluation of the embedded helper function as well.

rev [15; 7; 18; 9; 26]

Type out all the steps of the evaluation in the same format as the examples shown on the previous pages.

Submit your response in the form of a MS Word document or PDF document. Answer each of the two questions on a separate page (or separate set of pages). Show the question or question number on the top of the page where you begin your answer.

Explanation / Answer

Solution:

1)

So the program will start with the input [27; 13; 3; 9; 17]

msort [27; 13; 3; 9; 17]

now this will be divided into two [27; 13; 3], and [9; 17]

msort [27; 13; 3]

this will also divided into two [27; 13], and [3]

msort [27; 13] wiil be divided into [27], and [13]

merge [27], [13]

=> [13, 27]

merge [3], [13, 27]

=> [3; 13; 27]

msort[9; 17] will dicideed into [9], and [17]

merge[9], [17]

=> [9; 17]

merge [3; 13; 27], and [9; 17]

=> [3; 9; 13; 17; 27]

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.