AB1 Non-Recursive Expressions

Implement the following functions as non-recursive expressions (only exception is part 2) and only use the already imported functions. Additionally, the following language constructs are not permitted:

Pattern Matching (i.e. left of '=' there may only be a list of variable identifiers (varid) separated by whitespaces)
if ... then ... else ... (use if' instead if available)
Guards
List Comprehensions: [(i,j) | i <- [1,2], j <- [3,4]]
Arithmetic Sequences: [i .. j]

Directions (also apply to all following AB (=Arbeitsblatt, German for worksheet)):

directions concerning the submission of the AB can be found in Readme.html
code examples can be found in the file example/Test.hs
the i-th argument (input parameter) of a function is called argi. For example, the second argument of f :: Int -> Int -> Int -> Int is called arg2
you can implement the functions within a part in arbitrary order (this allows you to use later functions when defining previous ones)
negative numbers: if not explicitly stated otherwise then functions have to work as expected for negative numbers as well
ask when in doubt of how to interpret the specification of a function (i.e. when it is unclear what the output for a certain input should be)

🎦 Functions and Expressions (click to watch video) 🎦

For this AB you should look at the functions map, filter, reduce, foldl and foldr.

SPLib Functions (SPLib_en.html) - description of all functions which are used in this course
Maps and Filters, Folds on LearnYouAHaskell
Fold in the Haskell-Wiki

Part 1

You may assume that arg1 contains at least on element for all functions in this part (except for the function bigAnd2).

minimum  :: [Int] -> Int
maximum  :: [Int] -> Int

These functions return the minimal resp. maximal element of the list arg1.

bigAnd   :: [Bool] -> Bool 
bigOr    :: [Bool] -> Bool 
bigXor   :: [Bool] -> Bool

The function bigAnd returns true iff all elements in arg1 are true.
The function bigOr returns true iff at least one element in arg1 is true.
The function bigXor returns true iff an odd numbers of elements in arg1 is true.

sum :: [Int] -> Int
alternatingSum  :: [Int] -> Int
alternatingSum2 :: [Int] -> Int

The function sum returns the sum of all elements in arg1.
The function alternatingSum returns the alternating sum of all elements in arg1. For [1,2,3,4,5] this is 1 - 2 + 3 - 4 + 5.
The function alternatingSum2 is a variant where + and - are swapped. For [1,2,3,4,5] this is 1 + 2 - 3 + 4 - 5.

bigAnd2 :: [Bool] -> Bool

The function bigAnd2 returns true iff all elements in the list are true or the list is empty.

Part 2

For this part you may (and have to) use recursive expressions.

infiniteList :: Int -> [Int] 
listFromTo   :: Int -> Int -> [Int]

The function infiniteList returns the infinite list which contains all Int starting from arg1 in ascending order.
The function listFromTo returns the list which contains all Int starting from arg1 to arg2 in ascending order. Examples:

listFromTo 2 5 = [2,3,4,5]
listFromTo 2 1 = []

fibTree :: (Tree Int) 
fTree   :: (Int -> Int) -> (Tree Int)

The function fibTree is the infinite binary tree which describes the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, ...). The first child is the corresponding value from the sequence.

Example

The function fTree is a generalization of fibTree for arbitrary sequences. The first child of a node with value i contains the value f i with f = arg1.

Example

Part 3

crossList    :: [a] -> [b] -> [(a,b)]
genCrossList :: [[a]] -> [[a]]

The function crossList is the Cartesian product of two lists. Example:

crossList [1,2] [3,4] = [(1,3),(1,4),(2,3),(2,4)]

The function genCrossList is the Cartesian product generalized to arbitrarily many arguments, which are encoded as elements of the list arg1. You may assume that arg1 contains at least one element.

genCrossList [[1,2],[3,4],[5,6]] = [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
genCrossList [[1,2,3]] = [[1],[2],[3]]

Hint for genCrossList (if you have trouble implementing this function, try to complete the following code)

genCrossList lst = foldl crossList2 acc lst'
  where
    crossList2 x y = map g ?
      where
        g (lst,el) = append el lst  
    lst' = ?
    acc = map f ?
      where
        f el = [el]

primes :: Int -> [Int]

The function primes returns the first arg1 (≥ 0) prime numbers. Examples:

primes 5 = [2,3,5,7,11]
primes 0 = []

Hint for primes

Write a function without input parameters which returns the infinite list of all prime numbers.

Part 4

type Base = Int
toDigits   :: Base -> Int -> [Int]
fromDigits :: Base -> [Int] -> Int
length     :: Base -> Int -> Int

The function toDigits converts the number arg2 (≥ 0) into a list of digits w.r.t. the basis arg1 (≥ 2). The first element of the list is the one with the highest significance (for basis 2 this means the most significant bit). Examples:

toDigits 2 4 = [1,0,0]
toDigits 10 9876 = [9,8,7,6]

The function fromDigits is the inverse function of toDigits. This means it must hold that fromDigits b (toDigits b x) == x. You may assume that every element in arg2 is between 0 and (arg1 - 1) and arg2 contains at least one element. Examples:

fromDigits 2 [1,0,0] = 4
fromDigits 10 [9,8,7,6] = 9876

The function length returns the length of a number arg2 w.r.t. basis arg1. Examples:

length 2 4 = 3
length 10 9876 = 4

A number consisting of $n \geq 1$ digits $x_1, x_2, \dots, x_n$ w.r.t. basis $b \geq 2$ is defined as $$\sum_{i=1}^n x_i \cdot b^{i-1}$$

Hint for find and zip

the expression find f (infiniteList 1) returns the first x ≥ 1 such that (f x) == True
the expression zip [4,5,6] (infiniteList 7) returns [(4,7),(5,8),(6,9)]

Hint for toDigits

Write a function which returns the i-th digit of a number w.r.t. a given basis.