CS341-Project 1 Implement 16 Small F# Functions Solved

In Project 1 you’re going to write 16 small functions on list operations both provided by the standard library and useful utility functions. 

Programming Exercise
Each function should be written in a separate file.  We have provided the template code in each file, with comments describing the behavior of the code, the function declaration (you may write additional functions as desired, but the computation must begin by invoking the function as given) and some sample code that tests the function you have written against a couple of test cases.  Instructions for the behavior of each function are included in the comments of the template code, and a copy of the template for each function has been included in this document (though using the files directly from the zip should give you less spacing/nonprinting character errors). 

 

YOU MAY NOT INVOKE THE FUNCTION OF THE SAME NAME FROM THE LIST LIBRARY IN YOUR SOLUTION. 

 

Exercise #01: length L 
The first function to write, length (which you have already written in Homework 6), returns the length of the list passed in a s a parameter and should be written in the Project01-01.fs file.   

 

// 

// length L 

// 

// Returns length of L 

//  

// Examples: length []  = 0 

//           length [1] = 1 

//           length [1; 3; 98] = 3 

//           length [1; 2; 19; 67] = 4 

//           length ['a'; 'b'; 'c'; 'd'; 'e'] = 5 

//           length ["List"; "of"; "strings"] = 3 // 

 

Exercise #02:  max L  
The function max returns the value of the maximum element (as determined by the operator), and should be written in the Project01-02.fs file. 

 

// 

// max L 

// 

// Returns maximum element of L 

//  

// Examples: max []          = raises an exception (Unhandled Exception: System.ArgumentException: The input sequence was empty.) //           max [-2; 4]     = 4 

//           max [34]        = 34 

//           max [10; 10; 9] = 10 

//           max ['a'; 'e'; 'c'] = e // 

 

Exercise #03:  min L  
The function min returns the value of the minimum element (as determined by the < operator), and should be written in the Project01-03.fs file. 

 

// 

// min L 

// 

// Returns minimum element of L 

//  

// Examples: min []          = raises an exception (Unhandled Exception: 

System.ArgumentException: The input sequence was empty.) 

//           min [-2; 4]     = -2 

//           min [34]        = 34 

//           min [10; 9; 9; 101] = 9  

//           min ['d', 'r', 'b'] = b // 

 

Exercise #04:  nth L n 
The function nth returns the value of the element at index n of the list and should be written in the Project0104.fs file. 

 

// 

// nth L n 

// 

// Returns nth element of L 

//  

// Examples: nth []   0       = raises an exception //           nth [94] 2       = raises an exception 

//           nth [94]  0      = 94 

//           nth [94]  -1     = raises an exception  

//           nth [1; 45; 6] 1 = 45 

//           nth [1; 45; 6] 5 = raises an exception 

//           nth ['q'; 'w'; 'e'; 'r'; 't'; 'y'] 5 = 'y' 

// You may not call List.nth, List.Item, .[], etc directly in your solution. // 

 

Exercise #05:  map F L 
The function map returns a new list created from the elements of the list passed in (L), after they have been transformed by the application of function F.  This function does not modify the original list, creating a brand new list one element at a time.  The map function should be written in the Project01-05.fs file 

 

// 

// map F L 

// 

// Maps function F to L - Returns list produced by mapping function F over L //  

// Examples: map (fun x - x + 1) []                  = [] 

//           map (fun x - x + 1) [23]                = [24] 

//           map (fun x - x - 1) [23; 43]            = [22; 42] 

//           map (fun x - x - 1) [23; 43]            = [22; 42] 

//           map (fun i - (char i)) [99; 97; 115; 116] = ['c';'a';'s';'t'] 

//           map (fun c - (char ((int c)+1))) ['a';'b';'c']  = ['b';'c';'d'] // 

 

Exercise #06:  iter F L
The function iter behaves like map, but instead of building a new list from the elements of L, applies F and then throws away the result.  This is generally used only for functions which have side-effects, such as printing functions which do not change memory, but have the side effect of outputting to the screen.  The iter function should be written in the Project01-06.fs file. 

 

