# Homework 2 Solved

\$35.00 \$29.05

Category:

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