Функциональное программирование на языке Haskell
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Душкин Роман Викторович
Год издания: 2023
Кол-во страниц: 609
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
Дополнительное образование
ISBN: 978-5-89818-623-4
Артикул: 616233.03.99
Доступ онлайн
479 ₽
В корзину
Данная книга является первым в России изданием, рассматривающая функциональное программирование в полном объеме, достаточном для понимания новичку и для использования книги в качестве справочного пособия теми, кто уже использует парадигму функционального программирования в своей практике. Изучение прикладных основ показано на примере языка Haskell, на сегодняшний день являющегося самым мощным и развитым инструментом функционального программирования. Издание можно использовать и в качестве учебника по функциональному программированию, и в качестве самостоятельного учебного пособия по смежным дисциплинам, в первую очередь по комбинаторной логике и λ-исчислению. Также книга будет интересна тем, кто всерьез занимается изучением новых компьютерных технологий, искусственного интеллекта и экспертных систем.
На сайте издательства дмк.рф размещены материалы с транслятором Haskell, а также различными библиотеками к нему, дополнительными утилитами и рабочими примерами программ, рассмотренных в книге.
Функциональное программирование на языке Haskell: Полное руководство
Введение в функциональное программирование
Книга представляет собой всеобъемлющее введение в функциональное программирование, ориентированное на язык Haskell. Она охватывает основы, синтаксис, объектно-ориентированные концепции, монады, теоретические основы (комбинаторная логика и λ-исчисление), трансляторы программ и применение в искусственном интеллекте. Цель книги — предоставить как новичкам, так и опытным программистам инструменты для понимания и практического применения функциональной парадигмы.
Основы функционального программирования
Функциональное программирование (ФП) рассматривается как отдельное направление в информатике, стремящееся придать программам простую математическую интерпретацию. Книга начинается с истории ФП, начиная с императивного программирования и переходя к его основным свойствам: краткость, строгая типизация, модульность, функции как значения, чистота (отсутствие побочных эффектов) и отложенные вычисления. Рассматриваются типовые задачи, решаемые методами ФП, такие как получение остаточной процедуры, построение математического описания функций, определение формальной семантики языка, описание динамических структур данных, автоматическое построение программ по описанию структур данных, доказательство свойств программ и эквивалентная трансформация программ.
Базовые принципы языка Haskell
В главе представлено введение в Haskell, включая синтаксис и основные концепции. Рассматриваются списки как фундаментальная структура данных в ФП, базовые операции для работы со списками, генераторы списков и кортежи. Подробно описываются функции, их определение, соглашения об именовании, использование образцов и клозов, передача параметров, каррирование и частичное применение. Рассматриваются структуры данных и их типы, синонимы типов, полиморфные типы, охраняющие выражения, локальные переменные, накапливающие параметры, а также модули, импорт и экспорт данных, абстрактные типы данных.
Классы и их экземпляры
Глава посвящена сочетанию функционального и объектно-ориентированного программирования в Haskell. Рассматривается параметрический полиморфизм данных, классы как способ абстракции, наследование и реализация. Описываются стандартные классы Haskell (Bounded, Enum, Eq, Floating, Fractional, Functor, Integral, Ix, Monad, Num, Ord, Read, Real, RealFloat, RealFrac, Show) и их использование. Проводится сравнение с другими языками программирования, такими как C++ и Java, для выявления общих и отличительных черт.
Монады: последовательное выполнение действий
Монады рассматриваются как тип-контейнер для реализации императивных действий в ФП. Описываются свойства монадических типов, операции связывания, правила построения монад. Рассматривается монада IO для операций ввода/вывода, включая обработку исключений, работу с файлами и потоками. Описываются стандартные монады Haskell (кроме списков и IO), а также разработка собственных монад и комбинирование монадических вычислений.
Комбинаторная логика и λ-исчисление
Глава посвящена теоретическим основам ФП, включая комбинаторную логику и λ-исчисление. Рассматриваются основы комбинаторной логики, базовые комбинаторы, абстракция функций как вычислительных процессов, λ-исчисление как теоретическая основа ФП, кодирование данных в λ-исчислении, редукция и вычисления в функциональных языках.
Трансляторы программ
В главе рассматривается теория построения трансляторов, включая математическую лингвистику, краткое введение в теорию построения трансляторов, реализацию трансляторов на языке Haskell, библиотеки для создания трансляторов (Parsec, Happy) и частичные вычисления, трансформацию программ и суперкомпиляцию.
ФП и искусственный интеллект
Заключительная глава посвящена применению ФП в искусственном интеллекте. Рассматриваются основные задачи ИИ, нечеткая математика и ФП, логический вывод на знаниях, общение с компьютером на естественном языке и перспективы ФП.
- Полная коллекция по информатике и вычислительной технике
- ДМК Пресс. Информационные системы и технологии
- ДМК Пресс. ИТ-технологии для профессионалов
- Интермедиатор. Информационные системы и технологии (сводная)
- Интермедиатор. ИТ-технологии для профессионалов (сводная)
- Программирование
- Программирование и алгоритмизация
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Функциональное программирование на языке Haskell, 2016, 616233.02.99
Функциональное программирование на языке Haskell, 2008, 616233.01.99
Фрагмент текстового слоя документа размещен для индексирующих роботов
Функциональное программирование на языке Haskell Душкин Р. В. Москва, 2023 2-е издание, электронное
Оглавление Содержание 5 Введение 19 1 Основы функционального программирования 27 1.1 История функционального программирования . . . . . . . . . . . . 28 1.2 Основные свойства функциональных языков . . . . . . . . . . . . . 44 1.3 Типовые задачи, решаемые методами функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 1.4 Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . . 69 1.5 Доказательство свойств функций . . . . . . . . . . . . . . . . . . . . 86 2 Базовые принципы языка Haskell 99 2.1 Списки — основа функциональных языков . . . . . . . . . . . . . . 100 2.2 Функции как описания процессов вычисления . . . . . . . . . . . . 118 2.3 Типизация данных и функций . . . . . . . . . . . . . . . . . . . . . . 131 2.4 Элементы программирования . . . . . . . . . . . . . . . . . . . . . . 142 2.5 Модули и абстрактные типы данных . . . . . . . . . . . . . . . . . . 153 3 Классы и их экземпляры 164 3.1 Параметрический полиморфизм данных . . . . . . . . . . . . . . . . 165 3.2 Классы в языке Haskell как способ абстракции действительности . 170 3.3 Наследование и реализация . . . . . . . . . . . . . . . . . . . . . . . 180 3.4 Стандартные классы языка Haskell . . . . . . . . . . . . . . . . . . . 192 3.5 Сравнение с другими языками программирования . . . . . . . . . . 207
Оглавление 3 4 Монады — последовательное выполнение действий в функциональной парадигме 213 4.1 Монада как тип-контейнер . . . . . . . . . . . . . . . . . . . . . . . . 214 4.2 Последовательное выполнение действий . . . . . . . . . . . . . . . . 222 4.3 Операции ввода/вывода в языке Haskell . . . . . . . . . . . . . . . . 239 4.4 Стандартные монады языка Haskell . . . . . . . . . . . . . . . . . . 252 4.5 Разработка собственных монад . . . . . . . . . . . . . . . . . . . . . 262 5 Комбинаторная логика и λ-исчисление 273 5.1 Основы комбинаторной логики . . . . . . . . . . . . . . . . . . . . . 274 5.2 Абстракция функций как вычислительных процессов . . . . . . . . 288 5.3 λ-исчисление как теоретическая основа функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 5.4 Кодирование данных в λ-исчислении . . . . . . . . . . . . . . . . . . 307 5.5 Редукция и вычисления в функциональных языках . . . . . . . . . 315 6 Трансляторы программ 331 6.1 Математическая лингвистика . . . . . . . . . . . . . . . . . . . . . . 331 6.2 Краткое введение в теорию построения трансляторов . . . . . . . . 346 6.3 Реализация трансляторов на языке Haskell . . . . . . . . . . . . . . 360 6.4 Библиотеки для создания трансляторов . . . . . . . . . . . . . . . . 372 6.5 Частичные вычисления, трансформация программ и суперкомпиляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 7 Функциональное программирование и искусственный интеллект 395 7.1 Основные задачи искусственного интеллекта . . . . . . . . . . . . . 396 7.2 Нечеткая математика и функциональное программирование . . . . 407 7.3 Логический вывод на знаниях . . . . . . . . . . . . . . . . . . . . . . 429 7.4 Общение с компьютером на естественном языке . . . . . . . . . . . 443 7.5 Перспективы функционального программирования . . . . . . . . . 454 Заключение 463 Ответы на задачи для самостоятельного решения 465 Решения задач из главы 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
Оглавление Решения задач из главы 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 Решения задач из главы 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 Решения задач из главы 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 Решения задач из главы 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 Решения задач из главы 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 A Функциональные языки программирования и Интернет-ресурсы по функциональному программированию 496 Функциональные языки программирования . . . . . . . . . . . . . . 496 Русские Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . . . . 502 Иностранные Интернет-ресурсы . . . . . . . . . . . . . . . . . . . . . 503 B Опции различных сред разработки на языке Haskell 506 Интегрированная среда разработки HUGS 98 . . . . . . . . . . . . . 506 Компилятор GHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510 Компилятор NHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 Компилятор компиляторов Happy . . . . . . . . . . . . . . . . . . . . 528 C Описание стандартного модуля Prelude 531 Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531 Описание некоторых операторов языка Haskell . . . . . . . . . . . . 586 D Краткий словарь терминов из области функционального программирования 589 Литература 599 Общая литература по функциональному программированию . . . . 599 Книги, руководства и статьи по языку Haskell . . . . . . . . . . . . 601 Комбинаторная логика и λ-исчисление . . . . . . . . . . . . . . . . . 602 Математическая лингвистика и теория построения трансляторов . 603 Искусственный интеллект . . . . . . . . . . . . . . . . . . . . . . . . 604
Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Краткая биография автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 О пользовании книгой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 Состав и структура представления информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 Контактная информация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1 Основы функционального программирования . . . . . . . . . . . . . . . . . . 27 В этой главе рассматриваются основополагающие принципы функционального программирования как отдельного направления в математической науке и технологии создания программного обеспечения. Приводится история развития функционального программирования, описываются предпосылки его развития. В главе рассматривается больше теоретического материала, нежели практического, поэтому пока изложение ведется без рассмотрения синтаксиса языка Haskell. Однако для приведения примеров используется именно этот язык наряду с математическими формулами. Изложение знаний о языке Haskell начинается с главы 2. 1.1 История функционального программирования . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Краткая история развития теории функционального программирования в мире и в России. Разработка функциональных языков для подтверждения теоретических выкладок. Проблемы, с которыми столкнулись исследователи при разработке функциональных языков программирования. Современное состояние теории функционального программирования. Стандарт Haskell 98 как результат унификации и стандартизации процессов развития функционального программирования. Предпосылки создания функционального программирования ........................ 34 История языка Haskell ..............................................................38
Содержание Заключительные слова ..............................................................42 1.2 Основные свойства функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 Описание основных свойств функциональных языков программирования. Краткость и простота, строгая типизация, модульность, функциональные значения и объекты, чистота и отложенные вычисления. Понимание свойств функциональных языков на примере языка Haskell. Краткость и простота .............................................................44 Строгая типизация ................................................................ 48 Модульность ........................................................................50 Функции — это значения и объекты вычисления ................................... 51 Чистота (отсутствие побочных эффектов и детерминированность) ............. 53 Отложенные (ленивые) вычисления ................................................ 55 1.3 Типовые задачи, решаемые методами ФП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Краткое описание семи типовых задач, которые решаются методами функционального программирования. Получение остаточной процедуры. Построение математического описания функций. Определение формальной семантики языка программирования. Описание динамических структур данных. Автоматическое построение «значительной» части программы по описанию структур данных, которые обрабатываются создаваемой программой. Доказательство наличия некоторого свойства программы. Эквивалентная трансформация программ. Получение остаточной процедуры .................................................. 60 Построение математического описания функций .................................. 62 Определение формальной семантики языка программирования ..................... 64 Описание динамических структур данных ..........................................64 Автоматическое построение функций по описанию структур данных ............. 66 Доказательство наличия некоторого свойства программы .........................67 Эквивалентная трансформация программ .......................................... 68 1.4 Конструирование функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Описание метода конструирования функций, предложенного Ч. Хоаром (синтаксически ориентированное конструирование). Метаязык для конструирования функций. Примеры определения типов и функций для обработки этих типов. Декартово произведение ............................................................ 70 Размеченное объединение ............................................................71
Содержание 7 Примеры определения типов данных ................................................72 1.5 Доказательство свойств функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86 Задача доказательства свойств функций. Описание процесса доказательства свойств функций в зависимости от типа области определения функций. Примеры доказательства свойств функций. Область определения D — линейно-упорядоченное множество .....................88 Множество D определяется как индуктивный класс ...............................89 Рассмотрение некоторых примеров доказательства свойств функций .............91 Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 2 Базовые принципы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99 Глава посвящена введению в основные положения языка Haskell, приводится описание синтаксиса для решения основных задач по созданию отдельных функций и законченных модулей. Рассматриваются базовые объекты «список» и «функция» для изучения в рамках функционального программирования, а также их реализация на языке Haskell. 2.1 Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100 Понятие списка в функциональном программировании. Списки как основная структура для работы с функциональными языками. Базисные операции для работы со списками. Списки и списочные структуры. Программная реализация списков в функциональных языках. Списки в языке Haskell. Генераторы списков и математические последовательности. Бесконечные списки и другие структуры данных. Кортежи. Проекция списков в язык Haskell ...................................................101 Несколько слов о программной реализации .........................................104 Примеры ........................................................................... 106 Определители списков и математические последовательности .................. 110 Кортежи .......................................................................... 117 2.2 Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118 Функция — основной объект изучения функционального программирования. Соглашения по именованию объектов в языке Haskell. Описание и определение функций на языке Haskell. Образцы и клозы. Передача параметров и возвращение значений функциями. Инфиксный способ записи функций. Функция как объект
Содержание для передачи в другие функции. Программа на языке Haskell — функция, описывающая процесс вычисления. Соглашения по именованию ........................................................118 Общий вид определения функции .................................................. 119 Образцы и клозы ................................................................... 119 Вызовы функций ................................................................... 125 Использование λ-исчисления ....................................................... 126 Инфиксный способ записи функций ................................................ 127 Несколько слов о функциях высшего порядка ...................................... 131 2.3 Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131 Структуры и типы данных. Типы функций. Каррированные и некаррированные функции. Язык Haskell и его механизмы для организации каррированных и некаррированных функций. Описание типов функций на языке Haskell. Частичное применение. Ленивые (отложенные) вычисления на языке Haskell. Структуры данных и их типы .................................................... 132 Синонимы типов .................................................................. 136 Типы функций в функциональных языках ..........................................137 Полиморфные типы ................................................................140 2.4 Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142 Охраняющие выражения и конструкции. Локальные переменные для оптимизации кода на функциональном языке и на языке Haskell. Использование накапливающего параметра (аккумулятора) для оптимизации процесса вычислений. Принципы построения определений функций с накапливающим параметром. Головная и хвостовая рекурсии. Охрана ............................................................................. 143 Ветвление алгоритма ............................................................. 145 Локальные переменные .............................................................146 Двумерный синтаксис ............................................................. 149 Накапливающий параметр — аккумулятор ....................................... 150 Принципы построения определений с накапливающим параметром ............... 152 2.5 Списки — основа функциональных языков . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153 Модули как способы структуризации и организации программ на языке Haskell. Импорт и экспорт данных при помощи модулей. Сокрытие данных. Абстрактные типы данных и интерфейсы. Иные аспекты использования модулей.
Содержание 9 Абстрактные типы данных ....................................................... 156 Другие аспекты использования модулей ........................................... 157 Литературный код ................................................................ 158 Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .160 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .161 3 Классы и их экземпляры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Эта глава посвящена рассмотрению симбиоза парадигм функционального и объектно-ориентированного программирования. Большинство современных функциональных языков поддерживают механизмы и методы, разработанные в рамках объектно-ориентированного программирования, в том числе и такие базовые концепты, как «наследование», «инкапсуляция» и «полиморфизм». Не обошел своим вниманием этот аспект и язык Haskell, в котором имеются достаточные средства для программирования в объектно-ориентированном стиле. 3.1 Параметрический полиморфизм данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Понятие класса и его реализации в языке Haskell. Чистый (параметрический) полиморфизм на языке Haskell. Примеры параметрического полиморфизма в императивных и функциональных языках, а также в языке Haskell. 3.2 Классы в языке Haskell как способ абстракции действительности . . . . . 170 Расширенное описание понятия класса в языке Haskell. Класс как высшая абстракция данных и методов для их обработки. Методы класса — шаблоны функций для реализации обработки данных. Минимальное описание методов класса и связь методов. Модель типизации Хиндли-Милнера ...............................................171 Определение классов ............................................................... 176 3.3 Наследование и реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Наследование классов и наследование методов. Экземпляры классов — реализация интерфейсов, предоставляемых реализуемым классом. Реализация методов для обработки данных. Класс — шаблон типа, реализация класса — тип данных. Наследование .......................................................................180 Реализация .........................................................................182 Реализация для существующих типов ............................................ 186 Сорта типов ...................................................................... 187 Дополнительные возможности при определении типов данных ...................189
Содержание 3.4 Стандартные классы языка Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192 Краткое описание всех стандартных классов, разработанных для облегчения программирования на языке Haskell. Дерево наследования стандартных классов. Типичные способы использования стандартных классов языка Haskell. Реализация стандартных классов — типы в языке Haskell. Класс Bounded ......................................................................192 Класс Enum ......................................................................... 193 Класс Eq ........................................................................... 195 Класс Floating .................................................................... 195 Класс Fractional .................................................................. 196 Класс Functor ......................................................................197 Класс Integral .................................................................... 198 Класс Ix ........................................................................... 199 Класс Monad ........................................................................ 199 Класс Num .......................................................................... 200 Класс Ord .......................................................................... 201 Класс Read ......................................................................... 202 Класс Real ......................................................................... 203 Класс RealFloat ................................................................... 203 Класс RealFrac .................................................................... 204 Класс Show ......................................................................... 206 3.5 Сравнение с другими языками программирования . . . . . . . . . . . . . . . . . . . . . 207 Более или менее полное сравнение понятий «класс» и «реализация класса» в языке Haskell с объектно-ориентированными языками программирования (на примере языков C++ и Java, а также некоторых других языков). Глобальные отличия понятия «класс» в функциональных и объектно-ориентированных языках. Окончательные замечания .........................................................209 Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211 4 Монады — последовательное выполнение действий в функциональной парадигме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 Глава описывает такое незаурядное понятие, введенное в функциональной парадигме программирования, как «монада». Монады, основанные на математической теории категорий, позволяют внедрить в функциональный подход опре
Похожие
Доступ онлайн
479 ₽
В корзину