СОШН I1 КОВ Д . В . Функциональное программирование на F# Электронное издание Профобразование Саратов.2 01 7 УДК БЕК 004.438F# 32.9 .1 CS4 Сошн и ков д. В. С54 фуtltщl1о1I алыlеe 1Ij)QI1)аммирование П рофобраэование, 20 17. - F# . - Эл. шд. Саратов: 191 с . _4488_0131_0 Автор этой КJII1П1 имеет БШ'ат ый ОIlЫТ [JренодаваllИЯ курсов ФункЦlЮ lIалЫЮI'О Щ)Qграммирования l!а базе F# в ведущих россиiiских УШlllерси те тах, в то же время , будуч и теХНОЛОГИ'lеСКI1М еваШ'ели стом Маii.крософт, 011 умеет ДОХОД 'II1IIО объясн и т ь КШlцеВЦI1И функционалыlO('О Щ)QI1)аммирова IIIIЯ даже 1!а'lIшающему раэраБОТ 'II1КУ П О, не щm 6еJ"ая к сложным I IOНЯТИ-ЯМ лям6да-llсчислеНI1Я. КНl1га содержит MHOJ"O Jtолезных IJримеРОIJ ис[юль.'юваНI1Я F# дЛЯ реше IIИЯ нраХТИ'Iе<:КИХ зада'l: Достуна к рел яционным и л и слабоструктур ирован IIЫМ XML- даIШЫМ , ИСl lOЛЬЭОlJание F# дЛЯ веб-разработки и веб-маЙШ1lн'а, IJI13уализация данных 11 ностроение AI1aJl)aMM, IlаllИсаНl1е сервисов для 06лачных ВЫ 'II1 CJlений и асинхронных IIРИJlожеllИЙ для Windows Р!lOпе 7. Ис пользуя фрагмент ы кода , раСС\1Отренные в КНИI'е, 'lI1 тател и МШ'ут немедл ен- 110 [JРИСТУ IIИТЬ к решению СВО I1Х нрактических задач Ila F# . БЕК 32.9 . 1 Все Ilр:ша защищены. Любая ч асть ~той книги Ile может быть воснроизведе lШ в какой бы ru IIИ было форме и какими бы то ни быдо средствами без IПlсьмеllJЮГО ра.lрешеНIIЯ ола дельцевавruРСК И )(llрав М атери ал , юложенн ый о данн ой книге, MHoro KpaTl1O lI[)()верен. Но ПОСКОЛЬКУ uеРОЯ"ГIIОСТЬ теЮlИчесКIIХ ошиоок все равно существует, И.'lДатеЛЫТDО Ile может гарантировать абсолlOТНУЮ точность и ПР:ШИЛЫlOсть приводнмых сведеннЙ. В СВЯ.1И с ЭЛI.ll и.'\дательспlO Ile Ileceт ответ ствеlllюстизаоо.l.IЮЖllыеО1ПиБКИ,связаНll ыеСИСПОЛh.l0МIIIle.lI КIIИГИ. _5_4488·0131·0 © Сошников Д. В., 2011 © Оформлеllllе. Профобразоваиие, 2017 Предисловие Дона Сайма ... ..... ..... ..... ..... ............................................... 6 Предисловие автора ... ..... ..... ..... ..... ..... ..... ................................................ 8 о. Введение ........... ..... ..... ..... ..... ..... ..... ..... ..... ..... .......................................... 10 0 .1. Зачем изучать Функциональное программирование ... ..... ..... ..... ..... ..... ..... . 1О 0 .2. О чем и для кого эта книга .. ..... ..... ..... ..... ..... ..... ...... ..... ..... ..... ..... ..... ..... ..... . 12 0 .3 . Как установить и начать ис п ользовать F# .... ..... ...... ..... ..... ..... ..... ..... ..... ..... . 13 1. ОСНОВЫ функционального программирования ...... ..... ..... .. 17 1.1. Применение ФУНКЦИЙ У$. П рисваивание ... ..... ..... ...... ..... ..... ....... .... ..... ..... .. 17 1.2. Упорядоченные кортежи , списки и вывод тип ов ... ..... ..... ..... ....... .... ..... ..... .. 19 1.3 . Функциональные типы и описание ФУНКЦИЙ ... ...... ..... ..... ..... ....... .... ..... ..... .. 20 1.4. Каррирование .. ...... ..... ..... ..... ..... ..... ..... ..... ..... ....... .... ..... ..... ....... .... ..... ..... .. 22 1.5. УСЛОВНЫЙ о п ератор и опционалЬНЫЙ тип ... ..... ...... ..... ..... ..... ....... .... ..... ..... .. 23 1.6 . Типы данных, размеченное объединение и сопоставление с образцом ... .. 25 1.7 . Рекурсия , Функции-параметры и цикл for .. ..... ...... ..... ..... ..... ....... .... ..... ..... .. 27 1.8 . Конструкции », 1> ..... ..... ..... ..... ..... ..... ..... ..... ....... ......................... ..... ..... .. 28 1.9 . Пример - построение множества Мандельброта ... ... ..... ..... ....... .... ..... ..... .. 29 1.10. Интероперабельность с .NET ... ..... ..... ..... ..... ...... ..... ..... ..... ....... .... ..... ..... .. 31 2 . Рекурсивные структуры данных ......... ..... ..... ..... ..... ..... ..... ..... ..... 34 2. 1. Списки и конструкторы списков ... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 34 2.2 . Сопоставление с образцом ..... ..... ..... ..... ...... ..... ..... ..... ...... ..... ..... ..... ..... ..... 35 2.3 . П ростейшие Функции обработки списков .... ..... ...... ..... ..... ..... ..... ..... ..... ..... 36 2.4 . Функции высших порядков ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 37 2.4.1. Отображение ... ..... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 37 2.4.2. Фильтрация ..... ..... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 39 2.4.3. Свертка ... .... ..... ..... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 41 2.4.4. Другие функции высших п орядков .. ..... ....... .... ..... ..... ..... ..... ..... ..... ..... 43 2.5 . Генераторы списков .. .... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 44 2.6 . Хвостовая рекурсия .. .... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 45 2.7 . Сложностные особенности работ ы со списками ..... ..... ..... ..... ..... ..... ..... ..... 47 2.8 . Массивы .. ..... ...... ..... ..... ..... ..... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 50 2.9 . Многомерные массивы и матрицы .... ..... ...... ....... .... ..... ..... ..... ..... ..... ..... ..... 52 2.9.1. С п иски списков , или непрямоугольные массивы (Jagged АггаУ$) .. ..... 52 2.9.2. Многомерные массивы .NEТ ..... ..... ...... ....... .... ..... ..... ..... ..... ..... ..... ..... 53 2.9.3. С п ециализированные типы для матриц и векторов ... ..... ..... ..... ..... ..... 54 2.9.4. Разреженные матрицы .... ..... ..... ..... ...... ..... ...... ..... ..... ..... ..... ..... ..... ..... 55 . .. ...111 СодеРЖQн и е 2.9.5. Использование сторонних математических пакетов ...... ..... ..... ..... ..... 56 2.10. Деревья общего вида .. ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 56 2.11. Двоичные деревья ...... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 59 2.11 . 1. Определение ...... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 59 2.11 .2. ОБХОДДВQичныхдеревьев .. ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 59 2.11 .3. Деревья поиска ... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 60 2.11.4. Деревья выражений и абст рактные синтаксические деревья (AST) .. 62 2.12. Другие структуры данных ...... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 63 2.12. 1. Множества (Se1) .. ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 63 2.12.2. Отображения (Мар) .. ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 63 2.12.3. Хеш-таблицы .. ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... 64 З . Типовые приемы функци о нального 3 .1. Замыкания ... ....... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 66 3 .2. Динамическое связывание и mutabIe-перемеННblе ...... ..... ..... ..... ..... ..... ..... 67 3 .3 . Генераторы и ссыло чные переменные ref .... ..... ....... ..... ..... ..... ..... ..... ..... ..... 68 3.4. Ленивые последов ательности (seq) .. ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 71 3.4.1. Построение частотно го словаря текстового файла ... ..... ..... ..... ..... ..... 73 3.4.2. Вычисление числа 11 методом Монте-Карло .... ..... ..... ..... ..... ..... ..... ..... 74 3 .5. Ленивые и энергичные вычисления ... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... 76 програм м ирования . ••••• ••••••••••• ••••• ••••• ••••• ••••• ••••• ••••••• ••••••• •••• ••••• ••••• •••••• ••••• 81 4 . Императивные и объектно-ориентированные возможности F# ...... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... . 84 4.1. Мультипарадигмальность языка F# .. ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... . 84 4.2. Элементы императивного про г раммирования на F# ... ..... ..... ..... ..... ..... ..... . 85 4 .2.1. Ис п ользование изменяемых переменных и ссылок .. ..... ..... ..... ..... ..... . 85 4 .2.2. Цикл с предусловием ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 86 4 .2.3 . Условный оператор ... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 87 4 .2.4. Null-значения .. ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 87 4 .2.5. Обработка исключительных ситуаций ..... ....... ..... ..... ..... ..... ..... ..... ..... . 87 4.3. Объектно-ориентированное программирование на F# .... ..... ..... ..... ..... ..... . 89 4 .3 .1. За п иси ....... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 89 4 .3 .2. Моделирование объектной ориентированности через записи и замыкания ........ ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 90 4 .3 .3 . Методы ...... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 91 4 .3.4. Интерфейсы ... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 92 4 .3 .5. Создание классов с помощью делегирования ..... ..... ..... ..... ..... ..... ..... . 93 4 .3 .6 . Создание иерархии классов .... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... . 94 4 .3 .7 . Расширение Функциональности имеющихся классов ... ..... ..... ..... ..... . 97 4 .3 .8 . Модули ...... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... . 97 5 . Метапрограммирование ... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... 99 5.1. Языково-ориентирова нное программирование . 5.2. Активные шаблоны ... ..... ...... ..... ..... ..... ..... ...... ..... ....... ...... ..... ..... ..... ....... .... ... . 5.3 . Квотирование ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... .... 103 Содержо н не 111••• •• 5.4. Ко н струирование выражений, частичное применение Фун кции и суперкомпиляция ...... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ... 106 5.5. Монады ...... ....... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ... 107 5.5.1. Монада ввода-вывода .. ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ... 108 5.5.2. Монадические свойства ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ... 11 О 5.5.3. Монада недетерминированных вычислений .... ..... ..... ..... ..... ..... ..... ... 111 5.6 . Монадические выражения .... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ... 112 6 . Параллельное и асинхронное программирование ........ 115 6. 1. Асинхронные выражения и параллельное программирование ...... ..... ..... .. 115 6.2. Асинхронное про г раммирование ... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 116 6.3. Асинхронно-параллельная обработка файлов ..... ..... ..... ..... ..... ..... ..... ..... .. 118 6.4. Агентный паперн проектирования ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 120 6.5. Использование MPI .... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 122 7 . Решение типовых задач ...... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... ..127 7.1. Вычислительные задачи ...... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 127 7 .1.1. Вычисления с высокой точностью .... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 127 7 .1.2. Комплексный тип .... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 128 7 .1.3. Единицы измерения ... ....... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... .. 128 7 .1.4. Использование сторонних мате мат ических пакетов ... ..... ..... ..... ..... .. 129 7.2. Доступ кданным ... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 131 7 .2.1. Доступ к реляционным базам данных (SQL Server) ...... ..... ..... ..... ..... .. 131 7 .2.2. Доступ к слабоструктурированным данным XML .... ..... ..... ..... ..... ..... .. 136 7 .2.3. Работа с данными в Мiсrоsоft Excel .. ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 139 7.3. Веб-программирование .. ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 143 7 .3.1. Доступ к веб-сервисам, ХМL-данным , RSS- п отокам ... ..... ..... ..... ..... .. 144 7 .3.2. Доступ к текстовому содержимому веб-страниц .... ..... ..... ..... ..... ..... .. 144 7 .3.3. Использование веб-ориентированных про граммных интерфейсов на примере Bing Search API ... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 147 7 .3.4. Реализация веб-приложений на F# дЛЯ ASP.N EТWeb Forms .. ..... ..... .. 148 7 .3.5. Реализация веб-приложений на F# дЛЯ ASP. NEТ MVC ...... ..... ..... ..... .. 150 7 .3.6 . Реализация веб-приложений на F# при помощи системы WebSharper ....... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 152 7 .3.7 . Облачное п рограммирование на F# дЛЯ Windows Azure .... ..... ..... ..... .. 156 7.4. Визуализация и работа с графикой ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 158 7.4.1. Двухмерная графика на основе Windows Forms АРI ..... ..... ..... ..... ..... .. 159 7.4.2. Использование злемента Chart ... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 160 7.4.3. 3D-визуализация с помощью Directx и /ил и XNA ..... ..... ..... ..... ..... ..... .. 164 7.5. Анализ текстов и построение компиляторов ... ..... ..... ..... ..... ..... ..... ..... ..... .. 171 7.4.1. Реализация синтаксического разбора методом рекурсивного спуска ... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... .. 171 7.4.2. Использование fslex и fsyacc .. ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 174 7.5. Соэдание F#-приложений для Silverlight и Windows Phone 7 ..... ..... ..... ..... .. 179 Вместо заключения ...... ..... ..... ..... ..... ..... ....... ..... ..... ..... ..... ..... ..... ..... ..... .. 185 Рекомендуемая литература .. ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... 190 -------_... ПреДНСlIовне Дона Сайма F# ЯIJJlяется достаТО'IILО молодым ЯЗЫКОМ t!JюграММИРОlJашtЯ - его разработку мы IJаЧ.IСТВОМ с СаЙМОНО;>.1 П еii ТОIIОМ -ДЖOlIСОМ, ОДIШМ и з создателе ii языка H askell, ныне ра60таЮЩI1М n Мiсгоsоft Researcll 11 КемБР l1дже, п осле 1'01'0 как блаl'Oдаря в нервую o'lepeAb уси л и ям Дона CaiiMa F# был 1IКЛЮ'lен n соста 1l VisHa] StHdio 2010, я CT