PLT11 course -- assignment 7

(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau

Logistics

Assignment

The following tasks require the following skills:

  • Function definitions defined by pattern matching.
  • List constructors [] and (:).
  • Recursive functions.

You are required to code up functions in a certain way. First make sure to have any solution for the stated problem. Then work on trying to meet the extra code-level constraints.


1st option

Define a function equy to determine whether two lists contain the same elements modulo reordering. For example:

> :t equy 
equy :: (Eq a) => [a] -> [a] -> Bool

> equy [1,2,3,4] [1,3,2,4]
True

> equy [1,2,3,4] [1,3,2,4,5]
False

> equy [1,2,3,4] [1,3,2,5]
False

The equy function must be defined recursively and by pattern matching on lists. Do not reuse any function from the prelude except for Booleans and equality. Do not implement a sort function. If you need helper functions, then define them in the where block of the equy function. Hint: a simple solution would define a helper function rid for removing the first occurrence of a given element in a given list. By comparing the original list and the result of rid for equality, one could also observe whether any occurrence was found actually.


2nd option

Define a function flippy to transform a list such that first and last elements from the input are repeated combined in flipped order in the output. For example:

> :t flippy
flippy :: [a] -> [a]

> flippy [1,2,3,4,5,6]
[6,1,5,2,4,3]

> flippy [1,2,3,4,5,6,7]
[7,1,6,2,5,3,4]

The flippy function must be defined recursively and by pattern matching on lists. Do not reuse any function from the prelude. If you need helper functions, then define them in the where block of the flippy function. Hint: a simple solution would define the following helper functions.

-- Retrieve the last element of a list
last :: [a] -> a
-- Remove the last element of a list
butLast :: [a] -> [a]

3rd option

Define a function searchy to search for one string in another string. For example:

> searchy "ac" "xacy"
True
> searchy "ac" "xabcy"
False
> searchy "ac" "xabacy"
True

The searchy function must be defined recursively and by pattern matching on lists. Do not reuse any function from the prelude except for Booleans and equality. If you need helper functions, then define them in the where block of the searchy function. Hint: a simple solution could be obtained by filling in the dots in the following code.

searchy :: [Char] -> [Char] -> Bool
searchy [] _ = True
searchy _ [] = False
searchy (x:xs) (y:ys) = ...
 where
  -- one string is the prefix of the other string
  searchy' [] _ = True
  searchy' _ [] = False
  searchy' (x:xs) (y:ys) = ...