Лямбда функции в haskell
Добавил пользователь Евгений Кузнецов Обновлено: 20.09.2024
В этой главе мы узнаем о лямбда-исчислении. Лямбда-исчисление описывает понятие алгоритма. Ещё до появления компьютеров в 30-е годы двадцатого века математиков интересовал вопрос о возможности создания алгоритма, который мог бы на основе заданных аксиом дать ответ о том верно или нет некоторое логическое высказывание. Например у нас есть базовые утверждения и логические связки такие как “и”, “или”, “для любого из”, “существует один из”, с помощью которых мы можем строить из базовых высказываний составные. Некоторые из них окажутся ложными, а другие истинными. Нам интересно узнать какие. Но для решения этой задачи прежде всего необходимо было понять а что же такое алгоритм?
Ответ на этот вопрос дали Алонсо Чёрч (Alonso Church) и Алан Тьюринг (Alan Turing). Чёрч разработал лямбда-исчисление, а Тьюринг теорию машин Тьюринга. Оказалось, что задача автоматического определения истинности формул в общем случае не имеет решения.
В основе лямбда-исчисление лежит понятие функции. Мы можем составлять сложные функции из простейших, а также подставлять в функции аргументы, которые могут быть как константами так и другими функциями. Как только мы составили выражение мы можем передать его вычислителю. Он подставляет аргументы в функции и возвращает такое выражение, в котором невозможно далее проводить подстановки аргументов. Этот процесс проведения подстановок считается вычислением алгоритма.
В рамках теории машин Тьюринга алгоритм описывается по-другому. Машина Тьюринга имеет внутреннее состояние, Состояние содержит некоторое значение, которое изменяется по ходу работы машины. Машина живёт не сама по себе, она читает ленту символов. Лента символов – это большая цепочка букв. На каждую букву машина реагирует серией действий. Она может изменить значение состояния, обновить букву в ленте или перейти к следующему или предыдущему символу. Есть состояния, которые обозначают конец работы, они называются терминальными. Как только машина дойдёт до терминального состояния мы считаем, что вычисление алгоритма закончилось. После этого мы можем считать результат из состояний машины.
Функциональные языки программирования основаны на лямбда-исчислении. Поэтому мы будем говорить именно об этом описании алгоритма.
Лямбда исчисление без типов
Составление термов
Можно считать, что лямбда исчисление это такой маленький язык программирования. В нём есть множество символов, которые считаются переменными, они что-то обозначают и неделимы. В лямбда-исчислении программный код называется термом. Для написания программного кода у нас есть всего три правила:
Переменные $x$ , $y$ , $z$ … являются термами.
Если $M$ и $N$ – термы, то $(MN)$ – терм.
Если $x$ – переменная, а $M$ – терм, то $(\lambda x .M)$ – терм
В формальном описании добавляют ещё одно правило, оно говорит о том, что других термов нет. Первое правило, говорит о том, что у нас есть алфавит символов, который что-то обозначает, эти символы являются базовыми строительными блоками программы. Второе и третье правила говорят о том как из базовых элементов получаются составные. Второе правило – это правило применения функции к аргументу. В нём $M$ обозначает функцию, а $N$ обозначает аргумент. Все функции являются функциями одного аргумента, но они могут принимать и возвращать функции. Поэтому применение трёх аргументов к функции $Fun$ будет выглядеть так:
$$(((Fun\ Arg1)\ Arg2)\ Arg3)$$
Третье правило говорит о том как создавать функции. Специальный символ лямбда ( $\lambda$ ) в выражении $(\lambda x .M)$ говорит о том, что мы собираемся определить функцию с аргументом $x$ и телом функции $M$ . С такими функциями мы уже сталкивались. Это безымянные функции. Приведём несколько примеров функций. Начнём с самого простого, определим тождественную функцию:
Функция принимает аргумент $x$ и тут же возвращает его в теле. Теперь посмотрим на константную функцию:
$$(\lambda x .(\lambda y .x))$$
Константная функция является функцией двух аргументов, поэтому наш терм принимает переменную $x$ и возвращает другой терм функцию $(\lambda y .x)$ . Эта функция принимает $y$ , а возвращает x . В Haskell мы бы написали это так:
Точка сменилась на стрелку, а лямбда потеряла одну ножку. Теперь определим композицию. Композиция принимает две функции одного аргумента и направляет выход второй функции на вход первой:
$$(\lambda f .(\lambda g .(\lambda x .(f(gx)))))$$
Переменные $f$ и $g$ – это функции, которые участвуют в композиции, а $x$ это вход результирующей функции. Уже в таком простом выражении у нас пять скобок на конце. Давайте введём несколько соглашений, которые облегчат написание термов:
В этой главе мы встретимся с условными конструкциями, выглянем в терминал, а также узнаем, почему из Haskell-функций не возвращаются (впрочем, последнее — не более чем игра слов).
Выглянем во внешний мир
Мы начинаем писать настоящий код. А для этого нам понадобится окно во внешний мир. Откроем модуль app/Main.hs , найдём функцию main и напишем в ней следующее:
Стандартная функция putStrLn выводит строку на консоль. А если говорить строже, функция putStrLn применяется к значению типа String и делает так, чтобы мы увидели это значение в нашем терминале.
Да, я уже слышу вопрос внимательного читателя. Как же так, спросите вы, разве мы не говорили о чистых функциях в прошлой главе, неспособных взаимодействовать с внешним миром? Придётся признаться: функция putStrLn относится к особым функциям, которые могут-таки вылезти во внешний мир. Но об этом в следующих главах. Это прелюбопытнейшая тема, поверьте мне!
И ещё нам следует познакомиться с Haskell-комментариями, они нам понадобятся:
Символы скрывают многострочный комментарий, а символ -- начинает комментарий однострочный.
На всякий случай напоминаю команду сборки, запускаемую из корня проекта:
После сборки запускаем:
Выбор и выход
Выбирать внутри функции приходится очень часто. Существует несколько способов задания условной конструкции. Вот базовый вариант:
где CONDITION — логическое выражение, дающее ложь или истину, EXPR1 — выражение, используемое в случае True , EXPR2 — выражение, используемое в случае False . Пример:
при запуске увидим это:
тогда увидим это:
Круглые скобки включают выражение типа String по схеме:
То есть функция putStrLn видит не применение функции checkLocalhost к строке, а просто выражение типа String . Если бы мы опустили скобки и написали так:
произошла бы ошибка компиляции, и это вполне ожидаемо: функция putStrLn применяется к одному аргументу, а тут их получается два:
Не знаю как вы, а я не очень люблю круглые скобки, при всём уважении к Lisp-программистам. К счастью, в Haskell существует способ уменьшить число скобок. Об этом способе — в одной из последующих глав.
Так что же с возвращением из функции? Вспомним о равенстве в определении:
То, что слева от знака равенства, равно тому, что справа. А раз так, эти два кода эквивалентны:
Мы просто заменили применение функции checkLocalhost её внутренним выражением, подставив вместо аргумента ip конкретную строку 173.194.22.100 . В итоге, в зависимости от истинности или ложности проверок на равенство, эта условная конструкция будет также заменена одним из двух выражений. В этом и заключается идея: возвращаемое функцией значение — это её последнее, итоговое выражение. То есть если выражение:
даст нам результат True , то мы переходим к выражению из логической ветви then . Если же оно даст нам False — мы переходим к выражению из логической ветви else . Это даёт нам право утверждать, что условная конструкция вида:
может быть заменена на первое нередуцируемое выражение, строку It's a localhost! , а условную конструкцию вида:
можно спокойно заменить вторым нередуцируемым выражением, строкой No, it's not a localhost. . Поэтому код:
есть ни что иное, как:
Каким бы сложным ни было логическое ветвление внутри функции checkLocalhost , в конечном итоге оно вернёт/вычислит какое-то одно итоговое выражение. Именно поэтому из функции в Haskell нельзя выйти в произвольном месте, как это принято в императивных языках, ведь она не является набором инструкций, она — выражение, состоящее из других выражений. Вот почему функции в Haskell так просто компоновать друг с другом, и позже мы встретим множество таких примеров.
Для любопытных
Внимательный читатель несомненно заметил необычное объявление главной функции нашего проекта, функции main :
Если IO — это тип, то что такое () ? И почему указан лишь один тип? Что такое IO () : аргумент функции main , или же то, что она вычисляет? Сожалею, но пока я вынужден сохранить это в секрете. Когда мы поближе познакомимся со Вторым Китом Haskell, я непременно расскажу про этот странный IO () .
Пришло время познакомиться с важной концепцией — лямбда-функцией. Именно с неё всё и началось. Приготовьтесь: в этой главе нас ждут новые открытия.
Истоки
Обратный слэш в начале — признак ЛФ. Сравните с математической формой записи:
Похоже, не правда ли? Воспринимайте обратный слэш в определении ЛФ как спинку буквы λ .
ЛФ представляет собой простейший вид функции, эдакая функция, раздетая догола. У неё забрали не только объявление, но и имя, оставив лишь необходимый минимум в виде имён аргументов и внутреннего выражения. Алонзо Чёрч понял: чтобы применить функцию, вовсе необязательно её именовать. И если у обычной функции сначала идёт объявление/определение, а затем (где-то) применение с использованием имени, то у ЛФ всё куда проще: мы её определяем и тут же применяем, на месте. Вот так:
Помните функцию square ? Вот это её лямбда-аналог:
Строение
Строение лямбда-абстракции предельно простое:
Соответственно, если ЛФ применяется к двум аргументам — пишем так:
И когда мы применяем такую функцию:
то просто подставляем 10 на место x , а 4 — на место y , и получаем выражение 10 * 4 :
В общем, всё как с обычной функцией, даже проще.
Мы можем ввести промежуточное значение для лямбда-абстракции:
Теперь мы можем применять mul так же, как если бы это была сама лямбда-абстракция:
И здесь мы приблизились к одному важному открытию.
Тип функции
Мы знаем, что у всех данных в Haskell-программе обязательно есть какой-то тип, внимательно проверяемый на этапе компиляции. Вопрос: какой тип у выражения mul из предыдущего примера?
Ответ прост: тип mul такой же, как и у этой лямбда-абстракции. Из этого мы делаем важный вывод: ЛФ имеет тип, как и обычные данные. Но поскольку ЛФ является частным случаем функции — значит и у обыкновенной функции тоже есть тип!
В нефункциональных языках между функциями и данными проведена чёткая граница: вот это функции, а вон то — данные. Однако в Haskell между данными и функциями разницы нет, ведь и то и другое покоится на одной и той же Черепахе. Вот тип функции mul :
Погодите, скажете вы, но ведь это же объявление функции! Совершенно верно: объявление функции — это и есть указание её типа. Помните, когда мы впервые познакомились с функцией, я уточнил, что её объявление разделено двойным двоеточием? Так вот это двойное двоеточие и представляет собой указание типа:
Точно так же мы можем указать тип любых других данных:
Но вы спросите, можем ли мы не указывать тип функции явно? Можем:
Это наша старая знакомая, функция square . Когда она будет применена к значению типа Int , тип аргумента будет выведен автоматически как Int .
И раз функция характеризуется типом так же, как и прочие данные, мы делаем ещё одно важное открытие: функциями можно оперировать как данными. Например, можно создать список функций:
Выражение functions — это список из двух функций. Два лямбда-выражения порождают эти две функции, но до момента применения они ничего не делают, они безжизненны и бесполезны. Но когда мы применяем функцию head к этому списку, мы получаем первый элемент списка, то есть первую функцию. И получив, тут же применяем эту функцию к строке "Hi" :
Это равносильно коду:
При запуске программы мы получим:
Кстати, а каков тип списка functions ? Его тип таков: [String -> String] . То есть список функций с одним аргументом типа String , возвращающих значение типа String .
Локальные функции
Раз уж между ЛФ и простыми функциями фактически нет различий, а функции есть частный случай данных, мы можем создавать функции локально для других функций:
Это — две функции, которые мы определили прямо в where -секции, поэтому они существуют только для основного выражения функции validComEmail . С простыми функциями так поступают очень часто: где она нужна, там её и определяют. Мы могли бы написать и более явно:
Впрочем, указывать тип столь простых функций, как правило, необязательно.
Вот как этот код выглядит с лямбда-абстракциями:
Теперь выражения containsAtSign и endsWithCom приравнены к ЛФ от одного аргумента. В этом случае мы не указываем тип этих выражений. Впрочем, если очень хочется, можно и указать:
Лямбда-абстракция взята в скобки, чтобы указание типа относилось к функции в целом, а не только к аргументу e :
Для типа функции тоже можно ввести псевдоним:
Впрочем, на практике указание типа для лямбда-абстракций встречается исключительно редко, ибо незачем.
Отныне, познакомившись с ЛФ, мы будем использовать их периодически.
И напоследок, вопрос. Помните тип функции mul ?
Что это за буква a ? Во-первых, мы не встречали такой тип ранее, а во-вторых, разве имя типа в Haskell не обязано начинаться с большой буквы? Обязано. А всё дело в том, что буква a в данном случае — это не совсем имя типа. А вот что это такое, мы узнаем в одной из ближайших глав.
Для любопытных
А почему, собственно, лямбда? Почему Чёрч выбрал именно эту греческую букву? По одной из версий, произошло это чисто случайно.
А наборщик, увидев такой символ, использовал заглавную греческую букву Λ :
ФВП, или Функции Высшего Порядка (англ. HOF, Higher Order Functions) — важная концепция в Haskell, с которой, однако, мы уже знакомы. Как мы узнали из предыдущих глав, функциями можно оперировать как значениями. Так вот функции, оперирующие другими функциями как аргументами и/или как результирующим выражением, носят название функций высшего порядка.
Так, оператор композиции функций является ФВП, потому что он, во-первых, принимает функции в качестве аргументов, а во-вторых, возвращает другую функцию (в виде ЛФ) как результат своего применения. Использование функций в качестве аргументов — чрезвычайно распространённая практика в Haskell.
Отображение
Рассмотрим функцию map . Эта стандартная функция используется для отображения (англ. mapping) функции на элементы списка. Пусть вас не смущает такой термин: отображение функции на элемент фактически означает её применение к этому элементу.
Вот объявление функции map :
Результатом работы этой программы будет строка:
Вот её объявление:
Функция из Char в Char выступает первым аргументом функции map , подставим сигнатуру:
Ага, уже теплее! Мы сделали два новых открытия: во-первых, заглушки a и b могут быть заняты одним и тем же конкретным типом, а во-вторых, сигнатура позволяет нам тут же понять остальные типы. Подставим их:
А теперь вспомним о природе типа String :
Всё встало на свои места. Функция map в данном случае берёт функцию toUpper и бежит по списку, последовательно применяя эту функцию к его элементам:
Так, на первом шаге функция toUpper будет применена к элементу 'h' , на втором — к элементу 'a' , и так далее до последнего элемента 'g' . Когда функция map бежит по этому списку, результат применения функции toUpper к его элементам служит элементами для второго списка, который и будет в конечном итоге возвращён. Так, результатом первого шага будет элемент 'H' , результатом второго — элемент 'A' , а результатом последнего — элемент 'G' . Схема такова:
Вот и получается:
Работа функции map выглядит как изменение списка, однако, в виду неизменности последнего, в действительности формируется новый список. Что самое интересное, функция toUpper пребывает в полном неведении о том, что ею в конечном итоге изменяют регистр целой строки, она знает лишь об отдельных символах этой строки. То есть функция, являющаяся аргументом функции map , ничего не знает о функции map , и это очень хорошо! Чем меньше функции знают друг о друге, тем проще и надёжнее использовать их друг с другом.
Рассмотрим другой пример, когда типовые заглушки a и b замещаются разными типами:
Функция toStr работает уже со списками разных типов: на входе список чисел с плавающей точкой, на выходе список строк. При запуске этой программы мы увидим следующее:
Уже знакомая нам стандартная функция show переводит свой единственный аргумент в строковый вид:
В данном случае, раз уж мы работаем с числами типа Double , тип функции show такой:
Подставим в сигнатуру функции map :
Именно так, как у нас и есть:
Функция map применяет функцию show к числам из первого списка, на выходе получаем второй список, уже со строками. И как и в случае с toUpper , функция show ничего не подозревает о том, что ею оперировали в качестве аргумента функции map .
Разумеется, в качестве аргумента функции map мы можем использовать и наши собственные функции:
Мы передали функции map нашу собственную ЛФ, умножающую свой единственный аргумент на 10 . Обратите внимание, мы вновь использовали краткую форму определения функции ten , опустив имя её аргумента. Раскроем подробнее:
Вы спросите, как же вышло, что оператор применения расположен между двумя аргументами функции map ? Разве он не предназначен для применения функции к единственному аргументу? Совершенно верно. Пришло время открыть ещё один секрет Haskell.
Частичное применение
Вспомним сокращённое определение функции ten :
Функция map получила лишь первый аргумент, а где же второй? Второй, как мы уже знаем, будет получен ею уже потом, после того, как мы подставим это выражение на место функции ten . Но что же происходит с функцией map до этого? А до этого с ней происходит частичное применение. Понятно, что она ещё не может выполнить свою работу, поэтому, будучи применённой лишь к одному аргументу, она возвращает ЛФ! Сопоставим с типом функции map , и всё встанет на свои места:
Поскольку голова в виде первого аргумента типа (a -> b) уже дана, осталось получить второй аргумент. Поэтому ЛФ, порождённая частичным применением, ожидает единственный аргумент, которым и будет тот самый второй, а именно список [1.2, 1,4, 1.6] .
Сопоставим тип функции ten с типом map , чтобы понять, где наш хвост:
Вот почему мы можем использовать краткую форму определения для функции ten : она уже является нашим хвостом!
Рассмотрим ещё один пример частичного применения, дабы закрепить наше понимание:
Это объявление функции replace , принимающей три строки: первая содержит то, что ищем, вторая содержит то, на что заменяем, а в третьей лежит то, где ищем. Например:
Определение функции replace нас сейчас не интересует, рассмотрим пошаговое применение:
Тип выражения first — String -> String -> String , оно явилось результатом частичного применения функции replace к первому аргументу, строке "http" . Тип выражения second — String -> String , оно явилось результатом вторичного частичного применения функции first к уже второму аргументу, строке "https" . И наконец, применив функцию second к третьему аргументу, строке "http://google.com" , мы наконец-то получаем конечный результат, ассоциированный с выражением result .
Из этого мы делаем интересное открытие:
Функция от нескольких аргументов может быть разложена на последовательность применений временных функций от одного аргумента каждая.
Поэтому мы и смогли подставить частично применённую map на место выражения ten . Используем круглые скобки, дабы яснее показать, что есть что:
Гибко, не правда ли? Теперь мы знакомы с частичным применением функции.
Композиция для отображения
Вернёмся к функции map . Если мы можем передать ей некую функцию для работы с элементами списка, значит мы можем передать ей и композицию двух или более функций. Например:
Мы хотим украсить имена трёх языков программирования. Для этого мы пробегаемся по списку композицией двух функций, big и stars . Функция big переводит строки в верхний регистр, а функция stars украшает имя двумя звёздочками в начале и в конце. В результате имеем:
Пройтись по списку композицией stars . big равносильно тому, как если бы мы прошлись сначала функцией big , а затем функцией stars . При этом, как мы уже знаем, обе эти функции ничего не знают ни о том, что их скомпоновали, ни о том, что эту композицию передали функции map .
Ну что ж, теперь мы знаем о функции map , и последующих главах мы увидим множество других ФВП. Отныне они будут нашими постоянными спутниками.
Since Haskell is a functional language, one would expect functions to play a major role, and indeed they do. In this section, we look at several aspects of functions in Haskell.
First, consider this definition of a function which adds its two arguments:
add :: Integer -> Integer -> Integer
add x y = x + y
This is an example of a curried function. (The name curry derives from the person who popularized the idea: Haskell Curry. To get the effect of an uncurried function, we could use a tuple , as in:
But then we see that this version of add is really just a function of one argument!) An application of add has the form add e1 e2, and is equivalent to (add e1) e2, since function application associates to the left . In other words, applying add to one argument yields a new function which is then applied to the second argument. This is consistent with the type of add, Integer->Integer->Integer, which is equivalent to Integer->(Integer->Integer); i.e. -> associates to the right . Indeed, using add, we can define inc in a different way from earlier:
This is an example of the partial application of a curried function, and is one way that a function can be returned as a value. Let's consider a case in which it's useful to pass a function as an argument. The well-known map function is a perfect example:
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
[Function application has higher precedence than any infix operator, and thus the right-hand side of the second equation parses as (f x) : (map f xs).] The map function is polymorphic and its type indicates clearly that its first argument is a function; note also that the two a's must be instantiated with the same type (likewise for the b's). As an example of the use of map, we can increment the elements in a list:
These examples demonstrate the first-class nature of functions, which when used in this way are usually called higher-order functions.
3.1 Lambda Abstractions
Instead of using equations to define functions, we can also define them "anonymously" via a lambda abstraction . For example, a function equivalent to inc could be written as \x -> x+1. Similarly, the function add is equivalent to \x -> \y -> x+y. Nested lambda abstractions such as this may be written using the equivalent shorthand notation \x y -> x+y. In fact, the equations:
inc x = x+1
add x y = x+y
inc = \x -> x+1
add = \x y -> x+y
We will have more to say about such equivalences later.
In general, given that x has type t1 and exp has type t2, then \x->exp has type t1->t2.
3.2 Infix Operators
Infix operators are really just functions, and can also be defined using equations. For example, here is a definition of a list concatenation operator:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs++ys)
[Lexically, infix operators consist entirely of "symbols," as opposed to normal identifiers which are alphanumeric (§2.4). Haskell has no prefix operators, with the exception of minus (-), which is both infix and prefix.]
As another example, an important infix operator on functions is that for function composition :
(.) :: (b->c) -> (a->b) -> (a->c)
f . g = \ x -> f (g x)
3.2.1 Sections
Since infix operators are really just functions, it makes sense to be able to partially apply them as well. In Haskell the partial application of an infix operator is called a section . For example:
| (x+) | = | \y -> x+y |
| (+y) | = | \x -> x+y |
| (+) | = | \x y -> x+y |
[The parentheses are mandatory.]
The last form of section given above essentially coerces an infix operator into an equivalent functional value, and is handy when passing an infix operator as an argument to a function, as in map (+) [1,2,3] (the reader should verify that this returns a list of functions!). It is also necessary when giving a function type signature, as in the examples of (++) and (.) given earlier.
We can now see that add defined earlier is just (+), and inc is just (+1)! Indeed, these definitions would do just fine:
We can coerce an infix operator into a functional value, but can we go the other way? Yes---we simply enclose an identifier bound to a functional value in backquotes. For example, x `add` y is the same as add x y. (Note carefully that add is enclosed in backquotes , not apostrophes as used in the syntax of characters; i.e. 'f' is a character, whereas `f` is an infix operator. Fortunately, most ASCII terminals distinguish these much better than the font used in this manuscript.) Some functions read better this way. An example is the predefined list membership predicate elem; the expression x `elem` xs can be read intuitively as "x is an element of xs."
[There are some special rules regarding sections involving the prefix/infix operator -; see (§3.5,§3.4).]
At this point, the reader may be confused at having so many ways to define a function! The decision to provide these mechanisms partly reflects historical conventions, and partly reflects the desire for consistency (for example, in the treatment of infix vs. regular functions).
3.2.2 Fixity Declarations
infixr 5 ++
infixr 9 .
Both of these specify right-associativity, the first with a precedence level of 5, the other 9. Left associativity is specified via infixl, and non-associativity by infix. Also, the fixity of more than one operator may be specified with the same fixity declaration. If no fixity declaration is given for a particular operator, it defaults to infixl 9. (See §4.4.2 for a detailed definition of the associativity rules.)
3.3 Functions are Non-strict
Suppose bot is defined by:
In other words, bot is a non-terminating expression. Abstractly, we denote the value of a non-terminating expression as _|_ (read "bottom"). Expressions that result in some kind of a run-time error, such as 1/0, also have this value. Such an error is not recoverable: programs will not continue past these errors. Errors encountered by the I/O system, such as an end-of-file error, are recoverable and are handled in a different manner. (Such an I/O error is really not an error at all but rather an exception. Much more will be said about exceptions in Section 7.)
A function f is said to be strict if, when applied to a nonterminating expression, it also fails to terminate. In other words, f is strict iff the value of f bot is _|_. For most programming languages, all functions are strict. But this is not so in Haskell. As a simple example, consider const1, the constant 1 function, defined by:
The value of const1 bot in Haskell is 1. Operationally speaking, since const1 does not "need" the value of its argument, it never attempts to evaluate it, and thus never gets caught in a nonterminating computation. For this reason, non-strict functions are also called "lazy functions", and are said to evaluate their arguments "lazily", or "by need".
Since error and nonterminating values are semantically the same in Haskell, the above argument also holds for errors. For example, const1 (1/0) also evaluates properly to 1.
Non-strict functions are extremely useful in a variety of contexts. The main advantage is that they free the programmer from many concerns about evaluation order. Computationally expensive values may be passed as arguments to functions without fear of them being computed if they are not needed. An important example of this is a possibly infinite data structure.
Another way of explaining non-strict functions is that Haskell computes using definitions rather than the assignments found in traditional languages. Read a declaration such as
as `define v as 1/0' instead of `compute 1/0 and store the result in v'. Only if the value (definition) of v is needed will the division by zero error occur. By itself, this declaration does not imply any computation. Programming using assignments requires careful attention to the ordering of the assignments: the meaning of the program depends on the order in which the assignments are executed. Definitions, in contrast, are much simpler: they can be presented in any order without affecting the meaning of the program.
3.4 "Infinite" Data Structures
One advantage of the non-strict nature of Haskell is that data constructors are non-strict, too. This should not be surprising, since constructors are really just a special kind of function (the distinguishing feature being that they can be used in pattern matching). For example, the constructor for lists, (:), is non-strict.
Non-strict constructors permit the definition of (conceptually) infinite data structures. Here is an infinite list of ones:
numsFrom n = n : numsFrom (n+1)
Thus numsFrom n is the infinite list of successive integers beginning with n. From it we can construct an infinite list of squares:
squares = map (^2) (numsfrom 0)
(Note the use of a section; ^ is the infix exponentiation operator.)
Of course, eventually we expect to extract some finite portion of the list for actual computation, and there are lots of predefined functions in Haskell that do this sort of thing: take, takeWhile, filter, and others. The definition of Haskell includes a large set of built-in functions and types---this is called the "Standard Prelude". The complete Standard Prelude is included in Appendix A of the Haskell report; see the portion named PreludeList for many useful functions involving lists. For example, take removes the first n elements from a list:
The definition of ones above is an example of a circular list . In most circumstances laziness has an important impact on efficiency, since an implementation can be expected to implement the list as a true circular structure, thus saving space.
For another example of the use of circularity, the Fibonacci sequence can be computed efficiently as the following infinite sequence:
where zip is a Standard Prelude function that returns the pairwise interleaving of its two list arguments:
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip xs ys = []
Note how fib, an infinite list, is defined in terms of itself, as if it were "chasing its tail." Indeed, we can draw a picture of this computation as shown in Figure 1.
Figure 1
For another application of infinite lists, see Section 4.4.
3.5 The Error Function
Haskell has a built-in function called error whose type is String->a. This is a somewhat odd function: From its type it looks as if it is returning a value of a polymorphic type about which it knows nothing, since it never receives a value of that type as an argument!
In fact, there is one value "shared" by all types: _|_. Indeed, semantically that is exactly what value is always returned by error (recall that all errors have value _|_). However, we can expect that a reasonable implementation will print the string argument to error for diagnostic purposes. Thus this function is useful when we wish to terminate a program when something has "gone wrong." For example, the actual definition of head taken from the Standard Prelude is:
Читайте также: