Реализация функции Аккермана. Без кэширования:
let rec ack m n = match (m, n) with | (0, n) -> n + 1 | (m, 0) -> ack (m-1) 1 | (m, n) -> ack (m-1) (ack m (n-1));;
Описание функции:
$latex A\left(m,n\right)=\begin{cases}n+1&m=0\\A\left(m-1,1\right)&m>0,n=0\\A\left(m-1,A\left(m,n-1\right)\right)&m>0,n>0\end{cases}$
Математическое и алгоритмическое описания очень схожи. И не удивительно: хороший функциональный язык.
Реализация с кэшированием, самостоятельная программа:
open Hashtbl;; let a = create 200000 let arg n = int_of_string Sys.argv.(n) let rec ack m n = try find a (m, n) with Not_found -> let r = match (m, n) with | (0, n) -> n + 1 | (m, 0) -> ack (m-1) 1 | (m, n) -> ack (m-1) (ack m (n-1)) in add a (m, n) r; r;; print_int (ack (arg 1) (arg 2));;