Джоэла Каасинена (Nitor) и Джона Лонга (Университет Хельсинки)

1 Лекция 1: …И все начинается

1.1 О курсе

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

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

Работа над упражнениями предполагает знание того, как использовать командную строку и основы использования системы контроля версий Git.

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

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

1.2 Полезные материалы

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

• Страницы курса
• Курс канал в Telegram
• Курс репозиторий на GitHub содержит упражнения и этот материал
• Дополнительные ресурсы
  • A Gentle Introduction to Haskell — более старый и короткий учебник, но его все же стоит прочитать
  • Изучите Haskell во благо! – хорошее бесплатное введение в Haskell
  • The Haskell School of Expression – немного старое, но все еще актуальное введение в функциональное программирование
  • Программирование на Haskell: основы — электронная книга по Haskell стоимостью 59 долларов, медленная и длинная
  • IRC-канал #haskell на libera.chat — хорошее место для новичков.

1.3 Haskell

Haskell — это

Функциональный (Functional) — основными строительными блоками программ являются функции. Функции могут возвращать функции и принимать функции в качестве аргументов. Кроме того, единственная конструкция цикла в Haskell — это рекурсия.

Чистый (Pure) — Функции Haskell являются чистыми, то есть не имеют побочных эффектов. Побочные эффекты означают такие вещи, как чтение файла, распечатка текста или изменение глобальных переменных. Все входные данные функции должны находиться в ее аргументах, а все выходные данные функции — в ее возвращаемом значении. Это звучит ограничивающе, но упрощает рассуждения о программах и позволяет компилятору провести дополнительную оптимизацию.

Ленивый (Lazy) — значения оцениваются только тогда, когда они необходимы. Это дает возможность работать с бесконечными структурами данных, а также делает чистые программы более эффективными.

Строго типизированный (strongly typed) — каждое значение и выражение Haskell имеет тип. Компилятор проверяет типы во время компиляции и гарантирует отсутствие ошибок типов во время выполнения. Это означает отсутствие ошибок AttributeErrors (а-ля Python), ClassCastExceptions (а-ля Java) или ошибок сегментации (а-ля C). Система типов Haskell очень мощная и может помочь вам разрабатывать более качественные программы.

С выводом типов (type inferred) — помимо проверки типов компилятор может выводить типы для большинства программ. Это упрощает работу со строго типизированным языком. Действительно, большинство функций Haskell можно написать вообще без типов. Однако программисты по-прежнему могут давать аннотации типов функций и значений, чтобы упростить поиск ошибок типа. Аннотации типов также облегчают чтение программ.

Со сборкой мусора (garbage-collected) — как и большинство современных языков высокого уровня, Haskell имеет автоматическое управление памятью посредством сборки мусора. Это означает, что программисту не нужно беспокоиться о выделении или освобождении памяти, среда выполнения языка обрабатывает все это автоматически.

Компилируемый (compiled) — хотя в этом курсе мы в основном используем Haskell через интерактивную среду GHCi, Haskell является компилируемым языком. Программы на Haskell могут быть скомпилированы в очень эффективные двоичные файлы, а компилятор GHC очень хорош в оптимизации функционального кода в производительный машинный код.

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

См. также: Страница Haskell Wiki по функциональному программированию.

1.3.1 Возможности

Вот демонстрация некоторых интересных возможностей Haskell:

Функции высшего порядка – функции могут принимать функции в качестве аргументов:

map length ["abc","abcdef"]

В результате получается [3,6].

Анонимные функции, также известные как лямбды — вы можете определять одноразовые вспомогательные функции, не присваивая им имени.

filter (\x -> length x > 1) ["abc","d","ef"]

В результате получается ["abc","ef"].

Частичное применение — вы можете определять новые функции, передавая другой функции только некоторые из необходимых ей аргументов. Например, это умножает все элементы в списке на 3:

map (*3) [1,2,3]

Алгебраические типы данных (algebraic data types) – синтаксис для определения типов данных, который может содержать несколько различных случаев:

data Shape = Point | Rectangle Double Double | Circle Double

Теперь тип Shape может иметь значения типа Point, Rectangle 3 6 и Circle 5

Сопоставление с образцом – определение функций на основе случаев, которые соответствуют вашим определениям данных:

area Point = 0
area (Rectangle width height) = width * height
area (Circle radius) = pi * radius * radius

Lists – В отличие от многих языков, Haskell имеет краткий встроенный синтаксис для списков. Списки можно создавать из других списков, используя list Comprehensions. Вот фрагмент, который генерирует имена четной длины из набора параметров для имени и фамилии:

[whole | first <- ["Eva", "Mike"],
         last <- ["Smith", "Wood", "Odd"],
         let whole = first ++ last,
         even (length whole)]

В результате получается ["EvaSmith","EvaOdd","MikeWood"]. Благодаря ленивости Haskell мы можем даже создавать так называемые бесконечные списки:

primes = [ n | n <- [2..] , all (\k -> n `mod` k /= 0) [2..n `div` 2] ]

Первые десять простых чисел можно получить, вычислив

take 10 primes

Результатом будет [2,3,5,7,11,13,17,19,23,29].

Параметризованные типы – вы можете определить типы, которые параметризуются другими типами. Например, [Int] — это список Int, а [Bool] — список логических значений. Вы можете определить типизированные функции, которые работают со всеми типами списков, например reverse имеет тип [a] -> [a], что означает, что он принимает список, содержащий любой тип a, и возвращает список того же типа.

Классы типов – еще одна форма полиморфизма, при которой вы можете дать функции разную реализацию в зависимости от типов аргументов. Например, класс типов Show определяет функцию show, которая может преобразовывать значения различных типов в строки. Класс типов Num определяет арифметические операторы, такие как +, которые работают со всеми типами чисел (Int, Double, Complex, …).

1.3.2 Немного истории

Краткая хронология Haskell:

• 1930-е годы: лямбда-исчисление
• 1950-1970-е годы: Lisp, Pattern Сопоставление, схемы, ML
• 1978 Джон Бэкус: Можно ли программирование освободить от стиля фон Неймана?
• 1987 Было принято решение объединить область чисто функциональных языков
• 1990 Haskell 1.0
• 1991 Haskell 1.1 (let-синтаксис, разделы)
• 1992 Haskell 1.2, GHC
• 1996 Haskell 1.3 (Монады, синтаксис do, улучшения системы типов)
• 1999 Haskell 98
• 2000-е: разработка GHC, множество расширений языка
• 2009 Стандарт Haskell 2010
• 2010-е: разработка GHC, платформа Haskell, стек Haskell

Слово «haskel» на иврите означает мудрость, но название языка программирования Haskell происходит от логика Хаскелла Карри. Название Haskell происходит от древнескандинавских слов áss (бог) и ketill (шлем).

1.3.3 Использование Haskell

Вот несколько примеров программных проектов, написанных на Haskell.

• Darcs распределенная система контроля версий
• Инструмент предотвращения спама Sigma на Facebook
• Реализации Языки программирования PureScript и Elm написаны на Haskell.
• Инструмент Pandoc для преобразования различных форматов документов – он также используется для создания материалов этого курса.
• Сервер PostgREST, который предоставляет HTTP REST API для базы данных PostgreSQL.
• Функциональные консалтинговые компании, такие как Galois и Well-Typed имеет долгую историю разработки критически важных систем для клиентов на Haskell

Дополнительную информацию см. в The Haskell Wiki и этой записи блога!

1.4 Запуск Haskell

Самый простой способ получить Haskell — установить инструмент stack, см. https://haskellstack.org. Упражнения этого курса предназначены для работы со Stack, поэтому вам следует пока использовать его.

Кстати, если вас интересует, что такое Stack и как он связан с другими инструментами Haskell, такими как Cabal и GHC, читайте больше здесь или здесь. Мы вернемся к пакетам Haskell и подробному их использованию во второй части курса.

А сейчас, после установки Stack, просто запустите stack ghci, чтобы получить интерактивную среду Haskell.

Примечание! GHC 8.10.7 содержит ошибку GHCi, которая делает невозможным редактирование строк в системах на базе ARM. В качестве обходного пути используйте TERM=dumb stack ghci. Дополнительную информацию здесь.

1.5 Начнем!

GHCi — интерактивный интерпретатор Haskell. Вот пример сеанса:

$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
Prelude> 1+1
2
Prelude> "asdf"
"asdf"
Prelude> reverse "asdf"
"fdsa"
Prelude> :type "asdf"
"asdf" :: [Char]
Prelude> tail "asdf"
"sdf"
Prelude> :type tail "asdf"
tail "asdf" :: [Char]
Prelude> :type tail
tail :: [a] -> [a]
Prelude> :quit
Leaving GHCi.

Кстати, при первом запуске stack ghci он загрузит GHC и некоторые библиотеки, поэтому не волнуйтесь, если вы увидите какой-то вывод и вам придется подождать некоторое время, прежде чем получить приглашение Prelude>.

Давайте разберемся в этом. Не волнуйтесь, если вы еще чего-то не понимаете, это всего лишь первое знакомство с выражениями и типами.

Prelude> 1+1
2

Prelude> — это приглашение GHCi. Это указывает на то, что мы можем использовать функции из базовой библиотеки Haskell под названием Prelude. Мы вычисляем 1 плюс 1, и результат равен 2.

Prelude> "asdf"
"asdf"

Здесь мы вычисляем строковый литерал, и результатом является та же строка.

Prelude> reverse "asdf"
"fdsa"

Здесь мы вычисляем обратную строку, применяя функцию reverse к значению "asdf".

Prelude> :type "asdf"
"asdf" :: [Char]

Помимо оценки выражений мы также можем запросить их тип с помощью команды :type (сокращенно :t) GHCi. Тип "asdf" представляет собой список символов. Команды, начинающиеся с :, являются частью пользовательского интерфейса GHCi, а не частью языка Haskell.

Prelude> tail "asdf"
"sdf"
Prelude> :t tail "asdf"
tail "asdf" :: [Char]

Функция tail работает со списками и возвращает все элементы списка, кроме первого. Здесь мы видим применение tail к "asdf". Также мы проверяем тип выражения, а оно, как и ожидалось, представляет собой список символов.

Prelude> :t tail
tail :: [a] -> [a]

Наконец, вот тип функции tail. Он принимает список любого типа в качестве аргумента и возвращает список того же типа.

Prelude> :quit
Leaving GHCi.

Вот как вы выходите из GHCi.

1.6 Выражения и типы

Как мы видели в примере GHCi выше, expressions и types являются хлебом с маслом Хаскелл. Фактически, почти все в программе на Haskell является выражением. В частности, здесь нет statements, как в Python, Java или C.

Выражение имеет value и type. Пишем выражение и его тип так: expression :: type. Вот несколько примеров:

1.6.1 Синтаксис выражений

Выражения состоят из функций applied к аргументам. Функции applied (т. е. вызываются) путем размещения аргументов после имени функции – специального синтаксиса для вызова функции не существует.

Круглые скобки можно использовать для group выражений (так же, как в математике и других языках).

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

PS. в Haskell приложение-функция связывает left, то есть f g x y фактически совпадает с (((f g) x) y). Мы вернемся к этой теме позже. А пока вы можете просто думать, что f g x y — это f, примененный к аргументам g, x и y.

1.6.2 Синтаксис типов

Вот несколько основных типов Haskell, с которых можно начать.

Как видите, имена типов в Haskell начинаются с заглавной буквы. Некоторые значения, например True, также начинаются с заглавной буквы, но переменные и функции начинаются со строчной буквы (reverse, not, x). Мы вернемся к значению заглавных букв в Лекции 2.

