ninjas

7 лет назад

Академия: Введение в функциональное программирование. Конспект второй недели курса

Всем привет. Недавно я начал принимать участие в проекте Академия, и сегодня я рад представить вам подолжение конспекта курса Введение в функциональное программирование от Delft University of Technology

В прошлой части конспекта мы узнали о том, какие преимущества таит в себе функциональное программирование, познакомились с историей функциональных языков и увидели первый пример функции, написанной на Хаскеле. В этой части мы наконец перейдем от теории к практике, познакомимся с функциями, встроенными в стандартную библиотеку Prelude, узнаем об одной из самых фундаменальных структур данных - списках, и методах работы с ними

Подготовка рабочей среды

Для того, чтобы начать программировать на Хаскеле, нам понадобятся две вещи: текстовый редактор и компилятор. Выбор первого я оставляю на ваше усмотрение, а в качестве компилятора мы будем использовать наиболее популярный вариант - Glasgow Haskell Compiler (GHC)

1. Установка

На сайте GHC есть список пакетов, доступных для большинства популярных ОС, доступный по следующему адресу. Ниже я опишу инструкции по установке для самых популярных ОС:

Если вы являетесь счастливым обладателем дебиан-подобной системы, все, что вам нужно сделать - это открыть терминал и ввести sudo apt-get install ghc6 ghc6-prof ghc6-doc
Если вы используете Mac/Windows, то вам необходимо скачать соответсвующий пакет из списка

2. Запуск

Для простоты, мы не будем компилировать на код в исрлняемые файлы, а будем использовать интерактивную среду, входящую в состав GHC и называемую GHCi. Для ее запуска мы просто набираем в терминале ghci и видим следующее:

Отлично! Теперь мы наконец-то можем перейти от слов к делу

Первые шаги

Prelude - это стандартная библиотека, встраиваемая по умолчанию во все создаваемые нами модули, и включающая ряд наиболее часто используемых функций и структур данных. Для того, чтобы познакомиться с базовыми возможностями языка, я предлагаю посмотреть, что мы можем сделать с помощью этой стандартной библиотеки

Для начала рассмотрим простейшую арифметику. Наберите в терминале 2 + 2 и посмотрите, что из этого выйдет

Хм, довольно ожидаемо. Попробуем пример посложнее. Введите в консоль выражение 13 + 5 * 2, а затем (13 + 5) * 2

Как видите, здесь тоже обошлось без сюрпризов: умножение имеет приоритет над сложением, а скобки обладают большим приоритетом, чем остальные арифметические операции

На этом я предлагаю закончить экскурсию в начальную школу и перейти к вещам посерьезней, а именно к операциям над списками. Нужно сказать, что списки - это одна из фундаментальных и наиболее часто используемых в ФП структур данных, поэтому в стандартной библиотеке Prelude содержится множество функций, осуществляющих операции над ними - map, filter, length etc

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

Для того, чтобы создать список, нужно просто перечислить его элементы внутри квадратных скобок:

[1,2,3,4,5]

Итак, давайте введем в терминал let xs = [1,2,3,4,5,6,7,8,9,10] и посмотрим, что мы можем сделать с этим списком с помощью Prelude

head/tail: каждый список можно условно разделить на две части: начальный элемент и остаток. Как несложно догадаться, head возвращает первый элемент, tail - остаток. Подобную операцию можно провернуть и с концом списка: функция last возвращает последний элемет, init - то, что до него
!!: эта функция возращает элемент списка с заданным индексом. Например, xs !! 3 вернет четвертый элемент списка, то есть 4 (нумерация элементов в списке начинается с нуля)
take: эта встроенная функция принимает список и возвращает список из указанного количества элементов с начала исходного списка: take 3 xs вернет [1,2,3]
drop: функция, обратная take. Она принимает список и возвращает его элементы, за исключением указанного числа элементов с начала: drop 5 xs вернет [6,7,8,9,10]
length: название говорит само за себя
product: возвращает произведение всех элементов списка. Как несложно догадаться, функция работает только со списками, состоящими из чисел
++: сложение списков
reverse: возвращает список в обратном порядке

