Week 10: Exercises

1. All Pairs

Construct an infinite list allPairs that contains all pairs of positive integers. Every pair must appear exactly once in the list.

2. Subsets

Write a function subsets :: [a] -> [[a]] that returns a list of all subsets of a set represented as a list.

3. Combinations

Write a function combinations :: Int -> [a] -> [[a]] that takes an integer k and a list, and returns a list of all combinations of k elements of the elements in the list. The elements in each combination should appear in the same order as in the original list:

> combinations 2 "zebra"
["ze","zb","zr","za","eb","er","ea","br","ba","ra"]

4. Permutations

Write a function perms :: [a] -> [[a]] that returns a list of all permutations of a given list. Do not assume that the type a implements Eq.

5. Compositions

Write a function compositions :: Int -> [[Int]] that takes a natural number N and returns a list of all sets of positive integers that add up to N. Order matters: 1 + 2 and 2 + 1 are distinct compositions of N = 3.

6. Partitions

A partition of a positive integer n is a set of positive integers that add up to n. For example, the number 4 has 5 partitions:

1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 + 1
4

Write a function partitions :: Int -> [[Int]] that produces a list of all partitions of a positive integer.

7. Minimum Number of Coins

Write a function minCoins :: [Int] -> Int -> [Int] that takes a list of coin denominations and a sum, and returns a minimal list of coins which can be used to form the sum. Any denomination may be used multiple times in forming the sum. For example, coins [1, 2, 5, 10] 9 might return the list [2, 2, 5].

8. Equal Partitions

Write a function eqPartition :: [Int] -> Maybe ([Int], [Int]) that takes a list of integers and determines whether it can be partitioned into two sets whose sums are equal. If so, the function should return a Just with two lists containing the numbers in each set. If not, it should return Nothing.

9. List Functions

Write the following functions, which all belong to Haskell's standard library:

a) iterate :: (a → a) → a → [a]

Return an infinite list generated by applying a function repeatedly:

iterate f x = [x, f x, f (f x), …]

b) elemIndex :: Eq a => a → [a] → Maybe Int

Return the index of the first element in the given list that is equal to the query element, or Nothing if there is no such element. Elements are indexed starting from 0.

c) takeWhile :: (a → Bool) → [a] → [a]

Return the longest prefix of elements that all satisfy a predicate.

d) find :: (a → Bool) → [a] → Maybe a

Return the first element in the list that satisfies the given predicate, or Nothing if there is none.

e) partition :: (a → Bool) → [a] → ([a], [a])

Given a predicate and a list, return lists of elements that do and do not satisfy the predicate.

f) span :: (a → Bool) → [a] → ([a], [a])

Split a list into two lists using a predicate p. (span p l) is equivalent to (takeWhile p l, dropWhile p l).

10. Alternating Map

Write a function altMap that takes two functions and a list. altMap should apply the two functions alternately to list elements. For example:

altMap (\i -> i + 1) (\i -> i - 1) [1..8] == [2, 1, 4, 3, 6, 5, 8, 7]

11. Maximum By

a) Write the following function (which is in Haskell's standard library in the Data.List module):

maximumBy :: (a → a → Ordering) → [a] → a: Compute the largest element of a non-empty list with respect to a comparison function.; For example:

> maximumBy (\s t -> compare (length s) (length t)) ["one", "fine", "day"]
"fine"

b) Write a function maxBy :: Ord b => (a -> b) -> [a] -> a that takes a function f and a list of values, and returns the value x for which f(x) is largest.

For example:

> maxBy length ["one", "fine", "day"]
"fine"

12. Pythagorean Triples

Write a function triples that takes an integer N and returns a list of integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c². If two triples are multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)), only the smaller of them (e.g. (3, 4, 5)) should appear in the list.

> triples 15
[(3,4,5),(5,12,13)]

13. Infinite Diagonal Matrix

Construct an infinite diagonal matrix as an infinite list of lists:

[[1,0,0,0, ...], [0,1,0,0, ...], [0,0,1,0, ...], . . . ]

14. Largest Product in a Series

Solve Project Euler problem 8 (Largest Product in a Series). Assume that the input number is given as a list of strings:

num = [
  "73167176531330624919225119674426574742355349194934",
  "96983520312774506326239578318016984801869478851843",
  …

]

15. Finite State Machine

As you may have learned in an automata class, a finite state machine consists of

a finite set of states
a finite set of input symbols
a transition function that maps a state and an input symbol to a new state
a start state
a set of final (or accepting) states

In this exercise we will consider finite state machines whose states are integers and whose input symbols are characters.

a) Design finite state machines that accept the following sets of characters, represented by regular expressions:

ab(..)*
(.*)aaba(.*)

b) Design a representation for finite state machines in Haskell.

c) Write a function accept that takes a finite state machine and a string, and returns true if the the machine accepts the string. Use your function to test the finite state machines that you defined in part (a).