Ребенок по долгу службы борется с простыми числами и факторизацией целых (сокращает дроби, ищет НОК и НОД). В порядке общего образования решил написать ему программку для этих целей.
Для объяснения неиспорченному человеку решето Эратосфена, при всей своей неэффективности, подходит хорошо, им мы и воспользуемся для генерации простых чисел.
Весь этот текст - "литеральный хаскель", т.е. его можно спокойно скормить компилятору с расширением lhs и он скомпилируется. При этом все строчки, начинающиеся со значка цитирования, воспринимаются как текст программы, остальное - как просто текст. Также код может быть скрещен не с текстом, а с TeX. Я приведу текст программы целиком, а потом мы разберем его подробно:
canBeDividedBy n m = n `mod` m == 0
possibleDivisors n = takeWhile (<= half) primes
where half = n `div` 2
findDivisor n = find (canBeDividedBy n) (possibleDivisors n)
primes = 2 : primes' 3
where
primes' n = case (findDivisor n) of
Nothing -> n : primes' (n+2)
Just _ -> primes' (n+2)
factor n = factor' (possibleDivisors n) n
factor' [] n = [n]
factor' _ 1 = []
factor' p@(divisor : rest) n
|canBeDividedBy n divisor = divisor : factor' p (n `div` divisor)
| otherwise = factor' rest nНемного об указании типов в программе. Вообще говоря, оно не обязательно - компилятор выведет их сам. Но я буду указывать сигнатуры везде (о них можно спросить компилятор).
Нам потребуется функциональность из пары модулей (из Control.Monad - исключительно для
функции main, смысловой нагрузки не несет)
> import Control.Monad
> import Data.List
По ходу алгоритма нам зачастую придется проверять на делимость. Выразим это функией
canBeDividedBy n m. Функция будет возвращать истину, если n делится без остатка на m и ложь в противном случае. Сигнатура (имя и тип) функции выглядит так:
> canBeDividedBy :: (Integral n)=>n->n->Bool
Здесь сделано утверждение, что имеется функция canBeDividedBy, которая для любого типа n (n - переменная типа, т.е. обозначает некий конкретный тип), относящегося к классу целочисленных типов, отображает два значения типа n в значение типа Bool. Более корректно это прочитать следующим образом: n->(n->Bool). Т.е. значение типа n отображается в функцию из n в Bool. Фактически, все функции в Haskell имеют один аргумент. Целочисленных типов может быть много (Integer - с произвольной точностью, Int - машинное, переполнящееся,
Int32, Int16, Word8 и т.д. и никто не мешает наштамповать своих).
Применение функции в хаскеле записывается следующим образом: f arg1 arg2 .. argn, т.е. никаких скобок не ставится (только для обеспечения приоритета операций). Применение функции имеет приоритет, больший, чем любая операция, поэтому если первым аргументом мы хотим передать сумму, то должны записать так:
f (arg1 + arg2) arg3
Без скобок это выражение будет проинтерпретировано как (f arg1) + (arg2 arg3) что приведет к ошибке типизации при компиляции.
'+' в данном случае - инфиксная функция с "двумя аргументами" (см. выше). Но любая такая функция может быть записана в традиционном виде:
(+) 3 2
Верно и обратное: имея фунцию от двух аргументов с "нормальным" именем, мы можем использовать ее в инфиксном виде, заключив в обратные апострофы. Теперь, собственно, код:
> canBeDividedBy n m = n `mod` m == 0
mod - разумеется, функция получения остатка от деления
Мы будем пользоваться функией possibleDivisors. Она возвращает список простых чисел, которые могут быть делителями данного числа. Мы полагаем, что это первые простые числа, не превышающие половины числа.
> possibleDivisors :: (Integral n)=>n->[n]
Сигнатура говорит нам, что для целочисленного n возвращается список значение типа n.
Код функции:
> possibleDivisors n = takeWhile (<= half) primes
> where half = n `div` 2
Функция takeWhile - библиотечная. Она имеет следующую сигнатуру:
takeWhile :: (a->Bool)->[a]->[a]
Переводя на русский: отобрать из списка первые значения, удовлетворяющие некоторому условию.
Условие передается первым аргументом, это должна быть функция, проверяющая "подходящесть"
своего аргумента. В данном случае, это (<= half). Тут мы воспользовались синтаксическим
сахаром, который позволяет нам удобным образом частично применять инфиксные операции.
Называется такая форма sections. Таким образом, (<= half) - нужная нам функция. half
описан во второй строчке - это деленный нацело пополам аргумент. Без использования section
мы могли бы описать нашу функцию-условие следующим манером:
lessOrEqual a b = b <= a
Сигнатура того, что написано выше:
lessOrEqual::(Ord a)=>a->a->Bool
Частично примененная версия:
l = lessOrEqual 10
l :: (Num n)=>n->Bool
Мы могли бы не присваивать нашей функции имя, воспользовавшись lambda-выражением:
takeWhile (\a -> a <= half) primes
знак \ выбран за сходство с недописанной лямбдой.
Кроме того, мы могли бы написать нужное нам условие еще и так:
((>=) half)
Тут мы записали (>=) в стандартном (префиксном) виде и частично применили его (из двух аргументов передали один). Your mileage may vary.
Самое интересное в этом коде - primes. Это список всех простых чисел в природе. Его
мы опишем ниже.
> findDivisor :: (Integral n)=>n->Maybe n
Функция, отыскивающая делитель для числа среди его возможных делителей. Интересен возвращаемый тип: Maybe n. Maybe выражает концепцию данных, которых может и не быть. Значения могут принимать два вида (есть два конструктора):
Just a - все в порядке, значение есть
Nothing - значения нет
Maybe - это конструктор типов (тип, kind которого *->*). Не может быть значений типа Maybe, но могут быть значения типа
Maybe Int, Maybe String, Maybe Bool.
> findDivisor n = find (canBeDividedBy n) (possibleDivisors n)
find - библиотечная функция:
find :: (a->Bool)->[a]->Maybe a
Первый аргумент ее - критерий поиска, второй - список, в котором ищем. Результат - возможно, найденное значение. В нашем случае в качестве условия мы пользуемся частично примененный canBeDividedBy (добавь делитель - получишь ответ), а в качестве списка передаем список возможных делителей.
Переходим к самому интересному. Нам нужен список _всех_ простых чисел :) Да,именно так.
> primes :: (Integral n)=>[n]
Значение primes - полиморфно, т.е. существует для всех целочисленных типов. Это список целых. Немного о списках. Список, как и Maybe - конструктор типов. Не бывает значений типа "список", но бывают списки целых ([Int]), строк ([String]) и т.д. Так же, как и в случае с Maybe, значения могут быть двух видов:
[] - пустой список
x : xs - x, за которым следует еще список.
Мы можем записывать списки следующим образом: [1,2,3]. Это синтаксический сахар для "истинной" записи:
1 : (2 : ( 3 : [])) -- (операция (:) правоассоциативна)
Итак, код:
> primes = 2 : primes' 3
> where
> primes' n = case (findDivisor n) of
> Nothing -> n : primes' (n+2)
> Just _ -> primes' (n+2)
primes сообщает нам следующее: список всех простых чисел есть список, начинающийся с 2, за которой идет список, полученный как "вызов" primes' 3. primes' - вспомогательная функция описанная ниже. Она вычисляет список простых чисел начиная со своего аргумента. Как она это делает? Она ищет делитель своего
аргумента, пользуясь findDivisor. Да, findDivisor, сама пользуется primes, но нас это не смущает :) Мы считаем, что этот список существует (для его построения мы пользуемся корекурсией). Если делитель отсутствует (случай Nothing) то результат - наш аргумент к которому приписан результат primes' (n+2) (четные числа пропускаем). Если делитель найден (случай Just _), то результат просто равен результату primes' (n+2). Подчеркивание означает, что нас не интересует собственно найденный делитель, важно, что он есть. Вместо формы Just _ мы могли бы написать ключевое слово otherwise, т.е. для случая Nothing одно, для остальных - вот это
Итак, список получается бесконечный. но мы можем взять его, скажем, тысячный элемент:
primes !! 1000 == 7927
Мы можем попробовать его напечатать:
primes ==[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47....
Процесс печати, разумеется, займет бесконечное время.
Возможность поступать таким образом дает нам свойство вычислительной семантики хаскеля, называемое laziness, то бишь ленивость. Ничто не считается, пока не понадобится. Допустим, мы решили напечатать наш бесконечный список. Для этого нам потребуется напечатать первый элемент, а потом напечатать остаток списка (печать рекурсивна).
Первый элемент известен из выражения 2 : primes' 3, это 2. Ее печать вопросов не вызывает.
Теперь нам нужно напечатать следующий элемент. Как его найти? Это первый элемент в списке primes' 3. Чтобы его определить, сначала нужно поискать делитель 3. Для этого нам нужен кусок списка, не в котором простые числа, не превышающие половины 3. Этот кусок нам, разумеется уже известен (он пустой, у нас есть даже больше - целая 2 вначале). Таким образом, делитель не найден, поэтому результат (primes' 3) равен (3 : primes' 5), т.е. 3, за которой идет результат primes' 5. Дальше процесс повторяется.
Важно понимать, что primes не "вызывается" каждый раз при использовании. Понятие quot;вызова"
несколько надуманно для хаскеля. primes просто есть с момента своего описания. Просто он еще не вычислен до конца. И будет вычисляться по мере использования.
Из этого вытекает довольно забавный эффект (называется memoization). Если мы попросим, скажем, 10000 элемент primes - это займет некоторое время. Чтобы ответить на вопрос, чему он равен, придется вычислить 10000 элементов квадратичным алгоритмом. Но если мы сделаем это повторно, ответ получим почти мгновенно (за время, необходимое, чтобы добежать по списку до 10000 элемента). Все же уже посчитано.
Переходим к разложению числа на простые множители.
> factor :: (Integral n)=>n->[n]
> factor n = factor' (possibleDivisors n) n
Функция factor ничего умного не делает. Она "вызывает" вспомогательную функцию factor', передавая ей помимо числа еще и список возможных делителей этого числа.
> factor' :: (Integral n)=>[n]->n->[n]
Как работает функция factor'? Если список возможных делителей пуст, то результат (список делителей) состоит из самого числа (единицу мы старательно игнорируем):
> factor' [] n = [n]
Второй случай. Нас не интересует список возможных делителей, но само число равно 1. Результат закономерен - пустой список:
> factor' _ 1 = []
Рассмотрев тривиальные случаи, переходим к интересным:
> factor' p@(divisor : rest) n
> | canBeDividedBy n divisor = divisor : factor' p (n `div` divisor)
> | otherwise = factor' rest n
первый аргумент factor' записан интересным образом: p@(divisor : rest). Эта запись означает, что список, как минимум, не пуст, а состоит из чего-то, называемого divisor, за которым следует rest. Кроме того, на весь список мы можем ссылаться по имени p. Дальше идет рассмотрение случаев:
если n может быть поделен на divisor, то результат - divisor, за которым идет результат factor' с тем же набором потенциальных делителей, но числом, уже поделенным на делитель.
если n не делится на первый возможный делитель в списке, то результат - factor' для того же n но уже без "неудачного делителя".
Вот, собственно, и все. Сама программа очень коротенкая, описание заняло много. Пример:
factor 231132 == [2,2,3,11,17,103]
Функция main до бесконечности читает строчку за строчкой, раскладывает на множители и все сначала:
> main = forever (do
> num <- readLn
> print (factor num))
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
perikov's journal