Типы функций записываются с использованием синтаксиса ->:

• Функция одного аргумента: argumentType -> returnType
• … двух аргументов: argument1Type -> argument2Type -> returnType
• … из трех аргументов: argument1Type -> argument2Type -> argument3Type -> returnType

Выглядит немного странно, правда? Мы еще вернемся к этому.

1.6.3 Примечание относительно вводящих в заблуждение типов

Иногда типы, которые вы видите в GHCi, немного отличаются от тех, которые вы предполагаете. Вот два типичных случая.

Prelude> :t 1+1
1+1 :: Num a => a

На данный момент тип Num a => a следует читать как «любой числовой тип». В Haskell числовые литералы перегружены (overloaded): их можно интерпретировать как значения разных числовых типов, например Int или Double. Позже, в разделе о классах типов, мы вернёмся к точному значению Num a.

Prelude> :t "asdf"
"asdf" :: [Char]

Тип String — это просто псевдоним типа [Char], который означает «список символов». К спискам вернемся на следующей лекции! В любом случае вы можете использовать String и [Char] взаимозаменяемо, но GHCi в основном будет использовать [Char] при описании типов.

1.7 Структура программы на Haskell

Вот простая программа на Haskell, которая выполняет некоторые арифметические действия и печатает некоторые значения.

module Gold where

-- The golden ratio
phi :: Double
phi = (sqrt 5 + 1) / 2

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

f x = polynomial (polynomial x)

main = do
  print (polynomial phi)
  print (f phi)

Если вы поместите это в файл с именем Gold.hs и запустите его (например) с stack runhaskell Gold.hs, вы должны увидеть этот вывод

0.0
-1.0

Давайте пройдемся по файлу.

module Gold where

В каждом исходном файле имеется один Haskell module. Модуль состоит из definitions.

-- The golden ratio

Это комментарий. Комментарии не являются частью самой программы, а являются текстом для читателей программы.

phi :: Double
phi = (sqrt 5 + 1) / 2

Это определение константы phi с сопровождающей аннотацией типа (она же сигнатура типа) phi :: Double. Аннотация указывает, что phi имеет тип Double. Строка со знаком равенства (=) называется уравнением (equation). Слева от = находится определяемое выражение, справа от = — его определение.

Обычно определение (функции или константы) состоит из необязательной аннотации type и одного или нескольких equations

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

Это определение функции polynomial. Он имеет аннотацию типа и уравнение. Обратите внимание, чем уравнение функции отличается от уравнения константы наличием параметра x слева от знака =. Также обратите внимание, что ^ — это оператор степени в Haskell, а не побитовый оператор xor, как во многих других языках.

f x = polynomial (polynomial x)

Это определение функции f. Обратите внимание на отсутствие аннотации типа. Что такое тип f?

main = do
  print (polynomial phi)
  print (f phi)

Это описание того, что происходит при запуске программы. Он использует do-синтаксис и IO-монаду. Мы вернемся к ним во второй части курса.

1.8 Работа с примерами

Когда вы видите пример определения, подобный этому

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

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

Если определение помещается в одну строку, вы можете просто определить его в GHCi:

Prelude> polynomial x = x^2 - x - 1
Prelude> polynomial 3.0
5.0

Для многострочного определения вы можете либо использовать ; для разделения строк, либо использовать специальный синтаксис :{ :} для вставки блока кода в GHCi:

Prelude> :{
Prelude| polynomial :: Double -> Double
Prelude| polynomial x = x^2 - x - 1
Prelude| :}
Prelude> polynomial 3.0
5.0

Наконец, вы можете вставить код в новый или существующий файл .hs, а затем :load в GHCi. Если файл уже загружен, вы также можете использовать :reload.

-- first copy and paste the definition into Example.hs, then run GHCi
Prelude> :load Example.hs
[1 of 1] Compiling Main             ( Example.hs, interpreted )
Ok, one module loaded.
*Main> polynomial 3.0
5.0
-- now you can edit the definition
*Main> :reload
[1 of 1] Compiling Main             ( Example.hs, interpreted )
Ok, one module loaded.
*Main> polynomial 3
3.0

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

1.8.1 Обработка ошибок

Поскольку Haskell является типизированным языком, вы довольно быстро столкнетесь с ошибками типа. Вот пример ошибки во время сеанса GHCi:

Prelude> "string" ++ True

<interactive>:1:13: error:
    • Couldn't match expected type ‘[Char]’ with actual type ‘Bool’
    • In the second argument of ‘(++)’, namely ‘True’
      In the expression: "string" ++ True
      In an equation for ‘it’: it = "string" ++ True

Это наиболее распространенная ошибка типа «Не удалось соответствовать ожидаемому типу». Несмотря на то, что ошибка выглядит длинной и пугающей, она довольно проста, если вы ее просто прочитаете.

• Первая строка сообщения об ошибке <interactive>:1:13: error: сообщает нам, что ошибка произошла в GHCi. Если бы мы загрузили файл, вместо этого мы могли бы получить что-то вроде Sandbox.hs:3:17: error:, где Sandbox.hs — имя файла, 3 — номер строки, а 17 — номер символа в строке.

• Строка • Couldn't match expected type ‘[Char]’ with actual type ‘Bool’ сообщает нам, что непосредственной причиной ошибки является наличие выражения типа Bool, когда GHCi ожидал найти выражение типа [Char] ". Местоположение этой ошибки было указано в первой строке сообщения об ошибке. Обратите внимание, что ожидаемый тип не всегда правильный. Предоставление аннотаций типа вручную может помочь в отладке ошибок ввода.

• Строка • In the second argument of ‘(++)’, namely ‘True’ сообщает, что выражение неправильного типа было вторым аргументом оператора (++). Почему оно заключено в круглые скобки, мы узнаем позже.

  .

• Полное выражение с ошибкой: "string" ++ True. Как упоминалось выше, String — это псевдоним типа [Char], типа списков символов. Первым аргументом ++ был список символов, а поскольку ++ может объединять только два списка одного и того же типа, второй аргумент тоже должен был иметь тип [Char].

• Строка In an equation for ‘it’: it = "string" ++ True говорит, что выражение встречается в определении переменная it, которая является именем переменной по умолчанию, которую GHCi использует для автономных выражений. Если бы у нас была строка x = "string" ++ True в файле или объявление let x = "string" ++ True в GHCi, GHCi вместо этого напечатал бы In an equation for ‘x’: x = "string" ++ True.

Существуют и другие типы ошибок.

Prelude> True + 1

<interactive>:6:1: error:
    • No instance for (Num Bool) arising from a use of ‘+’
    • In the expression: True + 1
      In an equation for ‘it’: it = True + 1

Это тип ошибки, которую вы получаете, когда пытаетесь использовать числовую функцию, например +, для чего-то, что не является числом.

Обычно сложнее всего отследить следующую ошибку:

Prelude> True +

<interactive>:10:7: error:
    parse error (possibly incorrect indentation or mismatched brackets)

Есть много способов вызвать ее. Возможно, вы где-то упускаете какие-то символы. Мы вернемся к отступам позже в этой лекции.

1.8.2 Арифметика

В арифметике Haskell есть одна вещь, которая часто сбивает с толку новичков, — это деление.

В Haskell есть две функции деления: оператор / и функция div. Функция div выполняет целочисленное деление:

Prelude> 7 `div` 2
3

Оператор / выполняет обычное деление:

Prelude> 7.0 / 2.0
3.5

Однако вы можете использовать div только для типов целых чисел, таких как Int и Integer, и вы можете использовать только / для десятичных типов, таких как Double. Вот пример того, что произойдет, если вы попытаетесь их смешать:

halve :: Int -> Int
halve x = x / 2

error:
    • No instance for (Fractional Int) arising from a use of ‘/’
    • In the expression: x / 2
      In an equation for ‘halve’: halve x = x / 2

Просто постарайтесь пока иметь это в виду. Мы вернемся к разнице между / и div и к тому, что означают Num и Fractional, когда речь идет о классах типов.

1.9 Как мне что-нибудь сделать?

До сих пор вы видели некоторые арифметические действия, переворачивание строки и т. д. Как писать настоящие программы на Haskell? Многие из обычных программных конструкций, таких как циклы, операторы и присваивание, отсутствуют в Haskell. Далее мы рассмотрим основные строительные блоки программ на Haskell:

• Условные выражения
• Локальные определения
• Сопоставление с образцом
• Рекурсия

1.9.1 Условные выражения

На других языках if — это оператор. У него нет значения, он просто условно выполняет другие операторы.

В Haskell if — это expression. Это имеет ценность. Он выбирает между двумя другими выражениями. Он соответствует оператору ?: в C или Java.

// Java
int price = product.equals("milk") ? 1 : 2;

Условные выражения Python очень близки к условным выражениям Haskell if:

# Python
price = 1 if product == "milk" else 2

Вот как тот же пример выглядит в Haskell:

price = if product == "milk" then 1 else 2

Поскольку if в Haskell возвращает значение, вам всегда нужен else!

1.9.1.1 Функции, возвращающие Bool

Чтобы писать выражения if, вам необходимо знать, как получать значения типа Bool. Самый распространенный способ – сравнения. В Haskell работают обычные операторы ==, <, <=, > и >=. Вы можете выполнять упорядоченные сравнения (<, >) для всех видов чисел, а сравнения на равенство (==) практически для любых чисел:

Prelude> "foo" == "bar"
False
Prelude> 5.0 <= 7.2
True
Prelude> 1 == 1
True

Одной из странностей Haskell является то, что оператор «не равно» пишется /= вместо обычного !=:

Prelude> 2 /= 3
True
Prelude> "bike" /= "bike"
False

Помните, что помимо этих сравнений вы можете получить значения Bool из других значений Bool, используя операторы && («и») и || («или»), а также функцию not.

1.9.1.2 Примеры

checkPassword password = if password == "swordfish"
                         then "You're in."
                         else "ACCESS DENIED!"

absoluteValue n = if n < 0 then -n else n

login user password = if user == "unicorn73"
                      then if password == "f4bulous!"
                           then "unicorn73 logged in"
                           else "wrong password"
                      else "unknown user"

1.9.2 Локальные определения

Haskell имеет два разных способа создания локальных определений: let...in и where.

where добавляет к определению локальные определения:

circleArea :: Double -> Double
circleArea r = pi * rsquare
    where pi = 3.1415926
          rsquare = r * r

let...in — это выражение:

circleArea r = let pi = 3.1415926
                   rsquare = r * r
               in pi * rsquare

Локальные определения также могут быть функциями:

circleArea r = pi * square r
    where pi = 3.1415926
          square x = x * x

circleArea r = let pi = 3.1415926
                   square x = x * x
               in pi * square r

Мы вернемся к различиям между let и where, но в большинстве случаев вы можете использовать то, что захотите.

1.9.3 Несколько слов о неизменяемости

Хотя такие вещи, как pi выше, часто называют variables, я решил называть их определения здесь. Это связано с тем, что в отличие от переменных в Python или Java значения этих определений нельзя изменить. Переменные Haskell — это не ящики, в которые можно помещать новые значения, переменные Haskell присваивают имя значению (точнее, выражению) и все.

Мы еще поговорим о неизменяемости позже в этом курсе, но сейчас достаточно знать, что подобные вещи не работают.

increment x = let x = x+1
              in x

Это просто бесконечный цикл, поскольку он пытается определить новую переменную x со свойством x = x+1. Таким образом, при вычислении x Haskell просто продолжает вычислять 1+1+1+1+... неопределенное время.

compute x = let a = x+1
                a = a*2
            in a

