Метод породить и проверить
вычисление остатка от деления m на n.
Пусть m=17, n=5
17 12 7 2 -3 …
mod’ m n =
head (dropWhile (>=n)
(iterate (-n) m) )
(есть стандартная Ф mod)
когда мы исп беск списки то алгоритмы можно рассматривать как совокупность процессов, связанных потоками значений. Это другой взгляд на программу. Можно считать что эти процессы работают параллельно, потребляя значение с входных потоков и направляя результат в выходной поток. Это важная идея, которую мы рассмотрим. Можно описывать на функц языке || процессы.
Сети связанных процессов
Пусть задана ф, она работает с беск списокм, ей базовый случай не нужен. Она потребляет элементы списка чисел и генерирует значения на единицу больше.
Plus1 (x:xs)= (x+1) : plus1 xs
То есть
Plus1 = map (+1)
Список всех целых чисел:
Целые = 1: plus1 целые
целые
1
Plus1
1
+1
целые
эту схему можно читать как электронную схему, с обратной связью.
Определение ф чисел фибоначи
fib 0 = 1
fib 1 = 1
fib n = fib (n-2)+ fib(n-1)
это определние многократно вычисляет…. Лучше результат объединить в картеж. Но можно вычисление чисел фибаначи представить в виде процессов обрабатывающих потоки.
Схема. 2 конструктора списков, а + это ф sum
1 fibs
+
1 F1
sum (x:xs) (y:ys) = x+y:sum xs ys – сложение значений двух потоков.
Построив такую схему можно по ней легко написать программу
Поток чисел Фибоначчи:
fibs = 1:f1
where
f1 = 1:sum1 fibs f1
Задача хэмминга
требуется построить последовательность, которая обл след 2 мя свойствами.
1 этой последовательности принадлежит единица
2 условие: если x принадлежит последовательности то ей принадлежат 2x, 3x, 5x
3 этой последовательности не принадлежат другие значения кроме определенных в пунктах 1 и 2
Нам понадобятся след функции
mult2 = map (*2)
mult3 = map (*3)
mult5 = map (*5)
Три процесса, они получ на входе беск список и получают…….
Нам понадобится процесс join,который объединяет два потока
*2
join
1
X23 x
join
X235
*3
*5
Join xx@(x:xs) yy@(y:ys)
| x==y = join xs yy
| x<y = x : join xs yy
| otherwise = y:joinxx ys
Соединяются в один общий поток, в нем дубликатов не будет.
x = 1 : x235
where
x235 = join x23 x5
x23 = join x2x3
x2 = mult2 x
x3 = mult3 x
x5 = mult5 x
процессы могут быть и рекурсивными.
Решето Эратосфена
Алг генерации простых чисел.
1 берем список [2…].
2 его голова – простое число.
3 удаляем из хвоста элементы, кратные голове.
4 делаем тоже самое с хвостом.
sieve :: [Int] -> [Int]
sieve (x:xs) =
x: sieve [y| y<-xs, y `mod` x /=0]
в хаскеле строгая система типов. На основании которой компилятор проверяет условие чтобы каждое выражение получало … какое бы он не получил выражение в нем должны исп такие….
X= 5 + True
Мы здесь имеет +, конфликт типов.
Y = 5
Z = y x
Здесь тоже нарушено, переменная Y получае значение 5, это число а в след строке z применением y к x. Все подвыражения должны давать результаты подходящие для дальнейших вычислений. Это условие уточняется введением понятия типа данных.
Компилятор с хаскеля построив программу на базовом языке запускает алгоритм проверки типов. Если он обнаружит несовместимость типов, то будет выдано сообщение об ошибке а иначе компилятор сгенерирует код, исполняемый программой.
Такая проверка типов назыв статической. Она вып в то время, когда программа еще ничего не делает.
Бывают языки с динамической проверкой типов.
Она вып на этапе выполнения программы, тогда все значения в программе дополняются информацией о типе.
5+true
+
/ \
5 true
Int 5 bool true
Примером языка с динамич проверкой типов явл язык LISP.
Проверка типов делает программу безопасной.
Безопасность программы на хаскеле в том, что если она скомпилирована то она уже не прервет свою работу из-за несоответствия типов и не будет вести себя непредсказуемым образом.