Description
Problem 1:
———-
Implement the following functions:
a) filterFirst :: (a -> Bool) -> [a] -> [a]
so that filterFirst p xs removes the first element of xs which does not
satisfy the property p. For instance,
filterFirst even [1,2,3,4] ~~> [2,3,4]
b) filterLast :: (a -> Bool) -> [a] -> [a]
so that filterLast p xs removes the last element of xs which does not
satisfy the property p. For instance,
filterLast even [1,2,3,4] ~~> [1,2,4]
c) split :: [a] -> ([a],[a])
so that split will split a list into two lists, picking elements
alternately. For instance,
split [1,2,3,0,4] ~~> ([1,3,4],[2,0])
d) interleave :: ([a],[a]) -> [a]
so that interleave will interleave two lists. For instance,
interleave ([1,3,4],[2,0]) ~~> [1,2,3,0,4]
e) merge :: (Ord a) => ([a],[a]) -> [a]
so that merge merges two sorted lists to produce a sorted list.
For instance,
merge ([1,2,3],[4,5]) = [1,2,3,4,5]
f) mergeSort :: (Ord a) => [a] -> [a]
so that it realizes the mergesort algorithm. You have to use your
functions split (c) and merge (e).
Problem 2
———
a) Implement the functions
option :: RegExp -> RegExp
plus :: RegExp -> RegExp
where option e matches zero or one occurrence of the pattern e, and
plus e matches one or more occurrences of the pattern e.
b) Define regular expressions which match
– strings of digits which begin with a non-zero digit
– fractional numbers: two strings of digits separated by ‘.’;
make sure that these numbers have no superfluous zeros at the beginning or
at the end, so exclude strings like “01.34” and “1.20”
These are the exercises 12.16 and 12.17 of the book “Haskell – the craft
of functional programming” by Simpson Thompson (Third edition)
http://www.haskellcraft.com/