error:
    Conflicting definitions for ‘a’
    Bound at: <interactive>:14:17
              <interactive>:15:17

Здесь мы получаем прямую ошибку, когда пытаемся «обновить» значение a.

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

x :: Int
x = 5

f :: Int -> Int
f x = 2 * x

g :: Int -> Int
g y = x where x = 6

h :: Int -> Int
h x = x where x = 3

Если мы применим их к глобальной константе x, мы увидим эффект затенения:

f 1 ==> 2
g 1 ==> 6
h 1 ==> 3

f x ==> 10
g x ==> 6
h x ==> 3

Лучше всегда выбирать новые имена для локальных переменных, чтобы никогда не происходило затенение. Таким образом, читатель кода поймет, откуда берутся переменные, используемые в выражении. Обратите внимание, что в следующем примере f и g не дублируют аргументы друг друга:

f :: Int -> Int
f x = 2 * x + 1

g :: Int -> Int
g x = x - 2

1.9.4 Сопоставление с образцом

Определение (функции) может состоять из нескольких уравнения. Уравнения сопоставляются по порядку с аргументами, пока не будет найдено подходящее. Это называется соответствие шаблону.

Сопоставление шаблонов в Haskell является очень мощным инструментом, и в этом курсе мы будем продолжать узнавать о нем что-то новое, но вот несколько первых примеров:

greet :: String -> String -> String
greet "Finland" name = "Hei, " ++ name
greet "Italy"   name = "Ciao, " ++ name
greet "England" name = "How do you do, " ++ name
greet _         name = "Hello, " ++ name

Функция greet генерирует приветствие по стране и имени (оба String). У него есть особые случаи для трех стран и случай по умолчанию. Вот как это работает:

Prelude> greet "Finland" "Pekka"
"Hei, Pekka"
Prelude> greet "England" "Bob"
"How do you do, Bob"
Prelude> greet "Italy" "Maria"
"Ciao, Maria"
Prelude> greet "Greenland" "Jan"
"Hello, Jan"

Специальный шаблон _ соответствует чему угодно. Обычно он используется для случаев по умолчанию. Поскольку шаблоны сопоставляются по порядку, важно (usually) ставить регистр _ последним. Рассмотрим:

brokenGreet _         name = "Hello, " ++ name
brokenGreet "Finland" name = "Hei, " ++ name

Теперь для всех входов выбирается первый вариант.

Prelude> brokenGreet "Finland" "Varpu"
"Hello, Varpu"
Prelude> brokenGreet "Sweden" "Ole"
"Hello, Ole"

GHC даже предупреждает вас об этом коде:

<interactive>:1:1: warning: [-Woverlapping-patterns]
    Pattern match is redundant
    In an equation for ‘brokenGreet’: brokenGreet "Finland" name = ...

Ниже приведены еще несколько примеров. Но сначала давайте представим стандартную библиотечную функцию show, которая может превратить (почти!) что угодно в строку:

Prelude> show True
"True"
Prelude> show 3
"3"

Итак, вот пример функции с сопоставлением шаблонов и регистром по умолчанию, которая действительно использует значение (вместо того, чтобы просто игнорировать его с помощью _):

describe :: Integer -> String
describe 0 = "zero"
describe 1 = "one"
describe 2 = "an even prime"
describe n = "the number " ++ show n

Вот как это работает:

Prelude> describe 0
"zero"
Prelude> describe 2
"an even prime"
Prelude> describe 7
"the number 7"

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

login :: String -> String -> String
login "unicorn73" "f4bulous!" = "unicorn73 logged in"
login "unicorn73" _           = "wrong password"
login _           _           = "unknown user"

1.9.5 Рекурсия

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

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

Вот наша первая рекурсивная функция, вычисляющая факториал. В математике факториал — это произведение n первых положительных целых чисел и записывается как n!. Определение факториала:

n! = n * (n-1) * … * 1

Например, 4! = 4*3*2*1 = 24. В любом случае, вот реализация факториала на Haskell:

factorial :: Int -> Int
factorial 1 = 1
factorial n = n * factorial (n-1)

Вот как это работает. Мы используем ==> для обозначения «оценивает».

factorial 3
  ==> 3 * factorial (3-1)
  ==> 3 * factorial 2
  ==> 3 * 2 * factorial 1
  ==> 3 * 2 * 1
  ==> 6

Что происходит, когда вы оцениваете factorial (-1)?

Вот еще один пример:

-- compute the sum 1^2+2^2+3^2+...+n^2
squareSum 0 = 0
squareSum n = n^2 + squareSum (n-1)

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

Последовательность начинается с 1, 1. Чтобы получить следующий элемент последовательности, просуммируйте два предыдущих элемента последовательности.

Первые элементы последовательности Фибоначчи — это 1, 1, 2, 3, 5, 8, 13 и так далее. Вот функция fibonacci, которая вычисляет n -й элемент последовательности Фибоначчи. Обратите внимание, как это отражает математическое определение.

-- Fibonacci numbers, slow version
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci (n-2) + fibonacci (n-1)

Вот как оценивается fibonacci 5:

fibonacci 5
  ==> fibonacci 3                 + fibonacci 4
  ==> (fibonacci 1 + fibonacci 2) + fibonacci 4
  ==> (    1       +       1    ) + fibonacci 4
  ==> (    1       +       1    ) + (fibonacci 2 + fibonacci 3)
  ==> (    1       +       1    ) + (fibonacci 2 + (fibonacci 1 + fibonacci 2))
  ==> (    1       +       1    ) + (    1       + (    1       +     1      ))
  ==> 5

Обратите внимание, что fibonacci 3 оценивается дважды, а fibonacci 2 трижды. Это не самая эффективная реализация функции fibonacci. Мы вернемся к этому в следующей лекции. Другой способ подумать об оценке функции Фибоначчи — представить ее в виде дерева (мы сокращаем fibonacci как fib):

Тогда это дерево точно соответствует выражению (1 + 1) + (1 + (1 + 1)). Рекурсия часто может создавать цепочечные, древовидные, вложенные или цикличные структуры и вычисления. Рекурсия — один из основных методов функционального программирования, поэтому стоит потратить некоторые усилия на ее изучение.

1.10 Теперь все вместе!

Наконец, вот полный модуль Haskell, который использует ifs, сопоставление с образцом, локальные определения и рекурсию. Модуль интересуется Гипотезой Коллатца, известной открытой задачей математики. Он спрашивает:

Достигает ли последовательность Коллатца в конечном итоге 1 для всех начальных значений положительных целых чисел?

Последовательность Коллатца определяется путем принятия любого числа в качестве начального значения, а затем многократного выполнения следующей операции:

• , если число четное, разделить его на два
• , если число нечетное, утроить его и добавить один

Например, последовательность Коллатца для 3: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1… Как видите, как только число достигает 1, оно попадает в цикл.

module Collatz where

-- one step of the Collatz sequence
step :: Integer -> Integer
step x = if even x then down else up
  where down = div x 2
        up = 3*x+1

-- collatz x computes how many steps it takes for the Collatz sequence
-- to reach 1 when starting from x
collatz :: Integer -> Integer
collatz 1 = 0
collatz x = 1 + collatz (step x)

-- longest finds the number with the longest Collatz sequence for initial values
-- between 0 and upperBound
longest :: Integer -> Integer
longest upperBound = longest' 0 0 upperBound

-- helper function for longest
longest' :: Integer -> Integer -> Integer -> Integer
-- end of recursion, return longest length found
longest' number _ 0 = number
-- recursion step: check if n has a longer Collatz sequence than the current known longest
longest' number maxlength n =
  if len > maxlength
  then longest' n len (n-1)
  else longest' number maxlength (n-1)
  where len = collatz n

Мы можем загрузить программу в GHCi и поиграть с ней.

$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
Prelude> :load Collatz.hs
[1 of 1] Compiling Collatz          ( Collatz.hs, interpreted )
Ok, one module loaded.
*Collatz>

Давайте проверим, что наша программа правильно вычисляет начало последовательности Коллатца для 3.

*Collatz> step 3
10
*Collatz> step 10
5
*Collatz> step 5
16

Сколько шагов нужно, чтобы число 3 достигло 1?

*Collatz> collatz 3
7

Какая самая длинная последовательность Коллатца для начального значения меньше 10? А что насчет 100?

*Collatz> longest 10
9
*Collatz> longest 100
97

Длины этих последовательностей Коллатца:

*Collatz> collatz 9
19
*Collatz> collatz 97
118

1.11 Несколько слов об отступах

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

1. Вещи, сгруппированные вместе, начинаются с одного и того же столбца
2. Если выражение (или уравнение) необходимо разбить на несколько строк, увеличьте отступ

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

Несколько примеров по порядку.

Все в порядке:

i x = let y = x+x+x+x+x+x in div y 5

-- let and in are grouped together, an expression is split
j x = let y = x+x+x
              +x+x+x
      in div y 5

-- the definitions of a and b are grouped together
k = a + b
  where a = 1
        b = 1

l = a + b
  where
    a = 1
    b = 1

Это неправильно:

-- indentation not increased even though expression split on many lines
i x = let y = x+x+x+x+x+x
in div y 5

-- indentation not increased even though expression is split
j x = let y = x+x+x
      +x+x+x
      in div y 5

-- grouped things are not aligned
k = a + b
  where a = 1
      b = 1

-- grouped things are not aligned
l = a + b
  where
    a = 1
     b = 1

-- where is part of the equation, so indentation needs to increase
l = a + b
where
  a = 1
  b = 1

Если вы допустите ошибку с отступом, вы обычно получите такую ​​ошибку анализа:

Indent.hs:2:1: error: parse error on input ‘where’

Ошибка включает номер строки, поэтому просто пройдите по этой строке еще раз. Если вам не удается заставить работать отступы, попробуйте сначала поместить все в одну длинную строку.

1.12 Викторина

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

Что такое Haskell-эквивалент выражения C/Java/Python combine(prettify(lawn),construct(house,concrete))?

1. combine prettify (lawn) construct (house concrete)
2. combine (prettify lawn (construct house concrete))
3. combine (prettify lawn) (construct house concrete)

1. send(metric(double(population+increase)))
2. send(metric(double(population)+increase))
3. send(metric,double(population)+increase)
4. send(metric,double(population+increase))

Какое из следующих утверждений верно в Haskell?

1. Каждое значение имеет тип
2. Каждый тип имеет значение
3. Каждый оператор имеет тип

Какое из следующих утверждений верно в Haskell?

1. Невозможно повторно использовать имя переменной
2. Можно переприсвоить значение переменной
3. if всегда требует как then, так и else

Что делает функция f x = if even (x + 1) then x + 1 else f (x - 1)?

1. Сопоставляет каждое значение x с наименьшим четным числом, большим или равным x
2. Сопоставляет каждое значение x с наибольшим четным числом, меньшим или равным x
3. Сопоставляет каждое значение самому себе

Почему 3 * "F00" недействителен на Haskell?

1. 3 и "F00" имеют разные типы
2. Все числовые значения нуждаются в десятичной точке
3. "F00" нужен префикс «0x»

Почему 7.0 `div` 2 дает ошибка?

1. Потому что div не определен для типа Double
2. Потому что div не определен для типа Int
3. Потому что `...` используется для разделения строк.

1.13 Работа над упражнениями

Материалы курса, включая упражнения, доступны в репозитории Git на GitHub по адресу https://github.com/moocfi/haskell-mooc. Если вы не знакомы с Git, см. инструкции GitHub по клонированию репозитория.

После клонирования репозитория haskell-mooc перейдите в каталог exercises. Чтобы загрузить и построить зависимости, необходимые для запуска тестов с упражнениями (например, правильную версию GHC и различные библиотеки), выполните в терминале следующую команду:

