Функциональное программирование 2025/2026 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== Функциональное программирование == Курс по выбору для студентов 3 и 4 курса ФКН ВШЭ, 1 и 2…»)
 
(→‎Домашнее заданее)
 
(не показано 13 промежуточных версии 2 участников)
Строка 1: Строка 1:
 
== Функциональное программирование ==
 
== Функциональное программирование ==
  
−
Курс по выбору для студентов 3 и 4 курса ФКН ВШЭ, 1 и 2 модуль 2024 г. Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП  в целом и популярного языка Haskell в частности. Попутно сообщаются начальные сведения из области лямбда-исчислений, теории типов, теории категорий.
+
Курс по выбору для студентов 3 и 4 курса ФКН ВШЭ, 1 и 2 модуль 2025 г. Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП  в целом и популярного языка Haskell в частности. Попутно сообщаются начальные сведения из области лямбда-исчислений, теории типов, теории категорий.
  
 
== Преподаватели ==
 
== Преподаватели ==
Строка 7: Строка 7:
 
Лектор: Евгений Дашков, ТГ: [https://t.me/edashkov @edashkov], edashkov@gmail.com.
 
Лектор: Евгений Дашков, ТГ: [https://t.me/edashkov @edashkov], edashkov@gmail.com.
  
−
Лекции проводятся очно по пятницам с 1810 до 1930 в ауд. G603. [https://us06web.zoom.us/j/84196980093?pwd=Q2pm3yieJ2JFJWzg8AFiSVikN2nBSn.1 Ссылка] на трансляцию лекций.
+
Лекции проводятся очно по четвергам с 1300 до 1420 в ауд. R407.  
  
 
Семинарист: Павел Соколов, ТГ: [https://t.me/TurtlePU @TurtlePU].
 
Семинарист: Павел Соколов, ТГ: [https://t.me/TurtlePU @TurtlePU].
  
−
Учебный ассистент: Ислам Талипов, ТГ: [https://t.me/lishy2 @lishy2].
+
Учебный ассистент: Максим Чурилов, ТГ: [https://t.me/maxchrlv @maxchrlv].
  
 
== Текущая успеваемость ==
 
== Текущая успеваемость ==
  
−
[https://docs.google.com/spreadsheets/d/1TRg6E9I-arH81yIzJG73gBf29otro-x1D9icfMcqiuU/edit?usp=sharing Таблица].
+
[https://docs.google.com/spreadsheets/d/1EublfZQSZ2yAMwob-rMQmbFv6JFe-TJ1mfehuTdh9jY/edit?usp=drive_link Таблица].
  
 
== Setting up ==
 
== Setting up ==
  
−
<ol>
+
# Установка компилятора, системы сборки, языкового сервера
−
  <li>Если вы пользуетесь Windows, установите WSL2, если ещё не.</li>
+
#* (Рекомендованный способ) Через [https://www.haskell.org/ghcup/ ghcup]:
−
  <li>
+
#*# Скачайте [https://downloads.haskell.org/~ghcup/ бинарный файл] сами либо введите одну любимую команду:
−
    Установите [https://www.haskell.org/ghcup/ ghcup] &mdash; скачайте [https://downloads.haskell.org/~ghcup/ бинарный файл] сами
+
#*#* '''MacOS''': <code>brew install ghcup</code>
−
    либо введите одну любимую команду:
+
#*#* '''Arch'''-based distros: <code>yay -S ghcup-hs-bin</code>
−
    <ul>
+
#*#* '''WSL2''', '''MacOS''' >= 10.13, '''Linux''': <code>curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh</code>
−
      <li> '''MacOS''': <pre>brew install ghcup</pre></li>
+
#*#* '''Windows''': Команда доступна по [https://www.haskell.org/ghcup/install/#installation ссылке].
−
      <li> '''Arch'''-based distros: <pre>yay -S ghcup-hs-bin</pre></li>
+
#*# Убедитесь, что путь до места установки <code>ghcup</code> (скорее всего, <code>~/.ghcup/bin</code> либо <code>C:/ghcup</code>) содержится в <code>$PATH</code> &mdash; запустите <code>ghcup list</code>. При необходимости добавьте этот путь сами.
−
      <li> '''WSL2''', '''MacOS''' >= 10.13, '''Linux''': <pre>curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh</pre></li>
+
#*# Установите '''<code style="background-color:black;color:rgb(0,255,0)">recommended</code>''' версии компилятора, системы сборки и языкового сервера:
−
      <li> '''Windows Powershell''' (cringe): Команда доступна по [https://www.haskell.org/ghcup/install/#installation ссылке]</li>
+
#*## <code>ghcup install ghc recommended</code>
−
    </ul>
+
#*## <code>ghcup install stack recommended</code>
−
  </li>
+
#*## <code>ghcup install hls recommended</code>
−
  <li>Убедитесь, что путь до места установки <code>ghcup</code> содержится в <code>$PATH</code> &mdash; запустите <code>ghcup list</code>.</li>
+
#*# Создайте символические ссылки на установленные версии программ:
−
  <li>
+
#*## <code>ghcup set ghc recommended</code>
−
    Установите '''<code style="background-color:black;color:rgb(0,255,0)">recommended</code>''' версии компилятора, пакетного менеджера и языкового сервера:<pre>
+
#*## <code>ghcup set stack recommended</code>
−
ghcup install ghc recommended
+
#*## <code>ghcup set hls recommended</code>
−
ghcup install cabal recommended
+
#* (Если предыдущий вариант не сработал) '''Windows''':
−
ghcup install hls recommended</pre>
+
#*# <code>choco install haskell-language-server haskell-stack</code>
−
  </li>
+
#*# <code>refreshenv</code>
−
  <li>Убедитесь, что путь <code>~/.ghcup/bin</code> содержится в <code>$PATH</code>. При необходимости добавьте этот путь сами.</li>
+
# Настройте LSP client в своей любимой среде разработки:
−
  <li>
+
#* Для '''VS Code''' есть [https://github.com/haskell/vscode-haskell плагин]. Скорее всего, при запуске он предложит выбрать, каким образом ему находить HLS: через GHCup или вручную через PATH. Если устанавливали через <code>chocolatey</code>, выбирайте вторую опцию; иначе сначала попробуйте через GHCup.
−
    Создайте символические ссылки на установленные версии программ:<pre>
+
#* В '''NeoVim''' настройте [https://github.com/neovim/nvim-lspconfig nvim-lspconfig], он знает про HLS.
−
ghcup set ghc recommended
+
#* Инструкцию для других сред можно найти [https://haskell-language-server.readthedocs.io/en/latest/configuration.html#configuring-your-editor здесь].
−
ghcup set cabal recommended
+
# (Опционально) Установите [https://hoogle.haskell.org Hoogle] локально:
−
ghcup set hls recommended</pre>
+
## <code>stack install hoogle</code>
−
  </li>
+
## Теперь можно пользоваться Hoogle прямо из ghci с помощью команды <code>:!hoogle</code> и <code>:!hoogle --info</code>
−
  <li>
+
−
    Настройте LSP client в своей любимой среде разработки:
+
−
    <ul>
+
−
      <li>Для '''VS Code''' есть [https://github.com/haskell/vscode-haskell плагин], он должен обнаружить HLS самостоятельно.</li>
+
−
      <li>В '''NeoVim''' настройте [https://github.com/neovim/nvim-lspconfig nvim-lspconfig], он знает про HLS.</li>
+
−
      <li>Инструкцию для других сред можно найти [https://haskell-language-server.readthedocs.io/en/latest/configuration.html#configuring-your-editor здесь].</li>
+
−
    </ul>
+
−
  </li>
+
−
  <li>Опционально &mdash; установите [https://hoogle.haskell.org Hoogle] локально:
+
−
    <ol>
+
−
      <li><code>cabal install hoogle</code></li>
+
−
      <li>
+
−
        Допишите в файл <code>~/.ghci</code> следующее:<pre>
+
−
:def hoogle \x -> return $ ":!hoogle \"" ++ x ++ "\""
+
−
:def hdoc \x -> return $ ":!hoogle --info \"" ++ x ++ "\""</pre>
+
−
      </li>
+
−
      <li>Теперь можно пользоваться Hoogle прямо из ghci с помощью команд <code>:hoogle</code> и <code>:hdoc</code></li>
+
−
    </ol>
+
−
  </li>
+
−
</ol>
+
  
 
== Листки и код для лекций и семинаров ==
 
== Листки и код для лекций и семинаров ==
Строка 93: Строка 73:
 
! Набор задач !! colspan="11" | Срок сдачи
 
! Набор задач !! colspan="11" | Срок сдачи
 
|-
 
|-
−
| [https://drive.google.com/file/d/1MBSr_Ryb9Xw7HxYUU1vC6WfMHF_YJh9f/view?usp=sharing ДЗ 1] || 09.10 23:59
+
| [https://drive.google.com/file/d/1MBSr_Ryb9Xw7HxYUU1vC6WfMHF_YJh9f/view?usp=sharing ДЗ 1] || 12.10 23:59
 
|-
 
|-
−
| [https://drive.google.com/file/d/1IK0SZGj78veayMS6_1BS7lT9HncbNwTY/view?usp=drive_link Д3 2] || 01.11 23:59
+
| [https://drive.google.com/file/d/1IK0SZGj78veayMS6_1BS7lT9HncbNwTY/view?usp=drive_link Д3 2] || 24.10 23:59
 
|-
 
|-
−
| [https://drive.google.com/file/d/1UuZWdkEQsKpS1xDVXK1WqOy1tWP1KlJC/view?usp=drive_link ДЗ 3] || 19.11
+
| [https://drive.google.com/file/d/1UuZWdkEQsKpS1xDVXK1WqOy1tWP1KlJC/view?usp=drive_link ДЗ 3] || 28.11 23:59
 
|-
 
|-
−
| [https://drive.google.com/file/d/13XvUC48ga4xjTPbVl1isVI0GIxFT0Y_u/view?usp=drive_link ДЗ 4] || 07.12
+
| [https://drive.google.com/file/d/13XvUC48ga4xjTPbVl1isVI0GIxFT0Y_u/view?usp=drive_link ДЗ 4] || 9.12 23:59
 +
<!--
 
|-
 
|-
 
| [https://drive.google.com/file/d/14On7LzhyaasXiKm619EtKy7lqD_g9SF1/view?usp=drive_link ДЗ 5] || 20.12
 
| [https://drive.google.com/file/d/14On7LzhyaasXiKm619EtKy7lqD_g9SF1/view?usp=drive_link ДЗ 5] || 20.12
 +
-->
 
|}
 
|}
−
 
−
<!--
 
−
 
  
  
 
'''Срок сдачи задания устанавливается семинаристом группы.'''
 
'''Срок сдачи задания устанавливается семинаристом группы.'''
  
−
Сдавать решения нужно в [https://classroom.google.com/c/NjI3MDg1MDM2MTY0?cjc=wqtrr7k Classroom].
+
Сдавать решения нужно в [https://classroom.google.com/c/ODExMDgyMzM0ODMy?cjc=thn3zx6y Classroom].
−
 
+
−
-->
+
  
 
== Контрольная работа ==
 
== Контрольная работа ==

Текущая версия на 13:11, 25 ноября 2025

Функциональное программирование

Курс по выбору для студентов 3 и 4 курса ФКН ВШЭ, 1 и 2 модуль 2025 г. Функциональное программирование (ФП) представляет собой теоретически изящный, выдержавший проверку временем на практике и оказавший заметное влияние на технологии программирования вообще подход к созданию ПО. Курс посвящен основам ФП в целом и популярного языка Haskell в частности. Попутно сообщаются начальные сведения из области лямбда-исчислений, теории типов, теории категорий.

Преподаватели

Лектор: Евгений Дашков, ТГ: @edashkov, edashkov@gmail.com.

Лекции проводятся очно по четвергам с 1300 до 1420 в ауд. R407.

Семинарист: Павел Соколов, ТГ: @TurtlePU.

Учебный ассистент: Максим Чурилов, ТГ: @maxchrlv.

Текущая успеваемость

Таблица.

Setting up

  1. Установка компилятора, системы сборки, языкового сервера
    • (Рекомендованный способ) Через ghcup:
      1. Скачайте бинарный файл сами либо введите одну любимую команду:
        • MacOS: brew install ghcup
        • Arch-based distros: yay -S ghcup-hs-bin
        • WSL2, MacOS >= 10.13, Linux: curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh
        • Windows: Команда доступна по ссылке.
      2. Убедитесь, что путь до места установки ghcup (скорее всего, ~/.ghcup/bin либо C:/ghcup) содержится в $PATH — запустите ghcup list. При необходимости добавьте этот путь сами.
      3. Установите recommended версии компилятора, системы сборки и языкового сервера:
        1. ghcup install ghc recommended
        2. ghcup install stack recommended
        3. ghcup install hls recommended
      4. Создайте символические ссылки на установленные версии программ:
        1. ghcup set ghc recommended
        2. ghcup set stack recommended
        3. ghcup set hls recommended
    • (Если предыдущий вариант не сработал) Windows:
      1. choco install haskell-language-server haskell-stack
      2. refreshenv
  2. Настройте LSP client в своей любимой среде разработки:
    • Для VS Code есть плагин. Скорее всего, при запуске он предложит выбрать, каким образом ему находить HLS: через GHCup или вручную через PATH. Если устанавливали через chocolatey, выбирайте вторую опцию; иначе сначала попробуйте через GHCup.
    • В NeoVim настройте nvim-lspconfig, он знает про HLS.
    • Инструкцию для других сред можно найти здесь.
  3. (Опционально) Установите Hoogle локально:
    1. stack install hoogle
    2. Теперь можно пользоваться Hoogle прямо из ghci с помощью команды :!hoogle и :!hoogle --info

Листки и код для лекций и семинаров

Домашнее заданее

Домашнее задание выдается частями приблизительно раз в две недели; при выдаче каждой части указывается срок ее сдачи. Все задания письменные.

Каждая задача оценивается дробным значением от 0 до 1 балла. Задачи делятся на «обыкновенные» и «повышенной сложности». Все задания в целом оцениваются числом:

ДЗ = 8 * обыкн + 2 * сложн, где

обыкн = (сумма баллов, полученных за обыкновенные задачи) / (количество обыкновенных задач в домашнем задании),

сложн = (сумма баллов, полученных за задачи повышенной сложности) / (количество задач повышенной сложности в домашнем задании).

Преподаватель вправе потребовать от любого студента «защитить» (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля.


Набор задач Срок сдачи
ДЗ 1 12.10 23:59
Д3 2 24.10 23:59
ДЗ 3 28.11 23:59
ДЗ 4 9.12 23:59


Срок сдачи задания устанавливается семинаристом группы.

Сдавать решения нужно в Classroom.

Контрольная работа

Письменная Контрольная работа проводится в начале второго модуля. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем.

Каждая задача контрольной работы оценивается дробным значением от 0 до 1 балла. Контрольная оцениваются значением:

КР = 10 * (сумма полученных баллов за все задачи) / (количество задач в контрольной работе).

Экзамен

Письменный экзамен проводится в конце курса. Допускается использование собственных записей студента и явно разрешенных локальных справочных систем. Каждая задача экзамена оценивается дробным значением от 0 до 1 балла. Экзамен оценивается числом:

Экз = min (10, (взвешенная сумма баллов, полученных за все задачи)).

При этом веса задач положительны и устанавливаются таким образом, что в сумме дают не менее 10.

Самостоятельная работа (мини-проект)

При желании студенты согласовывают с семинаристом задачу для индивидуальной самостоятельной работы. При этом предполагаются решение достаточно сложной задачи по программированию и самостоятельное получение студентом недостающих сведений. Самостоятельная работа должна быть сдана до 15-го декабря.

За самостоятельную работу выставляется оценка Сам в зависимости от сложности выбранной задачи и достигнутого продвижения.

Некоторые темы для проектов

Варианты от Евгения Владимировича:

  • Определить кольцо Z[X1, X2, ...] многочленов над Z c произвольным количеством переменных. Должны поддерживаться методы show, +, -, *, а также операции подстановки одного многочлена в другой (в частности, вычисление значения в целых точках) и дифференцирования по произвольной переменной.
  • Определить понятие формулы первого порядка (в заданной сигнатуре) и реализовать алгоритм приведения таких формул к предваренной нормальной форме.
  • Определить понятие пропозициональной формулы и реализовать проверку таких формул на выполнимость с помощью метода резолюций. Метод применим только к КНФ, поэтому еще нужно реализовать полиномиальный алгоритм построения КНФ, «равновыполнимой» данной формуле.
  • Реализуйте «угадывающую машину» К. Шеннона.
  • Вычислите справедливую стоимость опциона методом "двоичного дерева".
  • Реализуйте игру "Жизнь" на торе с графикой ASCII

Варианты от Паши:

  • DSL для rich text-а (а-ля Markdown, возможно, с поддержкой формул)
  • Библиотека для простых символьных вычислений (с упрощением выражений)
  • Бот в телеграм с помощью servant
  • Model checker для простых моделей и формул (с нуля)
  • Автоматическое дифференцирование, линейная регрессия на его основе (с нуля)
  • Консольный роглайк
  • Интерпретатор Scheme
  • Улучшение интерпретатора лямбда-исчисления

Варианты инициативных проектов от некоторых студентов:

  • Решение задач на Codeforces на Haskell
  • Crafting Interpreters на Haskell
  • Криптографическая библиотека
  • Raft с нуля
  • Консольный мессенджер

Частые Вопросы по проектам

Какой сложности и объёма должен быть проект?

Зависит от вашего уровня. Подбирайте задачу, которую вам самим интересно решать и которую вы успеете доделать (или сделать осмысленный кусок) к дедлайну.

Можно ли брать одну и ту же тему проекта?

Да, можно, главное, чтобы проекты выполнялись самостоятельно. Обмениваться идеями можно, копировать код друг у друга — нет.

Можно ли выбирать тему, не предложенную преподавателями?

Да, можно, темы выше — это примерные ориентиры для вдохновения. Можно взять их, можно придумать что-то своё.

Как аппрувнуть тему?

Связываетесь со мной (Павлом), я оцениваю совместимость уровня студента до начала прохождения курса и сложности проекта и говорю, подходит ли Вам тема или нужно её отрафинировать.

Оценивается ли кодстайл?

Типы всех верхнеуровневых функций должны быть выписаны явно, а пользовательские типы и конструкторы должны иметь понятные, семантические названия. Отступы, именования локальных переменных и т.д. не проверяются.

Нужна ли документация проекта?

Haddock не обязателен, но см. комментарий про типы выше

В какой форме можно сдать код проекта?

В любом формате, который не предполагает нахождение вашего кода в открытом доступе и который желающие потом смогут собрать с помощью cabal build и запустить с помощью cabal run. При этом ограничений на версию GHC нет.

Какой дедлайн сдачи проекта?

С выбором темы желательно определиться до начала сессии, защита будет когда-то во время сессии, возможно, в несколько дней. Код нужно прислать за день (до 23:59) до начала Вашей защиты.

Будут ли дополнительные вопросы на понимание кода проекта?

Только в том случае, если мы начнём сомневаться в авторстве проекта.

За что производится оценивание проекта?

За навык решения не-тривиальной задачи на Haskell. Если вы решили ощутимую часть задачи, одобренной мной (Павлом), то это полный балл. Опять же, оценивание зависит от Вашего начального уровня до прохождения курса.

Как проходит защита?

Скорее всего онлайн. Вы рассказываете, какая у Вас тема, что Вы успели сделать, как устроен код (с высоты птичьего полёта, только основные типы данных, функции и инстансы). Мы можем задать Вам пару вопросов по задаче, возможным расширениям и архитектуре решения. Можно слушать защиты друг друга и задавать свои вопросы, групповые проекты защищаются всей командой сразу.

Полезные библиотеки

  • containers, unordered-containers — стандартные коллекции.
  • monoidal-containers — некоторые стандартные коллекции с в каком-то смысле более правильными инстансами Semigroup и Monoid.
  • lattices — решётки (алгебраическая структура).
  • brick — фреймворк для TUI интерфейсов.
  • servant — генератор API для веб-серверов и клиентов.
  • telegram-bot-simple — немного устаревшая библиотека для ботов в Телеграм.
  • haskeline — фреймворк для REPL интерфейсов.
  • ansi-terminal — для редактирования вывода (полезно для роглайков и Game of Life).
  • megaparsec — фреймворк для написания парсеров.
  • async — асинхронное IO.
  • data-fix, free — типы данных для обобщённой рекурсии.
  • QuickCheck — фреймворк для property-based тестирования.
  • HUnit — фреймворк для юнит-тестов.

Материалы

Группа слушателей курса в ТГ

Материалы Е.В. Дашкова

Записи лекций Е. В. Дашкова в МФТИ (Youtube)

Записи лекций Е. В. Дашкова в МФТИ (Rutube; не все еще сюда переехало)

Базовые ресурсы

Сайт языка

Haskell Tool Stack

Информация про Cabal

Hoogle

Hackage

Стандартная библиотека языка Haskell на Hackage

Книги и статьи

Learn You a Haskell for Great Good

Real World Haskell

Basic Simple Type Theory

Lectures on the Curry-Howard Isomorphism

Purely Functional Data Structures.

Нет в открытом доступе

Programming in Haskell by Graham Hutton

Basic Category Theory for Computer Scientists by Benjamin C. Pierce

Оценки и пересдача

Итоговая оценка получается так:

Итог = ОКРУГЛ (min(10, 0.15 * Сам + 0.23 * КР + 0.27 * ДЗ + 0.5 * Экз)).

Округление производится по правилам арифметики. Автоматы по курсу не предусмотрены.

Первая и вторая пересдачи экзамена проводятся в случае получения итоговой неудовлетворительной оценки аналогично собственно экзамену. Действуют правила ПОПАТКУС.

Источник — «http://wiki.cs.hse.ru/index.php?title=Функциональное_программирование_2025/2026&oldid=93873»