28 янв. 2010 г.

Clojure - Hello world!

Подсадил меня один хороший человек на Clojure - диалект Lisp, работающий в JVM.

Язык очень интересный, функциональный, особенно интересен после многолетнего использования объекто-ориентированной парадигмы.

Как же выглядит традицоинный Hello, world ! ряд Фибоначчи на clojure ?
(defn fib [n]
"Calculate n-th item of Fibonacci sequence"
(if (= n 0) 1
(if (= n 1) 2
(+ (fib (- n 2)) (fib (- n 1))))))
пробуем:
user=> (map fib (range 10))
(1 2 3 5 8 13 21 34 55 89)
Однако, если мы попробуем найти хотя бы 50ый элемент, то... наша попытка обречена на провал - мы впадём в оооочень глубокую рекурсию.

Выход конечно же использовать не обычную рекурсию, а хвостовую.
Итак, моя версия Hello, World:
(defn fib
"Calculate n-th item of Fibonacci sequence"
([n]
(if (zero? n) 1
(if (= n 1) 2
((fn
[n v2 v1] ; v2 = fib(n-2), v1 = fib(n-1)
(if (zero? n) (+ v2 v1)
(recur (dec n) v1 (+ v2 v1))))
(- n 2) 1 2)))))
вуаля:
user=> (map fib (range 20))
(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)
user=> (fib 100)
354224848179261915075
user=> (fib 500)
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125


updated. наиболее красивое решение, определяющее рекурсивно последовательность:
(def fibs (lazy-cat [1 2] (map + fibs (rest fibs))))


; элементы ряда, которые меньше, чем 100
user=> (take-while #(< % 100) fibs)
(1 2 3 5 8 13 21 34 55 89)
; первые 10 элементов ряда
user=> (take 10 fibs)
(1 2 3 5 8 13 21 34 55 89)

Матчасть: Programming Clojure by Stuart Halloway

В качестве практического применения можно попробовать решать задачи из Проекта «Эйлер».

ps. После того как сам решил несколько задач нашёл решение первых трёх задач на clojure.

2 комментария:

Shabunc комментирует...

Володя, я знал, я боялся, но знал - рано или поздно каждый программист так или иначе доходит до лиспа ))))

Eduard Bondarenko комментирует...

а вот еще решения euler на clojure
http://clojure-euler.wikispaces.com/