$ stack build

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

Примечание! Ниже приведены некоторые исправления распространенных проблем с stack build:

• Если вы получаете ошибку типа While building package zlib-0.6.2.3, вам необходимо установить заголовки библиотеки zlib. Правильная команда для Ubuntu — sudo apt install zlib1g-dev.
• Если вы получаете ошибку типа cannot find -ltinfo, вам необходимо установить заголовки ncurses. Правильная команда для Ubuntu — sudo apt install libncurses-dev. Правильная команда для Fedora — dnf install ncurses-devel.
• Если вы получаете ошибку типа Downloading lts-18.18 build plan ... RedownloadInvalidResponse, ваша версия стека слишком старая. Запустите stack upgrade, чтобы получить более новую версию.

В каталоге exercises в основном находятся файлы двух типов: наборы упражнений с именем SetNX.hs и соответствующая тестовая программа для упражнений с именем SetNXTest.hs. Оба являются исходными файлами Haskell, но при решении упражнений следует редактировать только файл упражнений. Инструкции ко всем отдельным упражнениям включены в файл упражнений в виде комментариев.

Используйте файл тестов, чтобы проверить свои ответы. Например, когда вы решили некоторые упражнения из Set1.hs, выполните следующую команду:

$ stack runhaskell Set1Test.hs

Результаты тестов выглядят примерно так:

===== EXERCISE 1
+++++ Pass
===== EXERCISE 2
+++++ Pass
===== EXERCISE 3
*** Failed! Falsified (after 2 tests and 1 shrink):
quadruple 1
  Expected: 4
  Was: 2

----- Fail
===== EXERCISE 4
+++++ Pass
===== EXERCISE 5
+++++ Pass
===== EXERCISE 6
+++++ Pass
===== EXERCISE 7
+++++ Pass
===== EXERCISE 8
+++++ Pass
===== EXERCISE 9
+++++ Pass
===== EXERCISE 10
+++++ Pass
===== EXERCISE 11
+++++ Pass
===== EXERCISE 12
+++++ Pass
===== EXERCISE 13
+++++ Pass
===== EXERCISE 14
+++++ Pass
===== EXERCISE 15
+++++ Pass
===== EXERCISE 16
+++++ Pass
===== EXERCISE 17
+++++ Pass
===== EXERCISE 18
+++++ Pass
===== EXERCISE 19
+++++ Pass
===== TOTAL
1101111111111111111
18 / 19

В приведенном выше примере я допустил ошибку в упражнении 3.

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

$ stack ghci Set1.hs
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Mooc.Todo        ( Mooc/Todo.hs, interpreted )
[2 of 2] Compiling Set1             ( Set1.hs, interpreted )
Ok, two modules loaded.
*Set1> quadruple 1
2

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

Примечание! Вы можете сдавать комплекс упражнений столько раз, сколько захотите.

Примечание! Если вы не хотите использовать стек или не можете заставить его работать, вы также должны иметь возможность запускать тесты с помощью Cabal следующим образом:

$ cabal v2-build
$ cabal v2-exec runhaskell Set1Test.hs

1.13.1 Эталонные решения

После успешного выполнения всех упражнений набора вы сможете просмотреть решения по моделям на Моя страница статуса. Полезно взглянуть на модельные решения, возможно, они подскажут вам прием, который вы упустили!

1.14 Упражнения

• Set1

2 Лекция 2: Либо умри героем…

• Подробнее о рекурсии
• Защитные выражения (guards)
• Дополнительные типы: списки, Maybe, Either
• Полиморфизм

2.1 Рекурсия и вспомогательные функции

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

Вот пример того, как можно преобразовать цикл (в Java или Python) в рекурсивную вспомогательную функцию в Haskell.

Java:

public String repeatString(int n, String str) {
    String result = "";
    while (n>0) {
        result = result+str;
        n = n-1;
    }
    return result;
}

Python:

def repeatString(n, str):
    result = ""
    while n>0:
        result = result+str
        n = n-1
    return result

Haskell:

repeatString n str = repeatHelper n str ""

repeatHelper n str result = if (n==0)
                            then result
                            else repeatHelper (n-1) str (result++str)

Prelude> repeatString 3 "ABC"
"ABCABCABC"

Вы могли заметить, что реализации Java и Python выглядят немного странно, поскольку в них используются циклы while вместо циклов for. Это потому, что таким образом преобразование в Haskell становится более простым.

Это можно сделать немного проще, используя сопоставление с образцом вместо if:

repeatString n str = repeatHelper n str ""

repeatHelper 0 _   result = result
repeatHelper n str result = repeatHelper (n-1) str (result++str)

Вот еще один пример с большим количеством переменных: эффективное вычисление чисел Фибоначчи.

Java:

public int fibonacci(int n) {
    int a = 0;
    int b = 1;
    while (n>1) {
        int c = a+b;
        a=b;
        b=c;
        n--;
    }
    return b;
}

Python:

def fibonacci(n):
    a = 0
    b = 1
    while n>1:
        c = a+b
        a = b
        b = c
        n = n-1
    return b

Haskell:

-- fibonacci numbers, fast version
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)

Изучите их и обратите внимание, что рекурсия Haskell имеет тот же формат, что и цикл.

Примечание: программы на Haskell часто используют апостроф для обозначения вспомогательных функций и альтернативных версий функций. Таким образом, имя fibonacci' для вспомогательной функции выше. Имена типа foo' обычно читаются как foo prime (как в математике).

Ранее я говорил, что эта версия Фибоначчи более эффективна. Вы понимаете, почему? Ответ в том, что рекурсивных вызовов становится меньше. Выражение fibonacci' _ _ n вызывает fibonacci' _ _ (n-1) один раз, и это означает, что мы можем вычислить fibonacci' _ _ n за n шагов.

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

2.2 Защитные выражения (guards)

Прежде чем мы перейдем к новым типам, давайте рассмотрим еще один фрагмент синтаксиса Haskell.

if then else часто бывает немного громоздким, особенно если у вас несколько случаев. Более простой альтернативой является условное определение или защищенное определение в Haskell. Это немного похоже на сопоставление с образцом: у вас есть несколько уравнений, но вы можете использовать произвольный код, решающий, какое уравнение использовать. Защищенные определения выглядят следующим образом:

f x y z
  | condition1 = something
  | condition2 = other
  | otherwise  = somethingother

Условием может быть любое выражение типа Bool. Выбирается первое условие, которое имеет значение True. Слово otherwise — это просто псевдоним True. Он используется для обозначения регистра по умолчанию.

2.2.1 Примеры

Вот несколько примеров использования средств защиты. Во-первых, у нас есть функция, описывающая данное число. Обратите внимание, насколько важно иметь регистр "Two" перед регистром "Even".

describe :: Int -> String
describe n
  | n==2      = "Two"
  | even n    = "Even"
  | n==3      = "Three"
  | n>100     = "Big!!"
  | otherwise = "The number "++show n

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

factorial n
  | n<0       = -1
  | n==0      = 1
  | otherwise = n * factorial (n-1)

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

guessAge :: String -> Int -> String
guessAge "Griselda" age
    | age < 47 = "Too low!"
    | age > 47 = "Too high!"
    | otherwise = "Correct!"
guessAge "Hansel" age
    | age < 12 = "Too low!"
    | age > 12 = "Too high!"
    | otherwise = "Correct!"
guessAge name age = "Wrong name!"

Prelude> guessAge "Griselda" 30
"Too low!"
Prelude> guessAge "Griselda" 60
"Too high!"
Prelude> guessAge "Griselda" 47
"Correct!"
Prelude> guessAge "Bob" 30
"Wrong name!"
Prelude> guessAge "Hansel" 10
"Too low!"

2.3 Списки

До сих пор мы всегда работали с одиночными значениями, такими как числа или логические значения. Строки содержат несколько символов, но в некотором смысле строка — это всего лишь один фрагмент информации. Чтобы иметь возможность заниматься реальным программированием, нам нужно обрабатывать переменное количество элементов. Для этого нам нужны структуры данных.

Базовая структура данных в Haskell — это список. Списки используются для хранения нескольких значений одного типа (другими словами, списки Haskell однородны). Вот как выглядит литерал списка:

[0,3,4,1+1]

Тип списка записывается как [Element], где Element — тип элементов списка. Вот еще несколько выражений списков и их типы:

[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a]                   -- more about this later
[[1,2],[3,4]] :: [[Int]]    -- a list of lists
[1..7] :: [Int]             -- range syntax, value [1,2,3,4,5,6,7]

Списки в Haskell реализованы как односвязные списки. Мы вернемся к этому позже.

2.3.1 Операции со списками

Стандартная библиотека Haskell включает в себя множество функций, которые работают со списками. Вот некоторые из наиболее важных из них вместе с их типами. Через секунду мы вернемся к тому, что на самом деле означает [a], а пока вы можете себе представить, что это означает «любой список».

head :: [a] -> a            -- returns the first element
last :: [a] -> a            -- returns the last element
tail :: [a] -> [a]          -- returns everything except the first element
init :: [a] -> [a]          -- returns everything except the last element
take :: Int -> [a] -> [a]   -- returns the n first elements
drop :: Int -> [a] -> [a]   -- returns everything except the n first elements
(++) :: [a] -> [a] -> [a]   -- lists are concatenated with the ++ operator
(!!) :: [a] -> Int -> a     -- lists are indexed with the !! operator
reverse :: [a] -> [a]       -- reverse a list
null :: [a] -> Bool         -- is this list empty?
length :: [a] -> Int        -- the length of a list

Примечание: последние две операции (null и length) на самом деле имеют более общие типы, но здесь я делаю вид, что вы можете использовать их только со списками.

Списки можно сравнивать с помощью знакомого оператора ==.

Помните это из нашей первой сессии GHCI?

Prelude> :t "asdf"
"asdf" :: [Char]

Это означает, что String — это просто псевдоним для [Char], что означает, что строка представляет собой список символов. Это означает, что вы можете использовать все операции над строками!

Некоторые операции со списками выполняются из модуля Data.List. Вы можете импортировать модуль в коде или в GHCi с синтаксисом import Data.List. Одним из примеров является функция sort, которая сортирует список:

Prelude> import Data.List
Prelude Data.List> sort [1,0,5,3]
[0,1,3,5]

Обратите внимание, как набор импортированных модулей отображается в командной строке GHCi.

2.3.2 Примеры

Вот несколько примеров работы со списками. В этом случае вместо того, чтобы показывать вам выходные данные GHCi, я просто использую ==>, чтобы показать, чему равно выражение.

Индексирование списка:

[7,10,4,5] !! 2
  ==> 4

Определение функции, которая отбрасывает 3-й и 4-й элементы списка с помощью take и drop:

f xs = take 2 xs ++ drop 4 xs

f [1,2,3,4,5,6]  ==>  [1,2,5,6]
f [1,2,3]        ==>  [1,2]

Вращение списка путем взятия первого элемента и перемещения его в конец:

g xs = tail xs ++ [head xs]

g [1,2,3]      ==>  [2,3,1]
g (g [1,2,3])  ==>  [3,1,2]

Вот пример синтаксиса диапазона:

reverse [1..4] ==> [4,3,2,1]

2.4 Несколько слов о неизменяемости

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

Prelude> list = [1,2,3,4]
Prelude> reverse list
[4,3,2,1]
Prelude> list
[1,2,3,4]
Prelude> drop 2 list
[3,4]
Prelude> list
[1,2,3,4]

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

2.5 Несколько слов о выводе типов и полиморфизме

Так что же означает такой тип, как head :: [a] -> a? Это означает, что для списка, содержащего элементы любого типа a, возвращаемое значение будет того же типа a.

В этом типе a является переменной типа. Имена переменных типа начинаются со строчной буквы, например a, b или thisIsATypeVariable. Такая переменная обозначает пока неизвестный тип, которым может оказаться любой тип. Переменные типа превращаются в конкретные типы, например Bool, в процессе вывода типов, также называемом унификацией (unification).

Давайте посмотрим на несколько примеров. Если мы применим head к списку логических значений, вывод типа сравнит тип аргумента заголовка [a] с типом фактического аргумента [Bool] и сделает вывод, что a должно быть Bool. Это означает, что тип возвращаемого значения head в этом случае также будет Bool.

head :: [a] -> a
head [True,False] :: Bool

Функция tail принимает список и возвращает список того же типа. Если мы применим tail к списку логических значений, возвращаемое значение также будет списком логических значений.

tail :: [a] -> [a]
tail [True,False] :: [Bool]

Если типы не совпадают, мы получаем ошибку типа. Рассмотрим оператор ++, который принимает два списка одного типа, как видно из его типа [a] -> [a] -> [a]. Если мы попытаемся применить ++ к списку логических значений и списку символов, мы получим ошибку. Вот что происходит в GHCi:

Prelude> [True,False] ++ "Moi"

<interactive>:1:16:
    Couldn't match expected type `Bool' against inferred type `Char'
      Expected type: [Bool]
      Inferred type: [Char]
    In the second argument of `(++)', namely `"Moi"'
    In the expression: [True, False] ++ "Moi"

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

f xs ys = [head xs, head ys]
g zs = f "Moi" zs

Мы можем запросить у GHCi их типы, и мы увидим, что вывод типа выявил, что два аргумента f должны иметь один и тот же тип, поскольку их головки помещаются в один и тот же список.

Prelude> :t f
f :: [a] -> [a] -> [a]

Функция g, которая зафиксировала один из аргументов f в строке (т. е. [Char]), получает более узкий тип. Вывод типа решил, что аргумент от zs до g также должен иметь тип [Char], поскольку в противном случае тип f не будет соответствовать вызову f.

Prelude> :t g
g :: [Char] -> [Char]

2.5.1 Примечание: немного терминологии

В таком типе, как [Char], мы называем Char параметром type. Тип, подобный типу списка, которому требуется параметр типа, называется параметризованным типом.

Тот факт, что такую ​​функцию, как head, можно использовать со многими различными типами аргументов, называется полиморфизмом. Функция head называется полиморфной. Существует много форм полиморфизма, и эта форма Haskell, использующая переменные типа, называется параметрический полиморфизм.

2.5.2 Примечание: аннотации типов

Поскольку в Haskell есть вывод типа, вам не нужно давать какие-либо аннотации типов. Однако даже несмотря на то, что аннотации типов не требуются, существует несколько причин для их добавления:

1. Они действуют как документация
2. Они действуют как утверждения, которые проверяет компилятор: помогают обнаружить ошибки
3. Вы можете использовать аннотации типов, чтобы придать функции более узкий тип, чем предполагает Haskell.

Хорошее практическое правило — давать аннотации типов определений верхнего уровня.

2.6 Тип Maybe

Помимо типа списка в Haskell есть и другие параметризованные типы. Давайте рассмотрим очень распространенный и полезный тип: тип Maybe.

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

Вместо этого Haskell предлагает изменить тип возвращаемого значения на Maybe. Это чистое, безопасное и аккуратное решение. У типа Maybe a два конструктора: Nothing и Just. Nothing — константа, а Just принимает параметр. Точнее:

Вы можете думать о Maybe a как о чем-то похожем на [a], за исключением того, что здесь может быть только 0 или 1 элемент, не более. В качестве альтернативы вы можете подумать о том, чтобы Maybe a вводил нулевое значение в тип a. Если вы знакомы с Java, Maybe Integer — это эквивалент Java Optional<Integer> в Haskell.

Вы можете создавать значения Maybe, указав Nothing или Just someOtherValue:

Prelude> :t Nothing
Nothing :: Maybe a
Prelude> Just "a camel"
Just "a camel"
Prelude> :t Just "a camel"
Just "a camel" :: Maybe [Char]   -- the same as Maybe String
Prelude> Just True
Just True
Prelude> :t Just True
Just True :: Maybe Bool

-- given a password, return (Just username) if login succeeds, Nothing otherwise
login :: String -> Maybe String
login "f4bulous!" = Just "unicorn73"
login "swordfish" = Just "megahacker"
login _           = Nothing

Вы используете значение Maybe путем сопоставления его с образцом. Обычно вы определяете шаблоны для случаев Nothing и Just something. Некоторые примеры:

-- Multiply an Int with a Maybe Int. Nothing is treated as no multiplication at all.
perhapsMultiply :: Int -> Maybe Int -> Int
perhapsMultiply i Nothing = i
perhapsMultiply i (Just j) = i*j   -- Note how j denotes the value inside the Just

Prelude> perhapsMultiply 3 Nothing
3
Prelude> perhapsMultiply 3 (Just 2)
6

intOrZero :: Maybe Int -> Int
intOrZero Nothing = 0
intOrZero (Just i) = i

safeHead :: [a] -> Maybe a
safeHead xs = if null xs then Nothing else Just (head xs)

headOrZero :: [Int] -> Int
headOrZero xs = intOrZero (safeHead xs)

headOrZero []  ==> intOrZero (safeHead [])  ==> intOrZero Nothing  ==> 0
headOrZero [1] ==> intOrZero (safeHead [1]) ==> intOrZero (Just 1) ==> 1

2.7 Примечание: конструкторы

Как вы можете видеть выше, мы можем сопоставлять шаблоны конструкторов Maybe: Just и Nothing. Мы вернемся к тому, что означают конструкторы, позже. А пока достаточно отметить, что конструкторы — это специальные значения, начинающиеся с заглавной буквы, по которым можно выполнять сопоставление с образцом.

Другие конструкторы, которые мы уже видели, включают конструкторы Bool – True и False. С конструкторами типа списка мы познакомимся на следующей лекции.

Конструкторы можно использовать так же, как и значения Haskell. Конструкторы, не принимающие аргументов, такие как Nothing и False, являются просто константами. Конструкторы типа Just, принимающие аргумент, ведут себя как функции. У них даже есть типы функций!

Prelude> :t Just
Just :: a -> Maybe a

2.8 Тип Either

Иногда было бы неплохо добавить сообщение об ошибке или что-то еще в Nothing. Вот почему у нас есть тип Either. Тип Either принимает два аргумента типа. Тип Either a b имеет два конструктора: Left и Right. Оба принимают аргумент: Left — аргумент типа a, а Right — аргумент типа b.

Вот простой пример: функция readInt, которая знает только пару чисел и возвращает описательную ошибку для остальных. Обратите внимание на соглашение Haskell об использовании Left для ошибок и Right для успеха.

readInt :: String -> Either String Int
readInt "0" = Right 0
readInt "1" = Right 1
readInt s = Left ("Unsupported string: " ++ s)

Примечание: конструкторы Either называются Left и Right, поскольку они ссылаются на левый и правый аргументы типа Either. Обратите внимание, что в Either a b a является левым аргументом, а b — правым аргументом. Таким образом, Left содержит значение типа a, а также Right типа b. Соглашение об использовании Right для успеха, вероятно, просто потому, что правильно также означает правильно. Никакое оскорбление не предназначено для левшей.

Вот еще один пример: соответствие шаблону Either. Как и в случае с Maybe, для Either существует два шаблона, по одному для каждого конструктора.

iWantAString :: Either Int String -> String
iWantAString (Right str)   = str
iWantAString (Left number) = show number

Как вы помните, списки Haskell могут содержать элементы только одного типа. Вы не можете иметь значение типа [1,"foo",2]. Однако вы можете использовать такой тип, как Either, для представления списков, которые могут содержать два разных типа значений. Например, мы могли бы отслеживать количество людей на лекции с возможностью добавления объяснения, если значение отсутствует:

lectureParticipants :: [Either String Int]
lectureParticipants = [Right 10, Right 13, Left "easter vacation", Right 17, Left "lecturer was sick", Right 3]

2.9 Выражение case

Мы видели сопоставление с образцом в аргументах функции, но есть также способ сопоставления с образцом в выражении. Это выглядит так:

case <value> of <pattern> -> <expression>
                <pattern> -> <expression>

В качестве примера давайте перепишем пример describe из первой лекции, используя case:

describe :: Integer -> String
describe 0 = "zero"
describe 1 = "one"
describe 2 = "an even prime"
describe n = "the number " ++ show n

describe :: Integer -> String
describe n = case n of 0 -> "zero"
                       1 -> "one"
                       2 -> "an even prime"
                       n -> "the number " ++ show n

Более интересный пример — когда значение, по которому мы сопоставляем шаблон, не является аргументом функции. Например:

-- parse country code into country name, returns Nothing if code not recognized
parseCountry :: String -> Maybe String
parseCountry "FI" = Just "Finland"
parseCountry "SE" = Just "Sweden"
parseCountry _ = Nothing

flyTo :: String -> String
flyTo countryCode = case parseCountry countryCode of Just country -> "You're flying to " ++ country
                                                     Nothing -> "You're not flying anywhere"

Prelude> flyTo "FI"
"You're flying to Finland"
Prelude> flyTo "DE"
"You're not flying anywhere"

Мы могли бы написать функцию flyTo, используя вспомогательную функцию для сопоставления с образцом вместо использования выражения регистра:

flyTo :: String -> String
flyTo countryCode = handleResult (parseCountry countryCode)
  where handleResult (Just country) = "You're flying to " ++ country
        handleResult Nothing        = "You're not flying anywhere"

Фактически, выражение регистра всегда можно заменить вспомогательной функцией. Вот еще один пример, написанный обоими способами:

-- given a sentence, decide whether it is a statement, question or exclamation
sentenceType :: String -> String
sentenceType sentence = case last sentence of '.' -> "statement"
                                              '?' -> "question"
                                              '!' -> "exclamation"
                                              _   -> "not a sentence"

-- same function, helper function instead of case-of
sentenceType sentence = classify (last sentence)
  where classify '.' = "statement"
        classify '?' = "question"
        classify '!' = "exclamation"
        classify _   = "not a sentence"

Prelude> sentenceType "This is Haskell."
"statement"
Prelude> sentenceType "This is Haskell!"
"exclamation"

2.9.1 Когда использовать выражения case

Вы можете спросить, какой смысл иметь другой синтаксис сопоставления с образцом. Что ж, выражения case имеют некоторые преимущества перед уравнениями, которые мы обсудим далее.

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

motivate :: String -> String
motivate "Monday"    = "Have a nice week at work!"
motivate "Tuesday"   = "You're one day closer to weekend!"
motivate "Wednesday" = "3 more day(s) until the weekend!"
motivate "Thursday"  = "2 more day(s) until the weekend!"
motivate "Friday"    = "1 more day(s) until the weekend!"
motivate _           = "Relax! You don't need to work today!"

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

motivate :: String -> String
motivate day = case distanceToSunday day of
  6 -> "Have a nice week at work!"
  5 -> "You're one day closer to weekend!"
  n -> if n > 1
       then show (n - 1) ++ " more day(s) until the weekend!"
       else "Relax! You don't need to work today!"

Кстати, есть и третий способ, защитные выражения (guards):

motivate :: String -> String
motivate day
  | n == 6 = "Have a nice week at work!"
  | n == 5 = "You're one day closer to weekend!"
  | n > 1 = show (n - 1) ++ " more day(s) until the weekend!"
  | otherwise = "Relax! You don't need to work today!"
  where n = distanceToSunday day

