1 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Потоки. «Завязывание узлов» Напишем программу для получения последовательности чисел Фибоначчи: fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...] fib1 = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...] + fib2 = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...] zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] zipWith f (a:as) (b:bs) = (f a b) : (zipWith f as bs) zipWith _ _ _ = [] plusLists = zipWith (+) -- функция почленного сложения списков multLists = zipWith (*) -- функция почленного умножения списков fib = 1:fib2 fib1 = 0:fib fib2 = zipWith (+) fib fib1

2 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Потоки. «Завязывание узлов» Операции над потоками: fib where fib = 1:fib2 fib2 = zipWith (+) fib1 fib fib1 = 0:fib Получаем готовое выражение для потока fib :

3 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Пример: описание грамматики языка Рассматриваем языки, описываемые регулярными выражениями, например: vowel = 'a' | 'o' consonant = 'c' | 'l' | 'k' | 'b' letter = vowel | consonant open = consonant vowel | consonant vowel vowel closed = open consonant syllable = open | closed Цель: создавать языки с помощью операций type Language = String -> Bool vowel = (symbol 'a') `alt` (symbol 'o') consonant = (symbol 'c') `alt` (symbol 'l') `alt` (symbol 'k') `alt` (symbol 'b') letter = vowel `alt` consonant open = (consonant `cat` vowel) `alt` ((consonant `cat` vowel) `cat` vowel) closed = open `cat` consonant syllable = open `alt` closed Проверка принадлежности слова языку: syllable "cool"

4 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Программирование регулярных выражений type Language = String -> Bool symbol :: Char -> Language alt :: Language -> Language -> Language cat :: Language -> Language -> Language symbol c word = [c] == word (lang1 `alt` lang2) word = (lang1 word) || (lang2 word) (lang1 `cat` lang2) [] = (lang1 []) && (lang2 []) (lang1 `cat` lang2) = (lang1 [] && lang2 word) || (lang1' `cat` lang2) s where lang1' w = lang1 (x:w)

5 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Расширение техники работы с регулярными выражениями ( ) :: Language -> String -> Language (lang word) w = (w == word) || (lang w) ( ) :: Language -> String -> Language (lang word) w = (w /= word) && (lang w) iter :: Language -> Language -- iter exp ~ exp* iter lang [] = True iter lang w = (lang' w) || ((lang' `cat` (iter lang')) w) where lang' = lang [] poss :: Language -> Language -- poss exp ~ [exp] poss lang = lang [] digit = symbol '0' `alt` symbol '1' `alt` symbol '2' `alt` symbol '3' `alt` symbol '4' `alt` symbol '5' `alt` symbol '6' `alt` symbol '7' `alt` symbol '8' `alt` symbol '9' unsigned = digit `cat` (iter digit) integral = poss ((symbol '+') `alt` (symbol '-')) `cat` unsigned number = integral `cat` poss (symbol '.' `cat` unsigned) `cat` poss (symbol 'e' `cat` integral)