friedman_ackermann.clj

;; A version of the ackermann function, described in https://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf

(require '[clojure.core.match :refer [match]])

(defn ackermann [[k & r :as s] n]
  (if (not (seq s))
    n
    (match [k n]
           [1 _] (recur r (*' 2 n))
           [_ 1] (recur (cons (dec k) r) 1)
           [_ _] (recur (cons k (cons (dec k) r))
                        (dec n)))))


;; (ackermann '(3) 5) 

;; some optimization

(defn exp [n]
  (loop [n n r 2]
    (if (= n 1)
      r
      (recur (dec n) (*' 2 r)))))

(defn tetr [n]
  (loop [n n r 2]
    (if (= n 1)
      r
      (recur (dec n) (exp r)))))

(defn ackermann' [[k & r :as s] n]
  (if (not (seq s))
    n
    (match [k n]
           [1 _] (recur r (*' 2 n))
           [2 _] (recur r (exp n))
           [3 _] (recur r (tetr n))
           [_ 1] (recur r 2)
           [_ 2] (recur r 4)
           [_ _] (recur (cons k (cons (dec k) r))
                        (dec n)))))