Предисловие
Недавно я начал изучать язык Clojure. Заинтересовал меня он потому, что это диалект lisp'a, выполняющийся на jvm. Сам я программирую на java, а lisp удивил меня своими скобочками. И тут такая смесь интересная. Да и с функциональным программированием тоже хотел познакомиться. Но тут же появилась проблема: как изучать clojure? Надо на нём что-то писать… А что? И пришёл к выводу, что очень удобно при изучении языка решить какие-нибудь несложные математические задачки: и к синтаксису привыкнешь, и с функционалом немного познакомишься. Для этого очень хорошо подходит Project Euler. Здесь я попробую показать, как начать работать с clojure и решить пару задач на нём. Я новичок в функциональном программировании и lisp'е, так что буду очень рад увидеть решения более близкие и красивые с точки зрения функционального и lisp'а.
Подготовка
Сперва надо конечно всё настроить, чтобы было где работать.
Clojure распространяется в виде jar-архива, как его подключать описано здесь.
Хороший, на мой взгляд, туториал можно найти тут.
Для clojure я использую emacs, как их подружить.
Вот, в принципе, и всё. Теперь можно приступить к решению этого самого Эйлера.
Задача 1
Задание
Найти сумму всех чисел от 1 до
Алгоритм
1. Создать последовательность чисел от 1 до
2. Отфильтровать eё, оставив только нужные нам числа.
3. Просуммировать все числа.
Код
(reduce +
(filter #(or (zero? (rem % 3))
(zero? (rem % 5)))
(range 1000)))
(range 1000) — последовательность чисел от 0 до 999
(#or (zero? (rem % 3)) (zero? (rem % 5))) — анонимная ф-ция, проверяющая делится ли аргумент % на 3 или 5. Если аргумент 1, то он обозначается %, иначе %1, %2, %3…
(filter ...) — фильтрует нашу пос-ть с помощью нашей анонимной ф-ции.
(reduce + ...) — ф-ция, которая в нашем случае складывает числа последовательности.
Вообще стоит отдельно посмотреть описание reduce, т.к. она часто используемая.
Так же документацию на любую функцию можно посмотреть с помощью (doc functionName) прямо в repl'е.
Задача 2
Задание
Найти сумму всех чётных чисел Фиббоначи меньших 4 миллионов.
Алгоритм
1. Строим последовательность Фиббоначи fib-seq (бесконечную, благодаря ленивой инициализации).
2. Строим вторую последовательность из чисел Фиббоначи меньших 4 миллионов.
3. Отбираем только чётные.
3. Суммируем.
Код
(def fib-seq
(lazy-cat [1 2] (map + fib-seq (rest fib-seq))))
(reduce +
(filter even?
(take-while #(< % 4000000) fib-seq))
Для меня тут самое сложно было осознать как задаётся пос-ть fib-seq в этом исполнении.
Она получается путём «склеивания» вектора [1 2] и пос-ти, которая вычисляется с помощью fib-seq. Как-то примерно так:
fib-seq = (1 2) + (3 5 8 13 ...) = fib-seq: (1 2 3 5 ...) + (rest fib-seq): (2 3 5 8 ...)
А дальше уже проще, с помощью take-while берём элементы из начала, пока они меньше 4000000, фильтруем и суммируем. Тут стоит отдельное внимание обратить на ф-цию map.
Задача промежуточная
Задание
Построить последовательность простых чисел (бесконечную).
Она пригодится ещё не в одной задаче из Эйлера.
Алгоритм
Идея и сама реализация взята отсюда.
В основе лежит решето Эратосфена. Решето — это у нас будет мап, в котором в качестве ключа будет выступать число, а значение — делитель числа. Сразу будем работать только с нечётными числами.
На каждом шагу мы будем брать очередного кандидата p, смотреть есть ли он в решете. Если нету — значит простое, иначе составное. Потом мы обновим решето, т.е. p — простое, то добавим в решето следующее число, делящееся на p, которого нет в решете. Если же p — составное, то мы его из решета достанем, достанем и его делитель, и добавим следующее число, которое делится на делитель и отсутствует в решете.
Код
Для реализаии напишем несколько ф-ций:
(defn enqueue [sieve candidate step]
(let [m (+ candidate step)]
(if (sieve m)
(recur sieve m step)
(assoc sieve m step))))
Эта ф-ция добавляет в решето следующее число за кандидатом, которое делится на step и которого ещё нет в решете.
(defn next-sieve [sieve candidate]
(if-let [step (sieve candidate)]
(-> (dissoc sieve candidate)
(enqueue candidate step))
(enqueue sieve candidate (+ candidate candidate))))
Эта ф-ция смотрит простой или составной кандидат и в зависимости от этого либо достаёт его из решета, либо нет. А потом добавляет следующий за ним, которого ещё нет в решете.
(defn next-primes [sieve candidate]
(if (sieve candidate)
(next-primes (next-sieve sieve candidate) (+ 2 candidate))
(cons candidate
(lazy-seq (next-primes (next-sieve sieve candidate) (+ 2 candidate))))))
Эта ф-ция и является основной, она возвращает пос-ть простых чисел. И она, к тому же, если я правильно понимаю, рекурсивная. На вход её даётся решето и кандидат. Она проверяет на простоту кандидата, и если он простой, то добавляет его к выходной пос-ти и вызывает себя рекурсивно с изменённым решетом и следующим кандидатом. Стоить отметить, что тут возвращается именно ленивая пос-ть (lazy-seq).
И теперь последняя фунцкия — создание глобальной последовательности простых чисел:
(def primes (concat [2] (next-primes {} 3)))
Задача 3
Задание
Найти максимальный простой делитель числа 600851475143.
Алгоритм
У нас будет 2 функции.
Одна вспомогательная, которая делит число на максимальную степень его делителя, чтобы «избавится» от делителя в числе.
Вторая основная, которая поочерёдно пробегает по всем простым числам и пытается наше число на них делить. И соответственно то простое число, после которого мы получили 1 и будет искомым.
Код
(defn divide-all [x divisor]
(if (zero? (rem x divisor))
(recur (/ x divisor) divisor)
x))
(defn max-prime-divisor [x ind]
(let [m (divide-all x (nth primes ind))]
(if (== m 1)
(nth primes ind)
(recur m (inc ind)))))
Тут мы использовали наши простые числа.
Вот и всё пока. Очень хотел бы увидеть какие-нибудь замечания, наставления на путь истинный с точки зрения самого языка и функционального программирования.