Темы лекций и семинаров по языку Haskell
Январь 2021 г.
-
Классификация языков программирования.
Императивные и функциональные языки. Введение в язык Haskell.
Функции и списки, примеры их определения и использования.
Примеры несложных программ: тест простоты, совершенные числа.
-
Приемы программирования на языке Haskell. Примеры программ:
задача о рюкзаке и полусовершенные числа. List Comprehension
как один из главных приемов программирования в Haskell.
Задача о Пифагоровых тройках. Pattern Matching (подбор шаблона)
и примеры использования этого приема. Конструкция where.
Обычный и расширенный алгоритмы Евклида. Конструкция
let -- in.
-
Функции, аргументами которых также являются функции.
Стандартные функции высшего порядка: filter, foldl, foldr,
zip, take, span и др. Функция map.
Типичная схема вычисления функции на списках,
использующая pattern matching и рекурсию.
-
Хвостовая рекурсия (tail recursion) или рекурсия
с использованием аккумулятора как главный прием
программирования в функциональных языках.
Примеры программ, использующих хвостовую рекурсию,
и сравнение хвостовой рекурсии с наивной рекурсией.
Схема построения цикла с помощью инварианта и ее реализация
с помощью хвостовой рекурсии в Haskell. Примеры: вычисление
значения многочлена по схеме Горнера и другие функции
для работы с многочленами. Вычисление различных средних
значений для списков.
-
Элементы теории чисел и реализация алгоритмов теории чисел
в Haskell. Кольцо вычетов по модулю m как фактор-кольцо кольца
целых чисел. Китайская теорема об остатках, Малая теорема Ферма,
теорема Эйлера и вычисление функции Эйлера. Схема асимметричного
кодирования с открытым ключом RSA.
-
Алгоритмы разложения на множители (факторизации) Полларда:
ρ-алгоритм, p-1-алгоритм и их реализация на языке Haskell.
-
Работа с вещественными числами в Haskell. Вычисление суммы
ряда с использованием схемы хвостовой рекурсии. Вычисление
стандартных функций с помощью суммирования рядов путем сведения
суммы ряда для больших значений x к суммированию ряда для
небольших значений. Примеры: вычисление значения sin(x) и
acrtg(x).
-
Вычисление квадратного корня и корня n-ой степени методом
итераций Ньютона в Haskell. Вычисление log(x) путем
использования схемы построения цикла с помощью инварианта
и применения хвостовой рекурсии.
-
Модули и конструирование собственных типов в Haskell.
Примеры определения новых типов. Модуль R2Graph, типы
R2Vector, R2Point и их использование для решения
геометрических задач на плоскости.
-
Обработка текстов в Haskell. Реализация компилятора и
интерпретатора формул на Haskell. Этапы компиляции:
сканер и парсер. Обратная польская запись формулы.
Реализация парсера с помощью алгоритма Дийкстры
"Сортировочная станция" (Shunting Yard). Вычисление
значения обратной польской записи формулы с помощью
стекового вычислителя. Реализация проекта
"Компилятор формул" на Haskell.
-
Грязный (tainted) код в Haskell. Файловый ввод-вывод и
чтение данных с консоли, тип IO() функций. Реализация
функции main с помощью рекурсии, конструкция "do"
и ее использование в грязном коде. Оформление компилятора
формул в виде исполняемого приложения с использованием
грязного кода.
-
Тип данных Map (отображение, словарь) в Haskell,
модуль Data.Map. Проект "Записная книжка".