Programowanie funkcyjne/Zadania egzaminacyjne

Propozycje zadań egzaminacyjnych:

• Napisz procedurę posumuj, która dla danej niemalejącej listy dodatnich liczb całkowitych $(a_1\dots a_n)$ oblicza listę $(b_1\dots b_n)$, gdzie $b_i=\sum _{k=a_i}^n{a}_k$. (Pamiętaj o tym, że jeśli $m>n$, $\sum _{k=m}^n{a}_k=0$.)
• Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości. Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1. Napisz procedurę słupki, która dla danej listy początkowych wysokości słupków obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków.
• Napisz funkcję max_diff : int list $\to$ int, która dla niepustej listy $[x_1;\dots ;x_n]$ znajdzie maksymalną różnicę $x_j-x_i$ dla $1\le i\le j\le n$. Jaką złożoność ma Twoja procedura?
• Napisz procedurę przedziały:int list -> int*int, która dla danej listy $[a_1,\dots ,a_n]$ oblicza taką parę liczb $(k,l)$, $1\le k\le l\le n$, dla której suma $a_k+\cdots +a_l$ jest największa. Oblicz i podaj złożoność Twojego rozwiązania.
• Napisz procedurę podziel: int list -> int list list, która dla danej listy $[a_1;a_2;\dots ;a_n]$ zawierającej permutację zbioru $\{1,2,\dots ,n\}$ znajdzie jej podział na jak najliczniejszą listę list postaci:

$[[a_1;a_2;\dots ;a_{k_1}];[a_{k_1+1};a_{k_1+2};\dots ;a_{k_2}];\dots ;[a_{k_{m-1}+1};a_{k_{m-1}+2};\dots ;a_{k_m}]]$

taką że:

$\begin{array}{rcl}\{a_1,a_2,\dots ,a_{k_1}\}& =& \{1,2,\dots ,k_1\}\text{(równość zbiorów)},\\ \{a_{k_1+1},a_{k_1+2},\dots ,a_{k_2}\}& =& \{k_1+1,k_1+2,\dots ,k_2\},\\ & ⋮& \\ \{a_{k_{m-1}+1},a_{k_{m-1}+2},\dots ,a_{k_m}\}& =& \{k_{m-1}+1,k_{m-1}+2,\dots ,k_m\}\end{array}$

Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.

Przykład: podziel [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]].

Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.