CSCI 2041 Lab02: Recursion on Lists

			   __________________

			    LAB 02 QUESTIONS
			   __________________


- Name: (FILL THIS in)
- NetID: (THE kauf0095 IN kauf0095@umn.edu)

Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.


PROBLEM 1: last_elem recursive function
=======================================

(A)
~~~

  Start the OCaml REPL in the `lab02-code' directory and load the
  `rec_funcs.ml' source file with a `#use' directive as shown.

  ,----
  | > ocaml
  |     OCaml version 4.06.0
  | 
  | # #use "rec_funcs.ml";;
  | val last_elem : 'a list -> 'a = <fun>
  | val elems_outside : int -> int -> 'a list -> 'a list = <fun>
  | #
  `----

  The first function loaded from the source file is called `last_elem'.

  Describe in words the type of `last_elem' :
  - What kind of argument does it take?
  - What type does it return?
  - What does the 'a notation mean?


(B)
~~~

  Call `last_elem' on several input lists in the REPL and show the
  return values.
  - Make sure to call the function on an empty list and report what
    happens.
  - Make sure to use several different types of lists (int list, string
    list) and a few different lengths.

  Paste your REPL transcript below AND describe in a line or two what
  the function does.


(C)
~~~

  Examine the definition of `last_elem' in `rec_funcs.ml'. Study how it
  operates carefully to gain insight on recursive functions.

  Add comments in your own words that describe line-by-line how the
  function operates. Paste your commented version of the code below.


PROBLEM 2: elems_outside with recursive helper function
=======================================================

(A)
~~~

  The other function loaded by `rec_funcs.ml' is called `elems_outside'.
  As before, describe it's type.
  - How many parameters does it take and what type are they?
  - What type does it return?


(B)
~~~

  In the REPL, call `elems_outside' on several lengths and types of
  lists. Show the results generated by these calls by pasting your REPL
  session below. Describe what the function appears to be doing.


(C)
~~~

  Examine the definition of `elems_outside' in `rec_funcs.ml'. Study how
  it operates carefully to gain insight on recursive functions.

  Add comments in your own words that describe line-by-line how the
  function operates. Paste your commented version of the code below.


Problem 3
=========

(A)
~~~

  Examine the two functions provided in `sorting.ml': `sorted_insert'
  and `sort'. Describe the parameter and return types for both
  functions. Based on the comments and source code, determine their
  purpose.


(B)
~~~

  The code provided for this problem is an adaptation of code from the
  Ocaml System Manual Section 1.2 which is here
  [http://caml.inria.fr/pub/docs/manual-ocaml/coreexamples.html#sec9]

  The original version looks like this:
  ,----
  | let rec sort lst =
  |   match lst with
  |     [] -> []
  |   | head :: tail -> insert head (sort tail)
  | and insert elt lst =
  |   match lst with
  |     [] -> [elt]
  |   | head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
  | ;;
  `----

  The version in `sorting.ml' has been re-written so that it is somewhat
  more verbose but potentially easier for a novice to understand.
  - Ordering of the functions is reversed so that insertion is defined
    prior to sorting
  - Two separate "let" bindings are used rather than a joint "let/and"
    binding
  - Pattern matching via "match" is replaced with "if/else" statements
  - Destructure binding is replaced with explicit calls to List.hd and
    List.tl

  All of the above concepts will eventually be covered and it does not
  hurt one to look ahead a bit.

  COMPARE the code in `sorting.ml' to the original OSM version above.
  Make some observations about how the syntax associated with the
  "match" statement must work.