Математическое введение в декларативное программирование. Зюзысов В.М. - 79 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

zip xs ys = [] -- один из списков есть []
> zip [1,2,3] [4,5,6]
[(1,4),(2,5),(3,6)]
> zip [1,2,3] ones
[(1,1),(2,1),(3,1)]
Определение
ones
выше является примером определения циклического списка. В
большинстве обстоятельств ленивые вычисления имеют важное значение для эффектив-
ности, так как при реализации можно хранить бесконечные списки как циклические
структуры; таким способом сохраняется пространство.
В качестве другого примера использования цикличности, можно взять последова-
тельность Фибоначчи. Числа Фибоначчи можно эффективно вычислить как следующую
бесконечную последовательность с помощью формы
2
:
fib :: [Integer]
fib = 1 : 1 : [x+y | (x,y) <- zip fib (tail fib)]
Первые 10 чисел Фибоначчи получаются просто:
> take 10 fib
[1,1,2,3,5,8,13,21,34,55]
Отметим, что бесконечный список
fib
, определяется с помощью самого себя.
Рассмотрим другие примеры бесконечных структур. Определим список из совер-
шенных чисел.
-- список делителей числа n
factors :: Integer -> [Integer]
factors n = [ i | i<-[1..n-1], n `mod` i == 0 ]
-- определение совершенного числа
perfect :: Integer -> Bool
perfect n = sum (factors n) == n
-- список совершенных чисел
perfects :: [Integer]
perfects = filter perfect [1..] –- встроенная функция filter выделяет из
-- списка элементы с указанным свойством
> take 3 perfects
[6,28,496]
Определим бесконечный список простых чисел с помощью решета Эратосфена.
primes :: [Integer]
2
Форма [<элемент>|<элемент> <– <список>, <логическое условие>] играет в языке Haskell такую
же роль, как определение множества элементов, удовлетворяющих некоторому свойству; обычная запись в
математике имеет вид {x | x∈X & P(x)}. Использование форм позволяет создавать ясные и короткие про-
граммы. Пример «быстрой сортировки»:
quicksort :: [Char] -> [Char]
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y <= x] ++
[x] ++
quicksort [y | y <- xs, y > x]
> quicksort "Why use Haskell?"
" ?HWaeehkllssuy"
79

Страницы