Construct an infinite list allPairs
that contains all pairs of positive integers. Every pair must appear
exactly once in the list.
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 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].
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.
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
apartition :: (a → Bool) → [a] → ([a], [a])
span :: (a → Bool) → [a] → ([a], [a])
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 triples
that takes
an integer N and returns a list of integer triples (a, b, c) with
0 < a < b < c ≤ N such that
a2 + b2 = c2. 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)]
Construct an infinite diagonal matrix as an infinite list of lists:
[[
1
,
0
,
0
,
0
,
...],
[0
,
1
,
0
,
0
,
...],
[0
,
0
,
1
,
0
,
...],
.
.
.
]
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", … ]
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).