// 

// iter F L 

// 

// Applies function F to the elements of L 

//  

// Examples: iter (fun x - printfn "%A squared is %A" x (x*x) ) [1; 2] = 1 squared is 1 //                                                                         2 squared is 4 

//           iter (fun x - printf "%c" x) ['t'; 'r'; 'u'; 'e']     = true 

//           iter (fun x - printfn "Iterating...") []              =  // 

 

Exercise #07:  reduce F L
The function reduce takes a binary function, and pairwise applies the function to the elements of the list.  The first application of the function takes the first and second elements as parameters, each following application uses the result of the previous application as the first parameter, and the next element of the list as the second parameter.  The reduce function should be written in the Project01-07.fs file.   

 

// 

// reduce F L 

// 

// reduces L to a single value by applying function F 

//  

// Examples: reduce (fun x y - x+y) []             = Unhandled Exception: 

System.ArgumentException: The input list was empty. 

//           reduce (fun x y - x*y) [23; 4]        = 92 

//           reduce (fun x y - x+y) [23; 43; -60]  = 6  

//           reduce (fun x y - if x y then x else y)  

//                  ['c'; 'a'; 'n'; 'a'; 'd'; 'a']  = 'n'  // 

 

Exercise #08:  fold F start L
The function fold applies a function f to each element of the collection by threading an accumulator argument through the computation.  What this means is that the first parameter of the function initially has the value passed in to the accumulator, and then the result of each application of the function between the accumulator and an element of the list becomes the new accumulator for the next step.  These “updates” to the accumulator are accomplished via new values to the parameter for each function invocation.  The fold function should be written in the Project01-08.fs file.  

 

// 

// fold F accumulator L // 

// Applies a function f to each element of the collection, threading an accumulator argument through the computation. 

// 

// Returns a value  

//  

// Examples:  

//          fold (fun x y - x&&y) true [] = true 

//          fold (fun x y - x+(string y)) "Hello " ['W';'o';'r';'l';'d'] = "Hello World" 

//          fold (fun x y - x+y) -60 [23; 43; 6] = 12 

//          fold (fun x y - x*y) 1 [23; 5; 80] = 9200 //           

 

Exercise #09:  flatten L
The function flatten takes a list of lists, and puts the elements all together into a single list.  The flatten function should be written in the Project01-09.fs file. 

 

// 

// flatten L 

// 

// Flatten a list of lists to a single list 

// 

// Returns list  

//  

// Examples:  

//          flatten [[]] = [] 

//          flatten [[1]] = [1] 

//          flatten [[1; 2]; [2; 3; 4]] = [1; 2; 2; 3; 4] 

//   flatten [['o'; 'n']; [' ']; ['w'; 'i'; 'n'; 'g'; 's']] =  //      ['o'; 'n'; ' '; 'w'; 'i'; 'n'; 'g'; 's'] 

// 

 

Exercise #10:  zip L1 L2
The function zip combines the elements of two lists pairwise, resulting in a list of tuples, where the first tuple in the list contains the first element of L1 as the first element, and the first element of L2 as the second element The zip function should be written in the Project01-10.fs file.  

 

// 

// zip L1 L2 

// 

// Zip two lists 

// 

// Returns list of tuples 

//  

// Examples:  

//          zip [] [] = [] 

//          zip [1] [1] = [(1, 1)] 

//          zip [1; 2; 40] [3; 56; 6] = [(1, 3); (2, 56); (40, 6)] 

//          zip [1; 2; 3] ['a'; 'b'; 'c'] = [(1, 'a'); (2, 'b'); (3, 'c')] //           

 

Exercise #11:  unzip L 
The function unzip takes a list of pairs (tuples of size 2) and splits them apart into two lists.  Since two lists are returned by this function, the return value is a tuple containing two lists.  The unzip function should be written in the Project01-11.fs file.   

 

// 

// unzip L 

// 

// Unzip a list of pairs to a pair of lists 

// 

// Returns tuple of lists 

//  

// Examples:  

//          unzip [] = ([], []) 

