Assignment 1

Assignment 1: higher-order functions and linear recursion #

Hint. In this assignment, you can often take advantage of the native higher-order functions that we have encountered: filter, map, all, any, etc.

Exercise 1: utility functions #

Implement the functions below by completing the function stubs in the file Src/Utility.hs.

Hint. Some of these functions can be used to implement others.

Hint. Feel free to create additional (auxiliary) functions to simplify your implementation.

hasSep #

Implement the function

hasSep :: String -> Bool

such that hasSep s evaluates to True iff s contains at least one /.

For instance,

hasSep "alice/workspace/oofp"

should evaluate to True, whereas

hasSep "hi there"

should evaluate to False.

someHasSep #

Implement the function

someHasSep :: [String] -> Bool

such that someHasSep ss evaluates to True iff one or several strings in ss contain at least one /.

For instance,

someHasSep ["Paste","cd alice/workspace/oofp","and","press","enter"]

should evaluate to True, whereas

someHasSep ["Restart","the","program"]

should evaluate to False.

mapTwice #

Implement the function

mapTwice :: (a -> b) -> (b -> c) -> [a] -> [c]

such that mapTwice f g xs applies f to each element of xs, and then g to each element of the resulting list.

For instance,

mapTwice (+ 1) (* 2) [1,3]

should evaluate to [4,8].

keepFullMatches #

Terminology. We say that an element x with type a satisfies a function f :: a -> Bool if f x evaluates to True.

Implement the function

keepFullMatches :: (a -> Bool) -> [[a]] -> [[a]]

such that keepFullMatches f xss consists of the lists in xss whose elements all satisfy f (in the same order as they appear in xss).

For instance,

keepFullMatches even [[1,3,4], [2,6,2], [3], [], [8,5,2]]

should evaluate to [[2,6,2], []].

appearsInSome #

Implement the function

appearsInSome :: (Eq a) => a -> [[a]] -> Bool

such that appearsInSome x xss evaluates to True iff x appears in at least one of the lists in xss.

For instance,

appearsInSome 3 [[1,4], [2,6,3], [], [4,3]]

should evaluate to True, whereas

appearsInSome 3 [[1,4], [2,4,2], [], [6]]

should evaluate to False.

hasTwin #

Implement the function

hasTwin :: (Eq a) => [(a,a)] -> Bool

such that hasTwin xs is True iff the list xs contains at least one pair of identical elements.

For instance,

hasTwin [(1,2), (2,2), (5,3), (3,3)]

should evaluate to True, whereas

hasTwin [(1,2), (2,1), (5,3), (1,2)]

should evaluate to False.

satisfiesAll #

Implement the function

satisfiesAll :: [a -> Bool] -> a -> Bool

such that satisfiesAll fs x evaluates to True iff f x evaluates to True for each function f in fs.

For instance,

satisfiesAll [even, (> 3)] 8

should evaluate to True, whereas

satisfiesAll [even, (> 3)] 2

should evaluate to False.

shiftAndZip #

Implement the function

shiftAndZip :: [a] ->  [(a,a)]

such that shiftAndZip xs consists of each element of xs (except for the last one) paired with its successor, in the same order as in xs.

For instance,

shiftAndZip [1,2,4,8]

should evaluate to [(1,2),(2,4),(4,8)]

Restriction. You can assume that the list xs has length $\ge 2$.

Hint. You may take advantage of the native Haskell function zip, seen during the lectures.

hasConsDup #

Implement the function

hasConsDup :: (Eq a) => [a] -> Bool

such that hasConsDup xs is True iff the list xs contains two consecutive occurrences of a same element.

For instance (since a String in Haskell is a list of characters),

hasConsDup "this is possible"

should evaluate to True, whereas

hasConsDup "this is unlikely"

should evaluate to False.

Restriction You can assume that the list xs has length $\ge 2$.

Hint. You may take advantage of some functions implemented above.

prefix #

Implement the function

prefix :: (Eq a) => [a] -> [a] -> Bool

such that prefix xs ys evaluates to True iff the list xs is a prefix of the list ys.

For instance,

prefix [1,3] [1,3,5,4]

should evaluate to True, whereas

prefix [1,3] [6,1,1,3,5,4]

should evaluate to False.

sublist #

Implement the function

sublist :: (Eq a) => [a] -> [a] -> Bool

