Assignment 2 solutions

Sun Sep 23

{-# LANGUAGE TemplateHaskell, Rank2Types #-}
import HApprox ((@?~))
import Test.Tasty (TestTree, testGroup)
import Test.Tasty.HUnit (testCase, (@?=))
import Test.Tasty.TH (defaultMainGenerator)
main = $(defaultMainGenerator)

(1) slice

We learned about built-in functions take and drop. Use them to write a function slice i k xs, where i and k are integer positions and xs is a list. It should return a list containing the elements of xs between positions i and k (including i, but excluding k). If k <= i or if i is out of bounds, make sure it returns an empty list.

Here are some examples:

ghci> slice 3 6 [0,0,0,1,2,3,0,0,0]
[1,2,3]
ghci> slice 2 2 [1,2,3,4]
[]
ghci> slice 2 3 [1,2,3,4]
[3]
ghci> slice 2 10 [1,2,3,4]
[3,4]
ghci> slice 10 15 [1,2,3,4]
[]
ghci> slice 3 2 [1,2,3,4]
[]

Solutions

slice i k xs = take (k-i) (drop i xs)

Tests

case_slice_3_6 = slice 3 6 [0,0,0,1,2,3,0,0,0] @?= [1,2,3]
case_slice_2_2 = slice 2 2 [1,2,3,4] @?= []
case_slice_2_3 = slice 2 3 [1,2,3,4] @?= [3]
case_slice_2_10 = slice 2 10 [1,2,3,4] @?= [3,4]
case_slice_10_15 = slice 10 15 [1,2,3,4] @?= []
case_slice_neg = slice 3 2 [1,2,3,4] @?= []

(2) rotate

Write a function rotate that ‘rotates’ a list to the left by n places. My solution uses take, drop, and the list concatenation operator, ++. The following transcript gives some examples of rotate:

ghci> rotate 0 []
[]
ghci> rotate 2 [1,2,3,4,5]
[3,4,5,1,2]
ghci> rotate 5 "abracadabra"
"adabraabrac"

The behavior of the function is unspecified if the n is negative or larger than the size of the list.

Solution

rotate n l = drop n l ++ take n l

That version works for all the test cases initially provided in the assignment, but we might like it to continue to rotate around if n is greater than the length of the list. In class, we explored a few ways to do that:

rotateA 0 xs = xs
rotateA n xs = rotateA (n-1) (drop 1 xs ++ take 1 xs)

rotateB n xs
  | n > length xs = rotateB (n - length xs) xs
  | otherwise = drop n xs ++ take n xs

rotateC _ [] = []
rotateC n xs = drop k xs ++ take k xs
  where k = n `mod` length xs

Tests

testRotate :: (forall a. Int -> [a] -> [a]) -> [TestTree]
testRotate rot =
  [ testCase "rotate_empty"    $ rot 0 [] @?= ([] :: [Float])
  , testCase "rotate_2_ints"   $ rot 2 [1,2,3,4,5] @?= [3,4,5,1,2]
  , testCase "rotate_5_str"    $ rot 5 "abracadabra" @?= "adabraabrac"
  , testCase "rotate_50_100"   $ rot 50 [1..100] @?= [51..100] ++ [1..50]
  ]

testRotateCirc :: (forall a. Int -> [a] -> [a]) -> [TestTree]
testRotateCirc rot =
  (testCase "rotate_circular" $ rot 13 "hello" @?= "lohel") :
  testRotate rot

test_rotate  = testRotate rotate -- This would fail on rotate_circular
test_rotateA = testRotateCirc rotateA
test_rotateB = testRotateCirc rotateB
test_rotateC = testRotateCirc rotateC

(3) atEvenIndices

Write a recursive function atEvenIndices that takes a list and returns a list that retains the elements at positions 0, 2, 4, etc. — alternating elements. The best way to understand is by example:

ghci> atEvenIndices [1..10]
[1,3,5,7,9]
ghci> atEvenIndices ["Alice", "Bob", "Carl"]
["Alice","Carl"]
ghci> atEvenIndices "university"
"uiest"
ghci> atEvenIndices "trail"
"tal"
ghci> atEvenIndices []
[]
ghci> atEvenIndices [pi]
[3.141592653589793]

Hint: This function actually has two base cases: the empty list, and the list containing just a single element.

Solution

atEvenIndices [] = []
atEvenIndices [x] = [x]
atEvenIndices (x:y:xs) = x : atEvenIndices xs

Tests

case_atEvenIndices_ints   = atEvenIndices [1..10] @?= [1,3,5,7,9]
case_atEvenIndices_strs   = atEvenIndices ["Alice", "Bob", "Carl"] @?= ["Alice","Carl"]
case_atEvenIndices_str_10 = atEvenIndices "university" @?= "uiest"
case_atEvenIndices_str_5  = atEvenIndices "trail" @?= "tal"
case_atEvenIndices_empty  = atEvenIndices [] @?= ([] :: [Int])
case_atEvenIndices_single = atEvenIndices [pi] @?= [3.141592653589793]

(4) atOddIndices

This is much like the previous function, but retains the elements at positions 1, 3, 5, etc. That is, it skips the first element but retains alternating elements after that. If you like, you may use the function atEvenIndices to define atOddIndices (but you would have to copy/paste its definition into this question). Some examples:

ghci> atOddIndices [1..10]
[2,4,6,8,10]
ghci> atOddIndices ["Alice", "Bob", "Carl"]
["Bob"]
ghci> atOddIndices "university"
"nvriy"
ghci> atOddIndices "trail"
"ri"
ghci> atOddIndices []
[]
ghci> atOddIndices [pi]
[]

Solution

atOddIndices [] = []
atOddIndices [x] = []
atOddIndices (x:y:xs) = y : atOddIndices xs

Tests

case_atOddIndices_ints   = atOddIndices [1..10] @?= [2,4,6,8,10]
case_atOddIndices_strs   = atOddIndices ["Alice", "Bob", "Carl"] @?= ["Bob"]
case_atOddIndices_str_10 = atOddIndices "university" @?= "nvriy"
case_atOddIndices_str_5  = atOddIndices "trail" @?= "ri"
case_atOddIndices_empty  = atOddIndices [] @?= ([] :: [Int])
case_atOddIndices_single = atOddIndices [pi] @?= []

(5) countOccurrences

For this problem, you’ll write a list-processing function that consumes a list, but just produces an integer. It should count how many times a particular element appears in a list. Here are some examples:

ghci> countOccurences 5 [1..10]
1
ghci> countOccurences 5 [1,5,2,5,3,5,7,5]
4
ghci> countOccurences 'a' "abracadabra"
5
ghci> countOccurences 'o' "xylophone"
2

You can either write it recursively by pattern-matching on the list, or you can use a combination of existing functions.

Solution

I created two versions of this function. The first one is recursive and directly pattern-matches on the list structure:

countOccurrencesRec x [] = 0
countOccurrencesRec x (y:ys)
  | x == y = 1 + countOccurrencesRec x ys
  | otherwise = countOccurrencesRec x ys

The second solution uses length, filter, and an operator section of (==).

countOccurrencesFilter x ys =
  length (filter (== x) ys)

You could also write that using a list comprehension with a Boolean predicate:

countOccurrencesCompr x ys =
  length [y | y <- ys, x == y]

Tests

Here is a generic set of test cases that can be applied to either solution.

testOccurrences :: (forall a. Eq a => a -> [a] -> Int) -> [TestTree]
testOccurrences count =
  [ testCase "count 1 int"   $ count 5 [1..10] @?= 1
  , testCase "count 4 ints"  $ count 5 [1,5,2,5,3,5,7,5] @?= 4
  , testCase "count 5 chars" $ count 'a' "abracadabra" @?= 5
  , testCase "count 2 chars" $ count 'o' "xylophone" @?= 2
  , testCase "count 0 ints"  $ count 11 [1..10] @?= 0
  , testCase "count empty"   $ count 'z' "" @?= 0
  ]

test_countOccurrencesRec = testOccurrences countOccurrencesRec
test_countOccurrencesFilter = testOccurrences countOccurrencesFilter
test_countOccurrencesCompr = testOccurrences countOccurrencesCompr

(6) dropFirstLast

Write a function dropFirstLast that takes a list and returns a list containing the same elements in the same order except for the first and last elements. If the list has fewer than three elements, the result should be the empty list. I recommend coding this in terms of drop, take, and length. You also could use the slice function you wrote previously, but you’d have to copy/paste its definition here. Examples:

ghci> dropFirstLast [1..10]
[2,3,4,5,6,7,8,9]
ghci> dropFirstLast "smiley"
"mile"
ghci> dropFirstLast [2,4,6]
[4]
ghci> dropFirstLast "xs"
""
ghci> dropFirstLast "x"
""
ghci> dropFirstLast []
[]

Solution

dropFirstLast xs = drop 1 (take (length xs - 1) xs)

Tests

case_dropFirstLast_ints = dropFirstLast [1..10]   @?= [2,3,4,5,6,7,8,9]
case_dropFirstLast_word = dropFirstLast "smiley" @?= "mile"
case_dropFirstLast_3    = dropFirstLast [2,4,6]  @?= [4]
case_dropFirstLast_2    = dropFirstLast "xs"     @?= ""
case_dropFirstLast_1    = dropFirstLast "x"      @?= ""
case_dropFirstLast_0    = dropFirstLast []       @?= ([] :: [Char])