# 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:
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.

## 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
1
1
2
1
3
2
4
3
5
5
6
8
7
13
...
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
1
f 1
2
f 2
3
f 3
4
f 4
5
f 5
6
f 6
7
f 7
...

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