//          unzip [(1, 3); (2, 56); (40, 6)] = ([1; 2; 40], [3; 56; 6]) 

//          unzip [(1, 'a'); (2, 'b'); (3, 'c')] = ([1; 2; 3], ['a'; 'b'; 'c']) 

// 

 

Exercise #12:  range stop
The function range creates a list of integers from 0 to the stop value.  The list should not include the stop value, but instead contain stop elements (0 to stop-1).  The range function with a single parameter should be written in the Project01-12.fs file.  Do not use List Comprehensions, build the list recursively. 

 

// 

// range stop 

// 

// Returns the range of integers starting from 0 

// and using the stop as the upper limit, non-inclusive 

//  

// Examples:  

//          range 0 = [] 

//          range 1 = [0] 

//          range 10 = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] 

// 

 

Exercise #13:  range2 start stop
The function range2 creates a list of integers from start to stop.  The list should include start but not stop, having (stop-start) elements.  Called with a 0 as the value of start, should behave the same as the single parameter version of range.  The range2 function with two parameters should be written in the Project0113.fs file.  Do not use List Comprehensions, build the list recursively. 

 

// 

// range2 start stop 

// 

// Returns a list of integers over the range from start as the lower limit (inclusive) to stop as the upper limit (non-inclusive)  

//  

// Examples:  

//          range2 0 0 = [] 

//          range2 0 1 = [0] 

//          range2 1 5 = [1; 2; 3; 4] 

//          range2 -2 3 = [-2; -1; 0; 1; 2] 

//           

 

Exercise #14:  range3 start stop step
The function range3 creates a list of integers from start to stop moving step values at a time.  The list should include start but not stop, having floor((stop-start)/step) elements.  Called with a 0 as the value of step, should behave the same as the two parameter version of range.  The range3 function with three parameters should be written in the Project01-14.fs file.  Do not use List Comprehensions, build the list recursively. 

 

// 

// range3 start stop step 

// 

// Returns the a list of integers over the range from start as the lower limit (inclusive) to stop as the upper limit (non-inclusive), incrementing by the amount specified in step  

//  

// Examples:  

//          range3 0 0 1   = [] 

//          range3 0 2 1   = [0; 1] 

//          range3 1 5 2   = [1; 3] 

//          range3 5 -2 -3 = [5; 2; -1] 

//           

         

Exercise #15:  slice L start stop
The function slice returns a slice of the list using the limits provided and should be written in the Project0115.fs file.  Instructions for the behavior of this function are included in the comments, and a copy of the file is included here. 

 

// 

// slice L start stop 

// 

// Returns a slice of the list with the specified starting and ending indices (start inclusive and end non-inclusive) 

// This function creates a list containing the copied values from the input list between the starting and ending index 

//  

// Examples:  

//          slice [1; 2; 3; 4; 5] 0 0 = [] 

//          slice [1; 2; 3; 4; 5] 0 1 = [1] 

//          slice [1; 2; 3; 4; 5] 1 4 = [2; 3; 4] 

//          slice [1; 2; 3; 4; 5] 0 5 = [1; 2; 3; 4; 5] 

//          slice [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] 6 2 = [] //           

 

Exercise #16:  filter F L
The function filter applies the predicate function F to the elements of list L and returns a list containing only the elements satisfying the predicate function.  The filter function should be written in the Project01-16.fs file. 

 

// 

// filter F L // 

// Applies the function F to the elements of list L and returns a list containing only the elements from L satisfying the condition 

//  

// Examples:  

//          filter (fun param - false) [1; 2; 3] - [] 

//          filter (fun param - true) [1; 2; 3] - [1; 2; 3] 

//          filter (fun x - x % 2 = 0) [1; 2; 3; 4; 5; 6] - [2; 4; 6] 

//          filter (fun x - x % 5 = 0) [1; 5; 3; 15; 25] - [5; 15; 25] 

//          filter (fun (s,x) - s.Length <= 4) [("Cat", 10); ("Deer", 3); ("Giraffe", 13)] - [("Cat", 10); ("Deer", 3)]  //