such that sublist xs ys evaluates to True iff the list xs appears as a (contiguous) sublist of the list ys.

For instance,

sublist [1,3] [6,1,3,5,4]

should evaluate to True, whereas

sublist [1,3] [6,1,2,3,5,4]

should evaluate to False.

Exercise 2: playing cards #

Data format.

Playing card. We represent a playing card as a pair (s, r) with type (Char, Int), where:

  • s represents the card’s suit: either 'C', 'D', 'H' or 'S' ( for Clubs, Diamonds, Hearts, and Spades respectively), and

  • r represent the card’s rank. This is an Int between 1 and 13, where:

    • 1, 11, 12 and 13 stand for an ace, jack, queen and king respectively, and
    • the numbers 2 to 10 stand for themselves.

We assume that the lowest rank is 1 (aka ace) and that the highest is 13 (aka king).

Hand. We represent a hand as a list of cards. Therefore a hand has type [(Char, Int)].

Implement the functions below by completing the function stubs in the file Src/Cards.hs.

Hint. Some of these functions can be used to implement others.

Functions of the previous exercise can be used as well.

Hint. Feel free to create additional (auxiliary) functions to simplify your implementation.

isFaceless #

Implement the function

isFaceless :: [(Char, Int)] -> Bool

such that isFaceless h evaluates to True iff the hand h has no jack, queen or king.

For instance,

isFaceless [('S',2), ('C',10)]

should evaluate to True, whereas

isFaceless [('S',2), ('C',11), ('C',5)]

should evaluate to False.

sumSpades #

Implement the function

sumSpades :: [(Char, Int)] -> Int

such that sumSpades h evaluates to the sum of the ranks of all Spades in the hand h.

For instance,

sumSpades [('S',2), ('C',10), ('S',12), ('H',1)]

should evaluate to 14.

countOcc #

Implement the function

countOcc :: Int -> [(Char, Int)] -> Int

such that countOcc r h is the number of occurrences of the rank r in the hand h.

For instance,

countOcc 12 [('S',12), ('C',4), ('C',12)]

should evaluate to 2.

isFourOfAKind #

Terminology. In poker, a “four of a kind” is a hand of 5 cards where 4 have the same rank.

Implement the function

isFourOfAKind :: [(Char, Int)] -> Bool

such that isFourOfAKind h evaluates to True iff h is a “four of a kind”.

Restriction. You can assume that cards in h are distinct.

Hint. in Haskell, the list of all integers from 1 to 13 (both inclusive) can be written [1 .. 13].

allSameSuit #

Implement the function

allSameSuit :: [(Char, Int)] -> Bool

such that allSameSuit h evaluates to True iff all cards in the hand h have the same suit.

For instance,

allSameSuit [('S',12), ('S',3)]

should evaluate to True, whereas

allSameSuit [('S',12), ('H',2), ('S',3)]

should evaluate to False.

isFlush #

Terminology. In poker, a flush is a hand of 5 cards with the same suit.

Implement the function

isFlush :: [(Char, Int)] -> Bool

such that isFlush h evaluates to True iff h is a flush.

Restriction. You can assume that all cards in h are different.

precedes #

Convention. We assume that players sort their hand by suit first (in alphabetical order), and then by rank. For instance, the following hand is sorted:

[('H',6), ('S',3), ('S',12)]

whereas the following hand is not sorted

[('S',12), ('H',2), ('S',3)]

Implement the function

precedes :: (Char, Int) -> (Char, Int) -> Bool

such that precedes c1 c2 evaluates to True iff the card c1 precedes the card c2 in the sorting order.

isSorted #

Implement the function isSorted :: [(Char, Int)] -> Bool

such that

isSorted h

evaluates to True iff the hand h is sorted (according to the order defined above).

Hint. You may take advantage of the function shiftAndZip implemented in the first exercise.

mergeSorted #

Implement the function

mergeSorted :: [(Char, Int)] -> [(Char, Int)] -> [(Char, Int)]

that merges two sorted hands into a sorted hand (where the sorting order is the one defined above).

Precisely, if h1 and h2 are two sorted hands, then mergeSorted h1 h2 evaluates to the sorted hand that consists of the cards of h1 and h2.

For instance,

mergeSorted [('H',6), ('S',3)] [('C',10), ('S',5)]

should evaluates to

[('C',10), ('H',6), ('S',3), ('S',5)]