Задание: f n = n!

fac1 n = if n == 0 then 1 else n * (fac1 (n-1))

fac2 0 = 1
fac2 n = (fac2 (n-1)) * n

Задание: найти n-е число Фибоначчи

fib1 n = if n <= 2 then 1 else fib1 (n-1) + fib1 (n-2)

Задание: найти сумму чисел в списке

summ [] = 0
summ (a:x) = a + (summ x)

Про приоритеты операций:

summ2 [] = 0
summ2 (a:x) = summ2 x + a

Задание: найти максимум в списке натуральных чисел

maxx [] = 0
maxx (a:x) = max2 a (maxx x)
max2 a b = if a > b then a else b

Неправильный способ (экспоненциальный):

emaxx [] = 0
emaxx (a:x) = if a > (emaxx x) then a else (emaxx x)

Задание: получить список [n,...,3,2,1]

deca 0 = []
deca n = n:(deca (n-1))

Задание: получить список [1,2,3,...,n]

Для n=20 это контрпример к экспоненциальному максимуму.

inca n = func n []
func 0 a = a
func n a = func (n-1) (n:a)

Задание: запустить emaxx на полученном тесте

emaxx (inca 20)

Доп. вопрос #1: как за O(log) запусков найти минимальное n, на котором emaxx работает дольше секунды?
Доп. вопрос #2: как за O(1) запусков найти минимальное n, на котором emaxx работает дольше секунды?