falgebra.clj

;; F-Algebra recursion schemes:

(defprotocol Functor
  "Functor"
  (fmap [xs f]))


(defn cata [alg f] (alg (fmap f (partial cata alg))))

(defn ana [coalg a] (fmap (coalg a) (partial ana coalg)))

(defn hylo [alg coalg a] (cata alg (ana coalg a)))

;; Factorial via ListF example:

(deftype ListFCons [value rec]
  Functor
  (fmap [this f] (ListFCons. value (f rec))))

(deftype ListFNull []
  Functor
  (fmap [this f] (ListFNull.)))

;; Product algebra. Equivalent to (reduce * 1) but for a single step only
(defmulti productAlg class)
(defmethod productAlg ListFCons [l] (* (.value l) (.rec l)))
(defmethod productAlg ListFNull [_] 1)

;; [1..n] coalgebra. Equivalent to  (comp (partial range 1) (partial + 1)) but for a single step only
(defn oneToNCoalg [n] (if (= n 0) (ListFNull.) (ListFCons. n (- n 1))))

(def factorial (partial hylo productAlg oneToNCoalg))

(factorial 5)