Скоро мы увидим, как можно определить distanceToSunday с помощью уравнений и выражений case.

Во-вторых, если вспомогательную функцию необходимо использовать во многих шаблонах, уравнения не работают. Например:

area :: String -> Double -> Double
area "square" x = square x
area "circle" x = pi * square x
  where square x = x * x

Это не скомпилируется, поскольку предложение where добавляется только к случаю "circle", поэтому вспомогательная функция square недоступна в случае "square". С другой стороны, мы можем написать

area :: String -> Double -> Double
area shape x = case shape of
  "square" -> square x
  "circle" -> pi * square x
  where square x = x*x

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

distanceToSunday :: String -> Int
distanceToSunday "Monday"    = 6
distanceToSunday "Tuesday"   = 5
distanceToSunday "Wednesday" = 4
distanceToSunday "Thursday"  = 3
distanceToSunday "Friday"    = 2
distanceToSunday "Saturday"  = 1
distanceToSunday "Sunday"    = 0

Использование выражения case приводит к гораздо более краткой реализации:

distanceToSunday :: String -> Int
distanceToSunday d = case d of
  "Monday"    -> 6
  "Tuesday"   -> 5
  "Wednesday" -> 4
  "Thursday"  -> 3
  "Friday"    -> 2
  "Saturday"  -> 1
  "Sunday"    -> 0

Эти три преимущества делают выражение case универсальным инструментом в наборе инструментов Haskeller. Стоит запомнить, как работает case.

(Представление дней недели в виде строк может помочь, но это не идеальное решение. Что произойдет, если мы применим motivate к "monday" (со всеми буквами в нижнем регистре) или "keskiviikko"? В Лекции 5 мы научимся лучше представлять такие вещи, как дни недели.)

2.10 Резюме: сопоставление с образцом

Вещи, которые можно использовать в качестве шаблонов:

• Int и Integer константы, такие как (-1), 0, 1, 2, …
• Bool значения True и False
• Char константы: 'a', 'b'
• String константы: "abc", ""
• Maybe Конструкторы: Nothing, (Just x)
• Either Конструкторы: (Left x), (Right y)
• Специальный шаблон _, который означает «что угодно, мне все равно»
• Комбинации этих шаблонов, например (Just 1)
• О других шаблонах, например списках, мы узнаем в следующих лекциях.

Места, где вы можете использовать шаблоны:

• Определение функции с помощью уравнений:

f :: Bool -> Maybe Int -> Int
f False Nothing  = 1
f False _        = 2
f True  (Just i) = i
f True  Nothing  = 0

• В выражении case of:

case number of 0 -> "zero"
               1 -> "one"
               _ -> "not zero or one"

Единственное, что вам действительно нужно, это сопоставление шаблонов получение значения внутри конструктора Just, Left или Right. Вот еще два примера:

-- getElement (Just i) gets the ith element (counting from zero) of a list, getElement Nothing gets the last element
getElement :: Maybe Int -> [a] -> a
getElement (Just i) xs = xs !! i
getElement Nothing xs = last xs

Prelude> getElement Nothing "hurray!"
'!'
Prelude> getElement (Just 3) [5,6,7,8,9]
8

direction :: Either Int Int -> String
direction (Left i) = "you should go left " ++ show i ++ " meters!"
direction (Right i) = "you should go right " ++ show i ++ " meters!"

Prelude> direction (Left 3)
"you should go left 3 meters!"
Prelude> direction (Right 5)
"you should go right 5 meters!"

Другие варианты использования (которые мы уже видели!) сопоставления с образцом также можно реализовать с помощью оператора ==. Однако такие вещи, как x==Nothing, будут работать не во всех случаях. Мы узнаем почему, когда поговорим о классах типов в лекции 4.

2.11 Викторина

Сколько значений возвращает f x = [x,x]?

1. Ноль
2. Один
3. Два

Почему выражение Nothing 1 вызывает ошибку типа?

1. Потому что Nothing не принимает аргументов
2. Потому что Nothing ничего не возвращает
3. Потому что Nothing является конструктором

Каков тип функции f x y = if x && y then Right x else Left "foo"?

1. Bool -> Bool -> Either Bool String
2. String -> String -> Either String String
3. Bool -> Bool -> Either String Bool

Какая из следующих функций может иметь тип Bool -> Int -> [Bool]

1. f x y = [0, y]
2. f x y = [x, True]
3. f x y = [y, True]

Каков тип этой функции? justBoth a b = [Just a, Just b]

1. a -> b -> [Maybe a, Maybe b]
2. a -> a -> [Just a]
3. a -> b -> [Maybe a]
4. a -> a -> [Maybe a]

2.12 Упражнения

• Set2a
• Set2b

3 Лекция 3: Катаморфизм

• Списки, списки, списки
• Функциональность
• Немного о типах

3.1 Наконец-то функциональное программирование

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

В Haskell функция — это значение, точно так же, как число или список. Функции можно передавать в качестве параметров другим функциям. Вот игрушечный пример. Функция applyTo1 принимает функцию типа Int->Int, применяет ее к числу 1 и возвращает результат.

applyTo1 :: (Int -> Int) -> Int
applyTo1 f = f 1

Давайте определим простую функцию типа Int->Int и посмотрим applyTo1 в действии.

addThree :: Int -> Int
addThree x = x + 3

applyTo1 addThree
  ==> addThree 1
  ==> 1 + 3
  ==> 4

Вернёмся к аннотации типа для applyTo1.

applyTo1 :: (Int -> Int) -> Int

Круглые скобки необходимы, поскольку тип Int -> Int -> Int будет типом функции, принимающей два аргумента Int. Подробнее об этом позже.

Давайте рассмотрим немного более интересный пример. На этот раз мы реализуем полиморфную функцию doTwice. Обратите внимание, как мы можем использовать его с различными типами значений и функций.

doTwice :: (a -> a) -> a -> a
doTwice f x = f (f x)

doTwice addThree 1
  ==> addThree (addThree 1)
  ==> 7
doTwice tail "abcd"
  ==> tail (tail "abcd")
  ==> "cd"

makeCool :: String -> String
makeCool str = "WOW " ++ str ++ "!"

doTwice makeCool "Haskell"
  ==> "WOW WOW Haskell!!"

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

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

Самая известная из функций высшего порядка, обрабатывающих списки, — это map. Он дает вам новый список, применяя данную функцию ко всем элементам списка.

map :: (a -> b) -> [a] -> [b]

map addThree [1,2,3]
  ==> [4,5,6]

Соучастником преступления для map является filter. Вместо преобразования всех элементов списка filter удаляет некоторые элементы списка и сохраняет другие. Другими словами, filter выбирает из списка элементы, соответствующие условию.

filter :: (a -> Bool) -> [a] -> [a]

Вот пример: выбор положительных элементов из списка

positive :: Int -> Bool
positive x = x>0

filter positive [0,1,-1,3,-3]
  ==> [1,3]

Обратите внимание, что обе сигнатуры типов map и filter используют полиморфизм. Они работают со всеми видами списков. Тип map даже использует два параметра типа! Вот несколько примеров вывода типа с использованием map и filter.

onlyPositive xs = filter positive xs
mapBooleans f = map f [False,True]

Prelude> :t onlyPositive
onlyPositive :: [Int] -> [Int]
Prelude> :t mapBooleans
mapBooleans :: (Bool -> b) -> [b]
Prelude> :t mapBooleans not
mapBooleans not :: [Bool]

И еще: помните, конструкторы были просто функциями? Это означает, что вы можете передавать их в качестве аргументов другим функциям!

wrapJust xs = map Just xs

Prelude> :t wrapJust
wrapJust :: [a] -> [Maybe a]
Prelude> wrapJust [1,2,3]
[Just 1,Just 2,Just 3]

3.1.2 Примеры функционального программирования на списках

Сколько «палиндромных чисел» находится между 1 и n?

-- a predicate that checks if a string is a palindrome
palindrome :: String -> Bool
palindrome str = str == reverse str

-- palindromes n takes all numbers from 1 to n, converts them to strings using show, and keeps only palindromes
palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

palindrome "1331" ==> True
palindromes 150 ==>
  ["1","2","3","4","5","6","7","8","9",
   "11","22","33","44","55","66","77","88","99",
   "101","111","121","131","141"]
length (palindromes 9999) ==> 198

Сколько слов в строке начинаются с буквы «а»? При этом используется функция words из модуля Data.List, которая разбивает строку на слова.

countAWords :: String -> Int
countAWords string = length (filter startsWithA (words string))
  where startsWithA s = head s == 'a'

countAWords "does anyone want an apple?"
  ==> 3

Функция tails из Data.List возвращает список всех суффиксов («хвостов») списка. Мы можем использовать tails для многих задач обработки строк. Вот как работает tails:

tails "echo"
  ==> ["echo","cho","ho","o",""]

Вот пример, в котором мы находим, какие символы идут после заданного символа в строке. Прежде всего, мы используем tails, map и take, чтобы получить все подстроки определенной длины:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n string = map shorten (tails string)
  where shorten s = take n s

substringsOfLength 3 "hello"
  ==> ["hel","ell","llo","lo","o",""]

В конце осталось несколько более коротких подстрок (понимаете почему?), но сейчас они подходят для наших целей. Теперь, когда у нас есть substringsOfLength, мы можем реализовать функцию whatFollows c k s, которая находит все вхождения символа c в строке s и выводит буквы k, следующие после этих вхождений.

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = map tail (filter match (substringsOfLength (k+1) string))
  where match sub = take 1 sub == [c]

whatFollows 'a' 2 "abracadabra"
  ==> ["br","ca","da","br",""]

3.2 Частичное применение

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

Начнем с GHCi:

Prelude> add a b = a+b
Prelude> add 1 5
6
Prelude> addThree = add 3
Prelude> addThree 2
5

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

Prelude> map addThree [1,2,3]
[4,5,6]
Prelude> map (add 3) [1,2,3]
[4,5,6]

Здесь мы видим, что нам даже не нужно давать имя функции, возвращаемой add 3. Мы можем просто использовать его везде, где ожидается функция одного аргумента.

Это называется частичное приложение. Все функции в Haskell ведут себя подобным образом. Давайте посмотрим поближе. Вот функция, которая принимает много аргументов.

between :: Integer -> Integer -> Integer -> Bool
between lo high x = x < high && x > lo

Prelude> between 3 7 5
True
Prelude> between 3 6 8
False

Мы можем передать between меньше аргументов и вернуть новые функции, точно так же, как мы видели с add:

Prelude> (between 1 5) 2
True
Prelude> let f = between 1 5 in f 2
True
Prelude> map (between 1 3) [1,2,3]
[False,True,False]

Посмотрите на типы частичного применения between. Они ведут себя аккуратно: аргументы исчезают из типа один за другим по мере добавления значений в выражение.

Prelude> :t between
between :: Integer -> Integer -> Integer -> Bool
Prelude> :t between 1
between 1 :: Integer -> Integer -> Bool
Prelude> :t between 1 2
between 1 2 :: Integer -> Bool
Prelude> :t between 1 2 3
between 1 2 3 :: Bool

На самом деле, когда мы пишем тип типа Integer -> Integer -> Integer -> Bool, это означает Integer -> (Integer -> (Integer -> Bool)). То есть функция с несколькими аргументами — это просто функция, которая возвращает функцию. Аналогично, такое выражение, как between 1 2 3, совпадает с ((between 1) 2) 3, поэтому передача нескольких аргументов в функцию происходит посредством нескольких вызовов с одним аргументом. Такое представление функций с несколькими аргументами называется currying (в честь логика Haskell Curry). Каррирование — это то, что делает возможным частичное применение.

