// GENERATED /* INSTRUCTIONS * * Complete the exercises below. For each \"EXERCI

Question

// GENERATED
/* INSTRUCTIONS
*
* Complete the exercises below. For each "EXERCISE" comment, add
* code immediately below the comment.
*
* Please see README.md for instructions, including compilation and testing.
*
* GRADING
*
* 1. Submissions MUST compile using SBT with UNCHANGED configuration and tests with no
* compilation errors. Submissions with compilation errors will receive 0 points.
* Note that refactoring the code will cause the tests to fail.
*
* 2. You MUST NOT edit the SBT configuration and tests. Altering it in your submission will
* result in 0 points for this assignment.
*
* 3. You MUST NOT use while loops or (re)assignment to variables (you can use "val" declarations,
* but not "var" declarations). You must use recursion instead.
*
* 4. You may declare auxiliary functions if you like.
*
* SUBMISSION
*
* 1. Submit this file on D2L before the deadline.
*
* 2. Late submissions will not be permitted because solutions will be discussed in class.
*
*/

object fp3 {

// EXERCISE 1: complete the following recursive definition of a "member" function
// to check whether an element "a" is a member of a list of integers "xs".
// Your implementation of "member" MUST be recursive and not use the builtin "contains" method from the List class.
// EXAMPLES:
// - member (5, List (4, 6, 8, 5)) == true
// - member (3, List (4, 6, 8, 5)) == false
def member (a : Int, xs : List[Int]) : Boolean = {
// TODO: Provide definition here.
false
}

// EXERCISE 2: complete the following recursive definition of an "allEqual" function
// to check whether all elements in a list of integers are equal.
// EXAMPLES:
// - allEqual (Nil) == true
// - allEqual (List (5)) == true
// - allEqual (List (5, 5, 5)) == true
// - allEqual (List (6, 5, 5, 5)) == false
// - allEqual (List (5, 5, 6, 5)) == false
// - allEqual (List (5, 5, 5, 6)) == false
def allEqual (xs : List[Int]) : Boolean = {
// TODO: Provide definition here.
false
}

// EXERCISE 3: complete the definition of the following function that computes the length of
// each String in a list, and returns the original Strings paired with their length.
// For example:
//
// stringLengths (List ("the", "rain")) == List (("the", 3), ("rain", 4))
//
// You must not use recursion directly in the function. You can use the "map" method
// of the List class.
def stringLengths (xs:List[String]) : List[(String, Int)] = {
// TODO: Provide definition here.
null
}

// EXERCISE 4: complete the function definition for "delete1" that takes
// an element "x" and a list "ys", then returns the list where any
// occurrences of "x" in "ys" have been removed. Your definition of
// "delete1" MUST be recursive.
// EXAMPLE:
// - delete1 ("the", List ("the","the","was","a","product","of","the","1980s")) == List ("was","a","product","of","1980s")
def delete1 [X] (x:X, ys:List[X]) : List[X] = {
// TODO: Provide definition here.
null
}

// EXERCISE 5: complete the function definition for "delete2" below. It must
// have the same behavior as "delete1". It must be written using "for comprehensions"
// and not use recursion explicitly.
def delete2 [X] (x:X, ys:List[X]) : List[X] = {
// TODO: Provide definition here.
null
}

// EXERCISE 6: complete the function definition for "delete3" below. It must
// have the same behavior as "delete1". It must be written using the
// builtin "filter" method for Lists and not use recursion explicitly.
def delete3 [X] (x:X, ys:List[X]) : List[X] = {
// TODO: Provide definition here.
null
}

// EXERCISE 7: complete the function definition for "removeDupes1" below.
// It takes a list as argument, then returns the same list with
// consecutive duplicate elements compacted to a single element.  
// Duplicate elements that are separated by at least one distinct
// element should be left alone.
// EXAMPLE:
// - removeDupes1 (List (1,1,2,3,3,3,4,4,5,6,7,7,8,9,2,2,2,9)) == List (1,2,3,4,5,6,7,8,9,2,9)
def removeDupes1 [X] (xs:List[X]) : List[X] = {
// TODO: Provide definition here.
null
}

// EXERCISE 8: write a function "removeDupes2" that behaves like "removeDupes1",
// but also includes a count of the number of consecutive duplicate
// elements in the original list (thus producing a simple run-length
// encoding). The counts are paired with each element in the output
// list.
// EXAMPLE:
// - removeDupes2 (List (1,1,2,3,3,3,4,4,5,6,7,7,8,9,2,2,2,9)) == List ((2,1),(1,2),(3,3),(2,4),(1,5),(1,6),(2,7),(1,8),(1,9),(3,2),(1,9))
def removeDupes2 [X] (xs:List[X]) : List[(Int, X)] = {
// TODO: Provide definition here.
null
}

// EXERCISE 9: complete the following definition of a function that splits a list
// into a pair of two lists. The offset for the the split position is given
// by the Int argument.
// The behavior is determined by:
//
// for all n, xs:
// splitAt (n, xs) == (take (n, xs), drop (n, xs))
//
// Your definition of "splitAt" must be recursive and must not use "take" or "drop".
//
// Your definition of "splitAt" must only travere the list once. So
// you cannot define your own versions of "take"/"drop" and use them
// (because that would entail one traversal of the list with "take"
// and then a second traversal with "drop").
def splitAt [X] (n:Int, xs:List[X]) : (List[X], List[X]) = {
// TODO: Provide definition here.
null
}

// EXERCISE 10: complete the following definition of an "allDistinct" function that checks
// whether all values in list are distinct. You should use your "member" function defined earlier.
// Your implementation must be recursive.
// EXAMPLE:
// - allDistinct (Nil) == true
// - allDistinct (List (1,2,3,4,5)) == true
// - allDistinct (List (1,2,3,4,5,1)) == false
// - allDistinct (List (1,2,3,2,4,5)) == false
def allDistinct (xs : List[Int]) : Boolean = {
// TODO: Provide definition here.
false
}
}

Explanation / Answer

Here is complete code with examples

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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