Week 8: Exercises

1. 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).

2. 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]

3. 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"

4. Subsets

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

5. 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"]

6. 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.

7. 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.

8. 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.

9. Sums with Coins

Write a function coins :: [Int] -> Int -> [[Int]] that takes a list of coin denominations and a sum, and returns a list of all ways to form the sum using coins from the set. Any coin may be used multiple times in forming the sum. Order does not matter: for example: the function should not return both [1, 1, 2] and [2, 1, 1].

10. 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 coin may be used multiple times in forming the sum. For example, coins [1, 2, 5, 10] 9 might return the list [2, 2, 5].

11. 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.

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).

16. N Queens

Is it possible to place N queens on an N x N chessboard such that no two queens attack each other?

a) Write a function that can produce a list of all possible solutions for a given N, where each solution is a list of positions of queens on the board. Use an exhaustive search. For example:

> queens 4
[[(2,1),(4,2),(1,3),(3,4)],[(3,1),(1,2),(4,3),(2,4)]]

b) Modify your function to return a list of strings, where each string depicts a possible solution:

> queens 4
[". Q . . \n. . . Q \nQ . . . \n. . Q . \n",". . Q . \nQ . . . \n. . . Q \n. Q . . \n"]

To see the output nicely in the REPL, you can use I/O functions (which we haven't learned about yet):

> mapM_ putStrLn (queens 4)
. Q . . 
. . . Q 
Q . . . 
. . Q . 

. . Q . 
Q . . . 
. . . Q 
. Q . .