Вот еще один пример использования частичного приложения с map:

map (drop 1) ["Hello","World!"]
  ==> ["ello","orld!"]

Помимо обычных функций, частичное приложение также работает с операторами. С помощью операторов вы можете выбирать, применять ли вам левый или правый аргумент. (Частично применяемые операторы также называются sections или operatorsections). Некоторые примеры:

Prelude> map (*2) [1,2,3]
[2,4,6]
Prelude> map (2*) [1,2,3]
[2,4,6]
Prelude> map (1/) [1,2,3,4,5]
[1.0,0.5,0.3333333333333333,0.25,0.2]

3.3 Префиксная и инфиксная запись

Обычные функции Haskell применяются в префиксной записи (prefix notation): имя функции предшествует аргументам. Операторы, напротив, применяются в инфиксной записи (infix notation) — имя функции помещается между аргументами.

Инфиксный оператор можно преобразовать в префиксную функцию, добавив вокруг него круглые скобки. Например,

(+) 1 2 ==> 1 + 2 ==> 3

Это особенно полезно, когда оператор необходимо передать в качестве аргумента другой функции.

Например, функция zipWith принимает два списка (двоичную функцию) и объединяет их с помощью этой функции. Мы можем использовать zipWith (+) для суммирования двух списков поэлементно:

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith (+) [0,2,5] [1,3,3]
[1,5,8]

Без возможности превратить оператор в функцию нам пришлось бы использовать вспомогательную функцию, такую ​​как add выше.

Обратите внимание, что отсутствие круглых скобок приводит к ошибке типа:

Prelude> zipWith + [0,2,5] [1,3,3]

<interactive>:1:11: error:
    • Couldn't match expected type ‘[Integer]
                                    -> (a -> b -> c) -> [a] -> [b] -> [c]’
                  with actual type ‘[Integer]’
    • The function ‘[0, 2, 5]’ is applied to one argument,
      but its type ‘[Integer]’ has none
      In the second argument of ‘(+)’, namely ‘[0, 2, 5] [1, 3, 3]’
      In the expression: zipWith + [0, 2, 5] [1, 3, 3]
    • Relevant bindings include
        it :: (a -> b -> c) -> [a] -> [b] -> [c]
          (bound at <interactive>:1:1)

Причина этой странной ошибки в том, что GHCi запутался и подумал, что мы каким-то образом пытаемся сложить zipWith и [0,2,5] [1,3,3] вместе. Логично, что он пришел к выводу, что [0,2,5] должен быть функцией, поскольку он применяется к [1,3,3] (помните, что функции связаны более жестко, чем операторы).

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

