Write the following functions, which all belong to Haskell's standard library:
a) iterate :: (a → a) → a → [a]
iterate f x = [x, f x, f (f x), …]
b) elemIndex :: Eq a => a → [a] → Maybe Int
c) takeWhile :: (a → Bool) → [a] → [a]
find :: (a → Bool) → [a] → Maybe acatMaybes :: [Maybe a] -> [a]catMaybes [Just 3, Nothing, Just 4, Just 5, Nothing]
will produce the list [3, 4, 5].partition :: (a → Bool) → [a] → ([a], [a])span :: (a → Bool) → [a] → ([a], [a])span p l
is equivalent to (takeWhile p l, dropWhile p l).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]
a) Write the following function (which is in Haskell's standard library in the Data.List module):
> 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"
Write a function subsets :: [a] -> [[a]]
that returns a list of all subsets of a set represented as a list.
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"]
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.
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.
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.
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].
Write a function min_coins :: [Int] ->
Int -> Just [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]. If it is not possible to form the given sum
from the given coins, return Nothing.
Write
a function eq_partition
:: [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.
Write
a function break
::
[String]
->
String
->
Maybe
[String]
that
takes two arguments: a dictionary of words plus a string. If it is
possible to break the string into some sequence of words from the
dictionary, the function should return a list of those words,
otherwise Nothing. For example, break
["black",
"blue",
"green",
"red",
"white"]
"redgreenblue"
should
return Just
["red",
"green",
"blue"].
If
there is more than one possible way to break the string into words,
the function may return any of these.
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 . .