imported>Edashkov: /* Листки и код для семинаров */

2022-12-26T21:43:41Z

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

Новая страница

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

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

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

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

Семинарист: Павел Соколов, ТГ: [https://t.me/TurtlePU @TurtlePU].

Учебный ассистент: Олег Мкртчян, ТГ: @unwishfulthinking.

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

[https://docs.google.com/spreadsheets/d/e/2PACX-1vTGKTtVAvjvCheX-dky3tB_W-GQnKunxccajwMziHquQvTDA7pqOGOZUfajFtO20dQhPkx0rurScFju/pubhtml https://docs.google.com/spreadsheets/d/e/2PACX-1vTGKTtVAvjvCheX-dky3tB_W-GQnKunxccajwMziHquQvTDA7pqOGOZUfajFtO20dQhPkx0rurScFju/pubhtml]

== Setting up ==

<ol>
<li>Если вы пользуетесь Windows, установите WSL2, если ещё не.</li>
<li>
Установите [https://www.haskell.org/ghcup/ ghcup] — скачайте [https://downloads.haskell.org/~ghcup/ бинарный файл] сами
либо введите одну любимую команду:
<ul>
<li> '''MacOS''': <pre>brew install ghcup</pre></li>
<li> '''Arch'''-based distros: <pre>yay -S ghcup-hs-bin</pre></li>
<li> '''WSL2''', '''MacOS''' >= 10.13, '''Linux''': <pre>curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh</pre></li>
<li> '''Windows Powershell''' (cringe): Команда доступна по [https://www.haskell.org/ghcup/install/#installation ссылке]</li>
</ul>
</li>
<li>Убедитесь, что путь до места установки <code>ghcup</code> содержится в <code>$PATH</code> — запустите <code>ghcup list</code>.</li>
<li>
Установите '''<code style="background-color:black;color:rgb(0,255,0)">recommended</code>''' версии компилятора, пакетного менеджера и языкового сервера:<pre>
ghcup install ghc recommended
ghcup install cabal recommended
ghcup install hls recommended</pre>
</li>
<li>Убедитесь, что путь <code>~/.ghcup/bin</code> содержится в <code>$PATH</code>. При необходимости добавьте этот путь сами.</li>
<li>
Создайте символические ссылки на установленные версии программ:<pre>
ghcup set ghc recommended
ghcup set cabal recommended
ghcup set hls recommended</pre>
</li>
<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>Опционально — установите [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>

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

* [https://drive.google.com/file/d/1Vm69QFV5XFgDozPM9hGp1teFdwjUdyLU/view?usp=sharing Листок 1]

* [https://drive.google.com/file/d/1xFLVoKjOGxooPTP66noHA0KFxosjFkkL/view?usp=sharing Листок 2]

* [https://github.com/edashkov/hse-fp-22 Лекции и семинары] Е. Дашкова

== Домашние задания ==
Домашние задания выдаются приблизительно раз в две недели; при выдаче каждого задания указывается срок его сдачи. Все задания письменные. Каждая задача оценивается 0, ½ или 1 баллом. Все задания в целом оцениваются числом:

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

{| class="wikitable"
|-
! Набор задач !! colspan="11" | Срок сдачи
|-
| || гр. Дашкова || гр. Соколова
|-
|[https://drive.google.com/file/d/1MBSr_Ryb9Xw7HxYUU1vC6WfMHF_YJh9f/view?usp=sharing ДЗ 1] || 20.09 || 20.09
|-
|[https://drive.google.com/file/d/1IK0SZGj78veayMS6_1BS7lT9HncbNwTY/view?usp=sharing ДЗ 2] || 11.10 || 11.10
|-
|[https://drive.google.com/file/d/1UuZWdkEQsKpS1xDVXK1WqOy1tWP1KlJC/view?usp=sharing ДЗ 3] || 01.11 || 01.11
|-
|[https://drive.google.com/file/d/13XvUC48ga4xjTPbVl1isVI0GIxFT0Y_u/view?usp=share_link ДЗ 4] || 26.11 || 26.11
|-
|[https://drive.google.com/file/d/14On7LzhyaasXiKm619EtKy7lqD_g9SF1/view?usp=share_link ДЗ 5] || 20.12 || 20.12
|}

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

'''Ссылка на классрум''': [https://classroom.google.com/c/OTM4MjAyNzk1MTda?cjc=xbblft6 https://classroom.google.com/c/OTM4MjAyNzk1MTda?cjc=xbblft6]

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

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

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

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

== Индивидуальный проект ==
При желании студенты согласовывают с семинаристом проект для индивидуальной работы. Также допускается работа в группах до трех человек. Проект представляет собой решение достаточно сложной задачи по программированию и предполагает самостоятельное получение недостающих сведений. Проекты должны быть сданы за день до защиты (до 23:59), то есть как минимум до 15 декабря. За проект выставляется (дробная) оценка ПР от 0 до 1 балла.

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

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

* Определить кольцо 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. Если вы решили ощутимую часть задачи, одобренной мной (Павлом), то это полный балл. Опять же, оценивание зависит от Вашего начального уровня до прохождения курса.

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

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

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

== Материалы ==

[https://t.me/+0xll5HN3Y1k0ZDRi Группа слушателей курса в ТГ]

[https://drive.google.com/drive/folders/1Ut4Tv4CkaMhC-8Mqxh4gK5WjaN3LkgUR?usp=sharing Материалы Е.В. Дашкова]

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

[https://www.haskell.org/ Сайт языка]

[https://docs.haskellstack.org/en/stable/README/ Haskell Tool Stack]

[https://www.haskell.org/cabal/ Информация про Cabal]

[https://www.haskell.org/hoogle/ Hoogle]

[https://hackage.haskell.org/ Hackage]

[http://hackage.haskell.org/package/base/ Стандартная библиотека языка Haskell на Hackage]

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

[http://learnyouahaskell.com/ Learn You a Haskell for Great Good]

[http://book.realworldhaskell.org/read/ Real World Haskell]

[https://mathtrielhighschool.files.wordpress.com/2011/08/number-theory.pdf Basic Simple Type Theory]

[https://disi.unitn.it/~bernardi/RSISE11/Papers/curry-howard.pdf Lectures on the Curry-Howard Isomorphism]

[https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf Purely Functional Data Structures.]

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

[https://www.cs.nott.ac.uk/~pszgmh/pih.html Programming in Haskell by Graham Hutton]

[https://mitpress.mit.edu/9780262660716/ Basic Category Theory for Computer Scientists by Benjamin C. Pierce]

== Оценки ==

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

Итог = ОКРУГЛ (2 * ПР + 2 * КР + 3 * ДЗ + 3 * Э).

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

Функциональное программирование 22-23 - История изменений

imported>Edashkov: /* Листки и код для семинаров */