Еще одна приятная особенность Haskell — это синтаксис применения двоичной функции так, как если бы она была инфиксным оператором, путем окружения ее обратными кавычками (`). Например:

6 `div` 2 ==> div 6 2 ==> 3
(+1) `map` [1,2,3] ==> map (+1) [1,2,3] ==> [2,3,4]

3.4 Лямбды

Последний гаечный ключ, который нам нужен в нашем наборе инструментов функционального программирования, — это λ (лямбда). Лямбда-выражения — это анонимные функции. Рассмотрим ситуацию, когда вам нужна функция только один раз, например, в выражении типа

let big x = x>7 in filter big [1,10,100]

Лямбда-выражение позволяет нам написать это напрямую, без определения имени (big) для вспомогательной функции:

filter (\x -> x>7) [1,10,100]

Вот еще несколько примеров в GHCi:

Prelude> (\x -> x*x) 3
9
Prelude> (\x -> reverse x == x) "ABBA"
True
Prelude> filter (\x -> reverse x == x) ["ABBA","ACDC","otto","lothar","anna"]
["ABBA","otto","anna"]
Prelude> (\x y -> x^2+y^2) 2 3           -- multiple arguments
13

Синтаксис Haskell для лямбда-выражений немного удивляет. Символ обратной косой черты (\) обозначает греческую букву лямбда (λ). Выражение Haskell \x -> x+1 пытается имитировать математическую запись λx. x+1. В других языках используется синтаксис, например x => x+1 (JavaScript) или lambda x: x+1 (Python).

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

Кстати, лямбда-выражения — это довольно мощные конструкции, имеющие собственную глубокую теорию, известную как Лямбда-исчисление. Некоторые даже считают чисто функциональные языки программирования, такие как Haskell, типизированными расширениями лямбда-исчисления с дополнительным синтаксисом.

3.5 Примечание: операторы . и $

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

(.) :: (b -> c) -> (a -> b) -> a -> c

И вот что он делает

(f.g) x ==> f (g x)

Вы можете использовать композицию функций для создания функций из других функций, не упоминая никаких аргументов. Например:

double x = 2*x
quadruple = double . double  -- computes 2*(2*x) == 4*x
f = quadruple . (+1)         -- computes 4*(x+1)
g = (+1) . quadruple         -- computes 4*x+1
third = head . tail . tail   -- fetches the third element of a list

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

doTwice :: (a -> a) -> a -> a
doTwice f = f . f

let ttail = doTwice tail
in ttail [1,2,3,4]
  ==> [3,4]

(doTwice tail) [1,2,3,4] ==> [3,4]

doTwice tail [1,2,3,4] ==> [3,4]

Часто композиция функций не используется при определении новой функции, а вместо этого используется для того, чтобы избежать определения вспомогательной функции. Например, рассмотрим разницу между этими двумя выражениями:

let notEmpty x = not (null x)
in filter notEmpty [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

filter (not . null) [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

Другой оператор, $, более тонкий. Давайте посмотрим на его тип.

($) :: (a -> b) -> a -> b

Он принимает функцию типа a -> b и значение типа a и возвращает значение типа b. Другими словами, это оператор приложения-функции. Выражение f $ x совпадает с выражением f x. Это кажется довольно бесполезным, но это означает, что оператор $ можно использовать для удаления скобок! Эти выражения одинаковы:

head (reverse "abcd")
head $ reverse "abcd"

Это не так уж впечатляет, когда оно используется для устранения одной пары скобок, но вместе . и $ могут устранить многие из них! Например, мы можем переписать

reverse (map head (map reverse (["Haskell","pro"] ++ ["dodo","lyric"])))

как

(reverse . map head . map reverse) (["Haskell","pro"] ++ ["dodo","lyric"])

Затем

reverse . map head . map reverse $ ["Haskell","pro"] ++ ["dodo","lyric"]

Иногда операторы . и $ полезны как самостоятельные функции. Например, список функций можно применить к аргументу, используя карту и раздел $:

map ($"string") [reverse, take 2, drop 2]
  ==> [reverse $ "string", take 2 $ "string", drop 2 $ "string"]
  ==> [reverse "string", take 2 "string", drop 2 "string"]
  ==> ["gnirts", "st", "ring"]

Если это кажется сложным, не волнуйтесь. Вам не нужно использовать . и $ в своем собственном коде, пока вы не освоитесь с ними. Однако вы встретите . и $ при чтении примеров и кода Haskell в Интернете, поэтому полезно о них знать. Эта статья также может помочь.

3.6 Пример: перезапись whatFollows

Теперь давайте перепишем приведенный ранее пример whatFollows, используя только что рассмотренные инструменты. Вот исходная версия:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n string = map shorten (tails string)
  where shorten s = take n s

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = map tail (filter match (substringsOfLength (k+1) string))
  where match sub = take 1 sub == [c]

Для начала избавимся от вспомогательной функции substringsOfLength и переместим весь код в whatFollows:

whatFollows c k string = map tail (filter match (map shorten (tails string)))
  where shorten s = take (k+1) s
        match sub = take 1 sub == [c]

Теперь давайте вместо определения shorten использовать частичное приложение:

whatFollows c k string = map tail (filter match (map (take (k+1)) (tails string)))
  where match sub = take 1 sub == [c]

Давайте используем . и $, чтобы устранить некоторые из этих скобок:

whatFollows c k string = map tail . filter match . map (take (k+1)) $ tails string
  where match sub = take 1 sub == [c]

Мы также можем заменить match лямбдой:

whatFollows c k string = map tail . filter (\sub -> take 1 sub == [c]) . map (take (k+1)) $ tails string

Наконец, нам вообще не нужно упоминать параметр string, поскольку мы можем просто выразить whatFollows как композицию map, filter, map и tails:

whatFollows c k = map tail . filter (\sub -> take 1 sub == [c]) . map (take (k+1)) . tails

Мы можем даже пойти немного дальше, переписав лямбду, используя раздел оператора

    \sub -> take 1 sub == [c]
=== \sub -> (==[c]) (take 1 sub)
=== \sub -> (==[c]) ((take 1) sub)
=== \sub -> ((==[c]) . (take 1)) sub
=== ((==[c]) . (take 1))
=== ((==[c]) . take 1)

Теперь у нас осталось:

whatFollows c k = map tail . filter ((==[c]) . take 1) . map (take (k+1)) . tails

Это несколько крайняя версия функции, но При умеренном использовании показанные здесь методы могут облегчить чтение кода.

3.7 Дополнительные примеры функциональной обработки списков

Вот еще несколько примеров функционального программирования со списками. Начнем с введения пары новых функций списка:

takeWhile :: (a -> Bool) -> [a] -> [a]   -- take elements from a list as long as they satisfy a predicate
dropWhile :: (a -> Bool) -> [a] -> [a]   -- drop elements from a list as long as they satisfy a predicate

takeWhile even [2,4,1,2,3]   ==> [2,4]
dropWhile even [2,4,1,2,3]   ==> [1,2,3]

Также есть функция elem, которую можно использовать для проверки наличия элемента в списке:

elem 3 [1,2,3]   ==> True
elem 4 [1,2,3]   ==> False

Используя их, мы можем реализовать функцию findSubstring, которая находит самую раннюю и самую длинную подстроку в строке, состоящей только из заданных символов.

findSubstring :: String -> String -> String
findSubstring chars = takeWhile (\x -> elem x chars)
                      . dropWhile (\x -> not $ elem x chars)

findSubstring "a" "bbaabaaaab"              ==> "aa"
findSubstring "abcd" "xxxyyyzabaaxxabcd"    ==> "abaa"

Функция zipWith позволяет поэлементно объединять два списка:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith (++) ["John","Mary"] ["Smith","Cooper"]
  ==> ["JohnSmith","MaryCooper"]
zipWith take [4,3] ["Hello","Warden"]
  ==> ["Hell","War"]

Иногда для функций более высокого порядка полезно иметь функцию, которая ничего не делает. Функция id :: a -> a является идентификационной функцией и просто возвращает свой аргумент.

id 3 ==> 3
map id [1,2,3] ==> [1,2,3]

Это кажется немного бесполезным, но вы можете использовать его, например, с filter или dropWhile:

filter id [True,False,True,True]  ==>  [True,True,True]
dropWhile id [True,True,False,True,False]  ==>  [False,True,False]

Еще одна очень простая, но иногда решающая функция — это функция-константа const :: a -> b -> a. Он всегда возвращает свой первый аргумент:

const 3 True ==> 3
const 3 0    ==> 3

При частичном применении его можно использовать, когда вам нужна функция, которая всегда возвращает одно и то же значение:

map (const 5) [1,2,3,4] ==> [5,5,5,5]
filter (const True) [1,2,3,4] ==> [1,2,3,4]

3.8 Списки и рекурсия

Вот новый оператор :

Prelude> 1:[]
[1]
Prelude> 1:[2,3]
[1,2,3]
Prelude> tail (1:[2,3])
[2,3]
Prelude> head (1:[2,3])
1
Prelude> :t (:)
(:) :: a -> [a] -> [a]

Оператор : создает список из головы и хвоста. Другими словами, x : xs — это то же самое, что [x] ++ xs. Зачем нам для этого нужен оператор?

На самом деле : — это конструктор для списков: он возвращает новый узел связанного списка. Другой конструктор списка — [], пустой список. Все списки создаются с использованием : и []. Знакомый синтаксис [x,y,z] на самом деле является более удобным способом записи x:y:z:[] или, более явно, x:(y:(z:[])). Фактически (++) определяется в терминах : и рекурсии в стандартной библиотеке.

Вот изображение того, как [1,2,3] структурировано в памяти:

3.8.1 Построение списка

Используя :, мы можем определить рекурсивные функции, которые создают списки. Например, вот функция, которая создает списки типа [3,2,1]:

descend 0 = []
descend n = n : descend (n-1)

descend 4 ==> [4,3,2,1]

Вот функция, которая создает список, повторяя функцию n раз:

iterate f 0 x = [x]
iterate f n x = x : iterate f (n-1) (f x)

iterate (*2) 4 3 ==> [3,6,12,24,48]

let xs = "terve"
in iterate tail (length xs) xs
  ==> ["terve","erve","rve","ve","e",""]

Вот более сложный пример: разбиение строки на части по заданному символу:

split :: Char -> String -> [String]
split c [] = []
split c xs = start : split c (drop 1 rest)
  where start = takeWhile (/=c) xs
        rest = dropWhile (/=c) xs

split 'x' "fooxxbarxquux"   ==>   ["foo","","bar","quu"]

3.8.2 Сопоставление с образцом для списков

В прошлой лекции говорилось, что конструкторы — это вещи, которые можно сопоставить с образцом. Выше было объявлено, что конструкторами для типа списка являются : и []. Мы можем сложить одно и одно и предположить, что мы можем сопоставить шаблоны : и []. Это верно! Вот как вы можете определить свои собственные версии head и tail, используя сопоставление с образцом:

myhead :: [Int] -> Int
myhead [] = -1
myhead (first:rest) = first

mytail :: [Int] -> [Int]
mytail [] = []
mytail (first:rest) = rest

Вы можете nest шаблоны. То есть вы можете сопоставить по шаблону более одного элемента с начала списка. В этом примере мы используем шаблон (a:b:_), который аналогичен (a:(b:_)):

sumFirstTwo :: [Integer] -> Integer
-- this equation gets used for lists of length at least two
sumFirstTwo (a:b:_) = a+b
-- this equation gets used for all other lists (i.e. lists of length 0 or 1)
sumFirstTwo _       = 0

sumFirstTwo [1]      ==> 0
sumFirstTwo [1,2]    ==> 3
sumFirstTwo [1,2,4]  ==> 3

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

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList (x:[])     = "a list with one element"
describeList (x:y:[])   = "a list with two elements"
describeList (x:y:z:xs) = "a list with at least three elements"

describeList [1,3]        ==> "a list with two elements"
describeList [1,2,3,4,5]  ==> "a list with at least three elements"

Шаблоны списков, оканчивающиеся на :[], можно напечатать как литералы списка. То есть точно так же, как [1,2,3] имеет то же значение, что и 1:2:3:[], шаблон [x,y] совпадает с шаблоном x:y:[]. Давайте перепишем предыдущий пример.

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList [x]        = "a list with exactly one element"
describeList [x,y]      = "a list with exactly two elements"
describeList (x:y:z:xs) = "a list with at least three elements"

Другой способ вложения шаблонов — это сопоставление шаблонов в заголовке и сопоставление шаблонов в списке. Например, эта функция проверяет, начинается ли список с 0:

startsWithZero :: [Integer] -> Bool
startsWithZero (0:xs) = True
startsWithZero (x:xs) = False
startsWithZero []     = False

3.8.3 Использование списка

Используя сопоставление с образцом и рекурсию, мы можем рекурсивно обработать весь список. Вот как можно суммировать все числа в списке:

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

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

myMaximum :: [Int] -> Int
myMaximum [] = 0       -- actually this should be some sort of error...
myMaximum (x:xs) = go x xs
  where go biggest [] = biggest
        go biggest (x:xs) = go (max biggest x) xs

Примечание! , «go» — это просто милое имя для вспомогательной функции. Это не специальный синтаксис.

Часто при работе со списком удобно использовать вложенные шаблоны. Вот пример, который подсчитывает, сколько значений Nothing встречается в списке Maybe:

countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs) = 1 + countNothings xs
countNothings (Just _  : xs) = countNothings xs

countNothings [Nothing,Just 1,Nothing]  ==>  2

3.8.4 Создание и использование списка

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

doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

Он оценивается следующим образом:

doubleList [1,2,3]
=== doubleList (1:(2:(3:[])))
==> 2*1 : doubleList (2:(3:[]))
==> 2*1 : (2*2 : doubleList (3:[]))
==> 2*1 : (2*2 : (2*3 : doubleList []))
==> 2*1 : (2*2 : (2*3 : []))
=== [2*1, 2*2, 2*3]
==> [2,4,6]

Если вы знаете сопоставление с образцом для списков, вы можете легко определить map и filter. На самом деле, давайте просто посмотрим на реализации стандартной библиотеки GHC. Вот карта:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

и вот фильтр:

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

(Примечание! Присвоение имени аргументу _pred — это способ сообщите читателю кода, что этот аргумент не используется. Это также могло быть просто _.)

3.8.5 Хвостовая рекурсия и списки

Когда рекурсивная функция вычисляет новый вызов той же функции с другими аргументами, она вызывается. хвостовая рекурсия. (Говорят, что рекурсивный вызов находится в хвостовой позиции.) Это тип рекурсии, соответствующий императивному циклу. Мы уже видели много примеров функций с хвостовой рекурсией, но еще не сравнивали два способа написания одной и той же функции. Это sumNumbers из ранее в этой лекции:

-- Not tail recursive!
sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

Во втором уравнении функция + находится на верхнем уровне, т. е. в хвостовой позиции. Рекурсивный вызов sumNumbers является аргументом +. Это sumNumbers, написанное с использованием вспомогательной функции хвостовой рекурсии:

-- Tail recursive version
sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
  where go sum [] = sum
        go sum (x:xs) = go (sum+x) xs

Обратите внимание на второе уравнение go: оно имеет рекурсивный вызов go на верхнем уровне, т. е. в хвостовой позиции. + теперь является аргументом go.

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

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

-- Not tail recursive!
doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

-- Tail recursive version
doubleList :: [Int] -> [Int]
doubleList xs = go [] xs
    where go result [] = result
          go result (x:xs) = go (result++[2*x]) xs

Здесь прямой вариант гораздо эффективнее. Оператор (:) работает за постоянное время, тогда как оператору (++) необходимо пройти весь список, что требует линейного времени. Таким образом, прямая версия использует линейное время (O(n)) относительно длины списка, а версия с хвостовой рекурсией — квадратичную (O(n²))!

Может возникнуть соблазн исправить это, используя (:) в версии с хвостовой рекурсией, но тогда список будет генерироваться в обратном порядке. Это можно было бы исправить с помощью приложения reverse, но это сделало бы результирующую функцию довольно сложной.

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

3.9 Что-то забавное: генераторы списков

В Haskell есть list Comprehensions, удобный синтаксис для определения списков, сочетающий в себе возможности map и filter. Возможно, вы уже знакомы со списками Python. Haskell работают примерно так же, но их синтаксис немного отличается.

Отображение:

[2*i | i<-[1,2,3]]
  ==> [2,4,6]

Фильтрация:

[i | i <- [1..7], even i]
  ==> [2,4,6]

В общем, эти две формы эквивалентны:

[f x | x <- lis, p x]
map f (filter p lis)

Понимание списков может сделать еще больше. Вы можете перебирать несколько списков:

[ first ++ " " ++ last | first <- ["John", "Mary"], last <- ["Smith","Cooper"] ]
  ==> ["John Smith","John Cooper","Mary Smith","Mary Cooper"]

Вы можете создавать локальные определения:

[ reversed | word <- ["this","is","a","string"], let reversed = reverse word ]
  ==> ["siht","si","a","gnirts"]

Вы даже можете выполнять сопоставление с образцом при анализе списков!

firstLetters string = [ char | (char:_) <- words string ]

firstLetters "Hello World!"
  ==> "HW"

3.10 Что-то интересное: пользовательские операторы

В Haskell operator — это что-то, построенное из символов !#$%&*+./<=>?@\^|-~. Операторы могут быть определены так же, как функции (обратите внимание на немного другую аннотацию типа):

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

3.11 Что-то полезное: типизированные дыры

Иногда при написании Haskell может быть сложно найти выражения, имеющие правильный тип. К счастью, компилятор может помочь вам здесь! Функция Typed Holes позволяет вам оставлять пробелы в коде, и компилятор сообщит вам, какой тип выражения в пробеле должно быть.

Пробелы могут выглядеть как _ или _name. Их можно спутать с шаблоном «все идет» _, но разница в том, что дыра возникает на правой стороне =, тогда как шаблон «все идет» возникает на левой стороне =.

Начнем с простого примера в GHCi:

Prelude> filter _hole [True,False]

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool
      Or perhaps ‘_hole’ is mis-spelled, or not in scope
    • In the first argument of ‘filter’, namely ‘_hole’
      In the expression: filter _hole [True, False]
      In an equation for ‘it’: it = filter _hole [True, False]
    • Relevant bindings include
        it :: [Bool] (bound at <interactive>:5:1)
      Valid hole fits include
        not :: Bool -> Bool
          (imported from ‘Prelude’
           (and originally defined in ‘ghc-prim-0.6.1:GHC.Classes’))
        id :: forall a. a -> a
          with id @Bool
          (imported from ‘Prelude’ (and originally defined in ‘GHC.Base’))

Важной частью этого сообщения является самая первая строка. Это говорит вам, какой тип Haskell ожидает для дыры.

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool

В остальной части сообщения об ошибке предлагаются некоторые варианты значения _hole, например id и not.

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

keepElements [5,6,7,8] [True,False,True,False] ==> [5,7]

Мы начнем с zip, поскольку мы знаем, что он хорошо объединяет элементы двух списков в пары. Мы добавляем типизированное отверстие _doIt и вызываем его с результатом zip, чтобы увидеть, что нам нужно делать дальше.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = _doIt (zip xs bs)

<interactive>: error:
    • Found hole: _doIt :: [(a, Bool)] -> [a]
    ...

Похоже, это можно сделать с помощью map. Посмотрим, что произойдет:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map _f (zip xs bs)

<interactive>: error:
    • Found hole: _f :: (a, Bool) -> a
    ...
      Valid hole fits include
        fst :: forall a b. (a, b) -> a

Отлично! GHC напомнил нам о функции fst, которая извлекает первое из пары. Мы закончили?

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (zip xs bs)

Prelude> keepElements [5,6,7,8] [True,False,True,False]
[5,6,7,8]

Да, да, мы забыли выполнить фильтрацию. Давайте снова попробуем типизированную дыру:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter _predicate (zip xs bs))

<interactive>: error:
    • Found hole: _predicate :: (a, Bool) -> Bool
    ...
      Valid hole fits include
        snd :: forall a b. (a, b) -> b
        ...
        ... lots of other suggestions

И снова GHC напомнил нам о функции, которая, кажется, делает правильную вещь: просто извлекает второй элемент из кортежа. Теперь наша функция завершена и работает как положено.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter snd (zip xs bs))