Здесь нужно сделать небольшое, но важное отступление. Дело в том, что несмотря на внешнее сходство, списки в Хаскеле - это совсем не то же самое, что и массивы в знакомых всем языках, вроде С. Главное отличие заключается в том, что функции, вроде !! требуют перебора всего списка, пока не будет найден элемент с нужным индексом. Поэтому выполнение подобных операций занимает не константное, а линейное время. На первый взгляд эта особенность выглядит серьезным упущением разработчиков языка, но на деле в этом нет ничего страшного. Почему? Дело в том, что приемы ФП предполагают, что большую часть времени вы будете пользоваться более общими операциями, вроде map (преобразующей все элементы списка в соответствии с заданны правилом) или zip, в то время как обращение к конкретному элементу по индексу считается дурной практикой

Вызов функций

Следующий момент, который стоит обсудить - это синтаксис вызова фунций. В отличие от большинства языков, в Хаскеле аргументы не заключаются в скобки, а отделяются пробелами. Таким образом, если мы создадим функцию f, принимающую аргументы a b, ее вызов будет выглядеть так: f 1 2, а не f(1, 2). Зачем это сделано? Разработчики Хаскеля очень заботятся об упрощении синтаксиса, а так как определение и вызов функций - это две наиболее часто испоьзуемые операции в Хаскеле, их попытались упростить до предела

Отметим, что вызов функции имеет самый высокий приоритет, поэтому запись f 1 + 2 означает "вызови функцию f с аргументом 1 и добавь к результату 2", а не "вызови функцию f с аргументом (1+2)"

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

Еще одна особенность, которую нужно упомянуть - это так называемая инфиксная нотация. Как вы могли заметить, некоторые функции из стандартной библиотеки вызываются несколько необычным способом: например, !! вызывается не как !! 3 xs (обычная, префиксная способ записи), а как xs !! 3. Такой способ записи и называется инфиксная нотация. Ее можно использовать не только для встроенных, но и для созданных самостоятельно функций. Для иллюстрации возьмем пример из Haskell Wiki:

> let concatPrint x y = putStrLn $ (++) x y

> "a" `concatPrint` "b"

> ab

Такая форма эквивалентна concatPrint "a" "b". По своей сути, это лишь синтаксический сахар, не дающий никаких новых возможностей, но бывают случаи, когда им стоит воспользоваться в целях удобства

Пишем первую функцию

Теперь, после того как мы немного разобрались со встроенными функциями, пришло время написать свою собственную функцию и посмотреть, каким образом файлы со скриптами загружаются в GHCi

В качестве примера мы нашишем собственную реализацию встроенной функции product. Для этого откроем текстовый редактор, создадим файл first-step.hs и запишем в него следующую функцию:

customProduct [] = 0

customProduct xs = foldl (*) 1 xs

После этого мы открываем терминал с GHCi и пишем:

:load first-step.hs

После чего видим вывод:

*Main>

Отлично. Теперь мы можем протестировать нашу функцию. Для этого пишем customProduct [1,2,3,4,5,6] и видим результат 720. После этого вводим product [1,2,3,4,5,6] - результат тот же самый. Великолепно! Похоже, написание стандартных функций - это не такая уж сложная задача (особенно, если под рукой есть другие стандартные функции...)

Теперь вернемся к коду нашей функции. Что мы здесь видим? В первой строке мы определяем, что делать с пустым списком. Мне кажется логичным, что в результате перемножения элементов пустого списка должен получиться 0. После этого мы переходим к непустому списку. Задача, которая перед нами стоит, заключается в том, чтобы превратить множество элементов в один. В программировании такие задачи возникают довольно часто, поэтому давно существует специальный прием для их решения, называемый свертка (fold). Суть его в том, чтобы взять все элементы списка и скомбинировать их определенным способом в один элемент

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

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

Что в этой неделе показалось самым важным

Несмотря на то, что эта неделя, подобно первой, является вводной, из нее мы подчерпнули немало полезного познакомились с некоторыми встроенным в GHC функциями, узнали некоторые особенности синтаксиса Хаскеля, написали нашу первую функцию (пусть и довольно примитивную) и увидели, как удобно можно организовать работу, имея рекурсивные структуры данных . И, что еще более важно, на этой неделе появилась возможность познакомиться вживую с процессом написания программ на Хаскеле

Анонс следующей части

В конспекте третьей недели мы с вами перейдем к более серьезным вещам и рассмотрим тему, являющуюся альфой и омегой Хаскеля: типы данных и классы. Тема эта очень интересна, так что подписывайтесь на мой блог, чтобы не пропустить обновление

На этом у меня все, до новых встреч!