This shows you the differences between two versions of the page.
courses:functional_programming:lectures [2018/12/03 17:00] vnikolenko |
courses:functional_programming:lectures [2022/12/10 09:08] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Программа ====== | ||
- | ===== Введение ===== | ||
- | * Особенности функционального программирования(ФП) | ||
- | * Отличия ФП от императивного программирования | ||
- | * Сильные и слабые стороны ФП | ||
- | | ||
- | ===== Лямбда-исчиcление ===== | ||
- | * Формализации понятия алгоритма | ||
- | * Чистое λ-исчисление | ||
- | * Свободные и связанные переменные | ||
- | * Комбинаторы | ||
- | * Каррирование | ||
- | * Подстановка | ||
- | * Правила преобразования | ||
- | * Эквивалентность λ-термов | ||
- | | ||
- | ===== Рекурсия и редукция ===== | ||
- | * Теорема о неподвижной точке, Y-комбинатор | ||
- | * Совместимые (с λ-исчислением) отношения, отношения редукции, отношения равенства(конгруэнтности) | ||
- | * Одношаговая β-редукция, β-редукция, β-равенство | ||
- | * Редукционные графы | ||
- | * Нормальная форма(nf) | ||
- | * Ненормализуемые, слабо нормализуемые и сильно нормализуемые термы | ||
- | * Теорема Чёрча-Россера, теорема об общем редукте, теорема о единственности nf | ||
- | * Стратегии редукции | ||
- | * Головная нормальная форма, слабая головная нормальная форма | ||
- | * Теорема о нормализации | ||
- | |||
- | |||
- | ===== Просто(е) типизированное лямбда-исчисление ===== | ||
- | * Понятие типа (предназначение типов) | ||
- | * Просто(е) типизированное λ-исчисление (STLC) | ||
- | * Типизация по Чёрчу и Карри | ||
- | * Множество типов, предтермы, утверждение о типизации, контекст | ||
- | * Правила типизации | ||
- | * Леммы генерации, о контекстах | ||
- | * Теорема о редукции субъекта | ||
- | * Теорема о единственности типа для типизации по Чёрчу | ||
- | * Теорема о нормализации | ||
- | | ||
- | ===== Введение в язык Haskell ===== | ||
- | * Базовые типы | ||
- | * Связывание | ||
- | * Определение функций | ||
- | * Охранные выражения | ||
- | * Конструкции where и let...in | ||
- | * Операторы и сечения | ||
- | * Модули | ||
- | * Реализации языка Haskell и инфраструктура (cabal, stack, hackage, hoogle) | ||
- | |||
- | ===== Основы программирования в Haskell ===== | ||
- | * Ленивые и строгие вычисления | ||
- | * Алгебраические типы данных: декартово произведение и размеченное объединение | ||
- | * Сопоставление с образцом | ||
- | * Работа со списками | ||
- | * Генераторы списков | ||
- | * Функции высших порядков над списками | ||
- | |||
- | ===== Классы типов ===== | ||
- | * Виды полиморфизма | ||
- | * Классы типов | ||
- | * Сравнение с другими языками программирования | ||
- | * Обзор стандартных классов типов(Eq, Ord, Enum, Bounded, Show, Read, Num, Fractional, Integral) | ||
- | * Особенности внутренней реализации классов типов (реализация с помощью словарей) | ||
- | |||
- | ===== Свертки и моноиды ===== | ||
- | * Левая и правая свертки (foldr, foldl, foldl', foldr1, foldl1) | ||
- | * Родственные сверткам функции (scanl, scanr, unfold) | ||
- | * Semigroup a, закон для полугруппы | ||
- | * Semigroup a => Monoid a, законы для моноида | ||
- | * Стандартные моноиды ([a], Any, All, Product a, Sum a, Endo a, Dual a, Last a, First a) | ||
- | * Foldable | ||
- | |||
- | ===== Функторы ===== | ||
- | * Функторы | ||
- | * Законы для функторов | ||
- | * Аппликативные функторы | ||
- | * Законы для аппликативных функторов | ||
- | * Функция как функтор, аппликативный функтор | ||
- | * Список как аппликативный функтор, ZipList | ||
- | |||
- | <del> | ||
- | ===== Использование аппликативных функторов ===== | ||
- | * Аппликативные парсеры | ||
- | * Класс типов Alternative | ||
- | * Законы класса Alternative | ||
- | * Класс типов Traversable | ||
- | * Законы класса Traversable | ||
- | </del> | ||
- | |||
- | ===== Монады ===== | ||
- | * Стрелка Клейсли | ||
- | * Понятие монады | ||
- | * Класс типов Monad | ||
- | * Монады Identity, Maybe | ||
- | * Список как монада | ||
- | * Отличие монад от аппликативных функторов | ||
- | |||
- | ===== Стандартные монады ===== | ||
- | * Reader | ||
- | * Writer | ||
- | * State | ||
- | * IO | ||
- | * Функции ввода-вывода | ||
- | |||
- | ===== Трансформеры монад ===== | ||
- | * Класс типов MonadPlus | ||
- | * Законы класса MonadPlus | ||
- | * Монада Except | ||
- | * Мультипараметрические классы типов | ||
- | * Трансформеры монад | ||
- | * Законы для класса типов MonadTrans | ||
- | * Стандартные трансформеры библиотеки mtl | ||
- | |||
- | ===== Вывод типов* ===== | ||
- | ===== Программирование с зависимыми типами* ===== | ||
- | ===== Чисто функциональные структуры данных* ===== | ||
- | ===== ФП в mainstream-языках* ===== | ||
- | ===== GHC Core* ===== |