28 ноября 2013 в 21:48

Конспекты лекций «Haskell как первый язык программирования». Часть1

• Haskell ,
• Функциональное программирование

• Tutorial

Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell…

Базовые типы Haskell

Базовые типы языка Haskell - это:
Числа
Логические величины
Символы
Списки
Упорядоченные множества (tuples)
Функции

Числа
Целые:
Integer (-∞,∞)
Int (-2^31, 2^31-1)
В прелюдии (стандартной библиотеке) определенно много полезных функций для целых чисел, в том числе, и преобразование в число с плавающей точкой (fromInt и fromInteger)

Числа с плавающей точкой:
Float (7 знаков после запятой)
Double (16 знаков после запятой)

Логические величины
Bool (True | False)
Операции конъюнкции, дизъюнкции и отрицания (&&, ||, not)

Символы
Char (’a’)
И функции Char в Int и Int в Char (ord, chr)

Списки
Списки могут быть разные:
- список целых чисел
- список символов (строка)
[] - массив
- это список функций
и т. д.

Несколько стандартных операций в примерах:
Main> head
1
Main> tail
Main> length
2
Main> reverse
Main> 0:
Main> - строка приглашения в консоли компилятора ghci
«:» - операция присоединения элемента к списку.

Упорядоченные множества
Примеры:
(2.4, ”cat”) (Float, )
(’a’, True, 1) (Char, Bool, Int)
(,sqrt) (, Float->Float)
(1, (2, 3)) (Int, (Int, Int))

Но, сердце Haskell и всего функционального программирования - это, конечно, сами функции!

Функции

Функция, в современной математике, это закон соответствия, который сопоставляет каждому элементу x из данного множества A один единственный (или ни одного) элемент y из множества B.
Haskell, по своему назначению, это, прежде всего, язык математиков, поэтому синтаксис тут максимально точно соответствует этому определению.
Пример:
square:: Integer -> Integer square x = x*x
Как вы, наверное, догадались, это функция возведения числа в квадрат. Разберем её подробно:

Первая строка - это объявление функции:
Имя_функции:: область_определения - > область _значений
square:: Integer -> Integer
Тут следует сказать, что в Haskell совсем необязательно всегда объявлять функцию. В ряде случаев интерпретатор и так поймет какие у данной функции области определения и значения. Однако, опускать объявления - моветон.

Вторая строка - это определение функции:
Имя_функции параметры = правило_вычисления
square x = x*x

Функция без параметров есть ничто иное, как константа:
e:: Float e = exp 1.0

Функция с несколькими параметрами:
Спасибо за разъяснения ().
abcFormula:: Float -> Float -> Float -> abcFormula a b c = [ (-b+sqrt(b*b-4.0*a*c))/(2.0*a), (-b-sqrt(b*b-4.0*a*c))/(2.0*a) ] -- находит корни уравнения ax^2+bx+c=0

Определения функций с альтернативами

Как и в любом языке, в Haskell есть конструкции ветвления.
Разберем их на примере функции abs (модуль).
If … then … else …
abs1 x = if x>=0 then x else -x

Case … of …
abs2 x = case x>=0 of True -> x False -> -x

Но, помимо стандартных if и case, в Haskell есть очень красивая и наиболее используемая конструкция ветвления. Так называемые, охранные выражения . Пример:
abs3 x | x>0 = x | x<0 = -x | otherwise = 0
Прямую черту следует читать, как: «при».
Читаем: «Функция abs3, с входным параметром x, при x>0 принимает значение x, при x<0 принимает значение -x, и в любом другом случае принимает значение 0».
Конечно, мы могли записать все с помощью двух охранных выражений, но я записал три, что бы было понятно, что их может быть сколько угодно.
Otherwise в прелюдии определен очень просто:
otherwise:: Bool otherwise = True
То есть, можно спокойно написать вместо «otherwise» «True», но это, опять же, моветон.

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

Один из наиболее распространенных и эффективных приемов в Haskell - это сопоставление с образцом. Вместо параметра мы можем подсунуть функции пример того, как должен выглядеть параметр. Если образец подошел функция выполняется, если нет - переходит к следующему образцу. Например, определение факториала через рекурсию с помощью образцов:
fact:: Integer -> Integer fact 0 = 1 fact n = n * fact (n-1)
Тоже самое, но, с помощью охранных выражений:
fact:: Integer -> Integer fact n | n==0 = 1 | n>0 = n*fact (n-1)
Есть очень распространенный образец для списка: (x:xs). X - обозначает первый элемент, XS - остальной список (кроме первого элемента). «:» - операция присоединения элемента к списку. Примеры из прелюдии:
head:: [a] -> a head (x:_) = x head = error "Prelude.head: empty list" tail:: [a] -> [a] tail (_:xs) = xs tail = error "Prelude.tail: empty list"
Функция head принимает на вход список чего угодно [a] и возвращает первый элемент этого списка. Функция tail принимает на вход список чего угодно [a] и изымает из этого списка первый элемент.
«_» - означает, что данный элемент нас не интересует.

Ну вот, на сегодня и все. Если будет интерес, в ближайшее время напишу продолжение.

Мне задавали их множество раз. Отвечаю.

«Что такое этот ваш Haskell?»

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

«Это что, какой-то новый язык?»

Вовсе нет. История Haskell началась ещё в 1987 году. Этот язык был рождён в математических кругах, когда группа людей решила создать лучший функциональный язык программирования. В 1990 году вышла первая версия языка, названного в честь известного американского математика Хаскелла Карри . В 1998 году язык был стандартизован, а начиная с 2000-х началось его медленное вхождение в мир практического программирования. За эти годы язык совершенствовался, и вот в 2010 мир увидел его обновлённый стандарт. Так что мы имеем дело с языком, который старше Java.

«И кто его сделал?»

Haskell создавался многими людьми. Наиболее известная реализация языка нашла своё воплощение в компиляторе GHC (The Glasgow Haskell Compiler), родившегося в 1989 году в Университете Глазго. У компилятора было несколько главных разработчиков, из которых наиболее известны двое, Simon Peyton Jones и Simon Marlow . Впоследствии весомый вклад в разработку GHC внесли ещё несколько сотен человек. Исходный код компилятора GHC открыт . Кстати, сам компилятор на 82% написан на Haskell.

Для любопытных: исчерпывающее повествование об истории Haskell и GHC читайте .

«А библиотеки для Haskell имеются?»

О да! Их даже не сотни - их тысячи. В процессе чтения вы познакомитесь со многими из них.

«И что, его уже можно в production?»

Он уже в production. С момента выхода первого стандарта язык улучшался, развивалась его экосистема, появлялись новые библиотеки, выходили в свет книги. Haskell полностью готов к серьёзному коммерческому использованию, о чём свидетельствуют истории успешного внедрения Haskell в бизнесе, в том числе крупном .

«А порог вхождения в Haskell высокий?»

И да и нет. Освоение Haskell сложно в первую очередь из-за его непохожести на остальные языки, поэтому людям, имеющим опыт работы с другими языками, мозги поломать придётся. Именно поломать, а не просто пошевелить ими: Haskell заставляет иначе взглянуть даже на привычные вещи. С другой стороны, Haskell проще многих известных языков. Не верьте мне на слово, вскоре вы и сами в этом убедитесь. И знайте: многие люди, узнав вкус Haskell, категорически не желают возвращаться к другим языкам. Я вас предупредил.

«А я слышал ещё про какие-то монады…»

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

«А если сравнить его с C++/Python/Scala…»

Сравнение Haskell с другими языками выходит за рамки этой книги. Несколько раз вы встретите здесь кусочки кода на других языках, но я привожу их исключительно для того, чтобы подчеркнуть различие с Haskell, а вовсе не для сравнения в контексте «лучше/хуже». И вообще, я буду изо всех сил стараться не восхвалять Haskell без меры, я хочу лишь рассказать вам правду о нём. Мой вывод об этом языке я уже сделал, а свой вывод о нём вы должны сделать сами.

Типы

Программы на языке Haskell представляют собой выражения, вычисление которых приводит к значениям. Каждое значение имеет тип. Интуитивно тип можно понимать просто как множество допустимых значений выражения. Для того, чтобы узнать тип некоторого выражения, можно использовать команду интерпретатора:type (или:t). Кроме того, можно выполнить команду:set +t, для того, чтобы интерпретатор автоматически печатал тип каждого вычисленного результата.
Основными типами языка Haskell являются:
Типы Integer и Int используется для представления целых чисел, причем значения типа Integer не ограничены по длине.
Типы Float и Double используется для представления вещественных чисел.
Тип Bool содержит два значения: True и False, и предназначен для представления результата логических выражений.
Тип Char используется для представления символов. Имена типов в языке Haskell всегда начинаются с заглавной буквы.
Язык Haskell является сильно типизированным языком программирования. Тем не менее в большинстве случаев программист не обязан объявлять, каким типам принадлежат вводимые им переменные. Интерпретатор сам способен вывести типы употребляемых пользователем переменных.
Однако, если все же для каких-либо целей необходимо объявить, что некоторое значение принадлежит некоторому типу, используется конструкция вида: переменная:: Тип. Если включена опция интерпретатора +t, он печатает значения в таком же формате.
Ниже приведен пример протокола сессии работы с интерпретатором. Предполагается, что текст, следующий за приглашением Prelude>, вводит пользователь, а следующий за этим текст представляет ответ системы.

Prelude>:set +t
Prelude>1
1:: Integer
Prelude>1.2
1.2:: Double
Prelude>’a’
’a’ :: Char
Prelude>True
True:: Bool

Из данного протокола можно сделать вывод, что значения типа Integer, Double и Char задаются по тем же правилам, что и в языке Си.
Развитая система типов и строгая типизация делают программы на языке Haskell безопасными по типам. Гарантируется, что в правильной программе на языке Haskell все типы используются правильно. С практической точки зрения это означает, что программа на языке Haskell при выполнении не может вызвать ошибок доступа к памяти (Access violation). Также гарантируется, что в программе не может произойти использование неинициализированных переменных. Таким образом, многие ошибки в программе отслеживаются на этапе ее компиляции, а не выполнения.

Арифметика

Интерпретатор Hugs можно использовать для вычисления арифметических выражений. При этом можно использовать операторы +, -, *, / (сложение, вычитание, умножение и деление) с обычными правилами приоритета.
Кроме того, можно использовать оператор ^ (возведение в степень). Таким образом, сеанс работы может выглядеть следующим образом:

Prelude>2*2
4:: Integer
Prelude>4*5 + 1
21:: Integer
Prelude>2^3
8:: Integer
Кроме того, можно использовать стандартные математические функции sqrt (квадратный корень), sin, cos, exp и т.д. В отличие от многих других языков программирования, в Haskell при вызове функции не обязательно помещать аргумент в скобки. Таким образом, можно просто писать sqrt 2, а не sqrt(2). Пример:

Prelude>sqrt 2
1.4142135623731:: Double
Prelude>1 + sqrt 2
2.4142135623731:: Double
Prelude>sqrt 2 + 1
2.4142135623731:: Double
Prelude>sqrt (2 + 1)
1.73205080756888:: Double

Из данного примера можно сделать вывод, что вызов функции имеет более высокий приоритет, чем арифметические операции, так что выражение sqrt 2 + 1 интерпретируется как (sqrt 2) + 1, а не sqrt (2 + 1). Для задания точного порядка вычисления следует использовать скобки, как в последнем примере. (В действительности вызов функции имеет более высокий приоритет, чем любой бинарный оператор.)
Также следует заметить, что в отличие от большинства других языков программирования, целочисленные выражения в языке Haskell вычисляются с неограниченным числом разрядов (Попробуйте вычислить выражение 2^5000.) В отличие от языка Си, где максимально возможное значение типа int ограничено разрядностью машины (на современных персональных компьютерах оно равно 231-1 = 2147483647), тип Integer в языке Haskell может хранить целые числа произвольной длины.

Кортежи
Помимо перечисленных выше простых типов, в языке Haskell можно определять значения составных типов. Например, для задания точки наплоскости необходимы два числа, соответствующие ее координатам. В языке Haskell пару можно задать, перечислив компоненты через запятую и взяв их в скобки: (5,3). Компоненты пары не обязательно должны принадлежать одному типу: можно составить пару, первым элементом которой будет строка, а вторым - число и т.д.
В общем случае, если a и b - некоторые произвольные типы языка Haskell, тип пары, в которой первый элемент принадлежит типу a, а второй - типу b, обозначается как (a,b). Например, пара (5,3)имеет тип (Integer, Integer); пара (1, ’a’) принадлежит типу (Integer, Char). Можно привести и более сложный пример: пара((1,’a’),1.2) принадлежит типу ((Integer,Char),Double). Проверьте это с помощью интерпретатора. Следует обратить внимания, что хотя конструкции вида (1,2) и (Integer,Integer) выглядят похоже, в языке Haskell они обозначают совершенно разные сущности. Первая является значением, в то время как последняя - типом. Для работы с парами в языке Haskell существуют стандартные функции fst и snd, возвращающие, соответственно, первый и второй элементы пары (названия этих функций происходят от английских слов «first» (первый) и «second» (второй)). Таким образом, их можно использовать следующим образом

Prelude>fst (5, True)
5:: Integer
Prelude>snd (5, True)
True:: Bool
Кроме пар, аналогичным образом можно определять тройки, четверки и т.д. Их типы записываются аналогичным образом.
Prelude>(1,2,3)
(1,2,3) :: (Integer,Integer,Integer)
Prelude>(1,2,3,4)
(1,2,3,4) :: (Integer,Integer,Integer,Integer)
Такая структура данных называется кортежем. В кортеже может хранится фиксированное количество разнородных данных. Функции fst и snd определены только для пар и не работают для других кортежей. При попытке использовать их, например, для троек, интерпретатор выдает сообщение об ошибке. Элементом кортежа может быть значение любого типа, в том числе и другой кортеж. Для доступа к элементам кортежей, составленных из пар, может использоваться комбинация функций fst и snd. Следующий пример демонстрирует извлечение элемента ’a’ из кортежа
(1, (’a’, 23.12)):
Prelude>fst (snd (1, (’a’, 23.12)))
’a’ :: Integer

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

Prelude>
::
Prelude>[’1’,’2’,’3’]
[’1’,’2’,’3’] ::
В списке может не быть ни одного элемента. Пустой список обозначается как .
Оператор: (двоеточие) используется для добавления элемента в начало списка. Его левым аргументом должен быть элемент, а правым - список:
Prelude>1:
::
Prelude>’5’:[’1’,’2’,’3’,’4’,’5’]
[’5’,’1’,’2’,’3’,’4’,’5’] ::
Prelude>False:
::
С помощью оператора (:) и пустого списка можно построить любой список:
Prelude>1:(2:(3:))
:: Integer
Оператор (:) ассоциативен вправо, поэтому в приведенном выше выражении можно опустить скобки:
Prelude>1:2:3:
:: Integer
Элементами списка могут быть любые значения - числа, символы, кортежи, другие списки и т.д.
Prelude>[(1,’a’),(2,’b’)]
[(1,’a’),(2,’b’)] :: [(Integer,Char)]
Prelude>[,]
[,] :: []
Для работы со списками в языке Haskell существует большое количество функций. В данной лабораторной работе рассмотрим только некоторые из них.
Функция head возвращает первый элемент списка.
Функция tail возвращает список без первого элемента.
Функция length возвращает длину списка.
Функции head и tail определены для непустых списков. При попытке применить их к пустому списку интерпретатор сообщает об ошибке. Примеры работы с указанными функциями:
Prelude>head
1:: Integer
Prelude>tail
::
Prelude>tail
:: Integer
Prelude>length
3:: Int
Заметьте, что результат функции length принадлежит типу Int, а не типу Integer.
Для соединения (конкатенации) списков в Haskell определен оператор ++.
Prelude>++
:: Integer

Строки
Строковые значения в языке Haskell, как и в Си, задаются в двойных кавычках. Они принадлежат типу String.
Prelude>"hello" "hello" :: String
В действительности строки являются списками символов; таким образом, выражения "hello", [’h’,’e’,’l’,’l’,’o’] и

’h’:’e’:’l’:’l’:’o’: означают одно и то же, а тип String является синонимом для . Все функции для работы со списками можно использовать при работе со строками:
Prelude>head "hello"
’h’ :: Char
Prelude>tail "hello"
"Hello" ::
Prelude>length "hello"
5:: Int
Prelude>"hello" ++ ", world"
"hello, world" ::
Для преобразования числовых значений в строки и наоборот существуют функции read и show:
Prelude>show 1
"1" ::
Prelude>"Formula " ++ show 1
"Formula 1" ::
Prelude>1 + read "12"
13:: Integer
Если функция show не сможет преобразовать строку в число, она сообщит об ошибке.

Функции
До сих пор мы использовали встроенные функции языка Haskell. Теперь пришла пора научиться определять собственные функции. Для этого нам необходимо изучить еще несколько команд интерпретатора (напомним, что эти команды могут быть сокращены до одной буквы):
Команда:load позволяет загрузить в интерпретатор программу на языке Haskell, содержащуюся в указанном файле.
Команда:edit запускает процесс редактирования последнего загруженного файла.
Команда:reload перечитывает последний загруженный файл. Определения пользовательских функций должны находиться в файле, который нужно загрузить в интерпретатор Hugs с помощью команды:load.
Для редактирования загруженной программы можно использовать команду:edit. Она запускает внешний редактор (по умолчанию это Notepad) для редактирования файла. После завершения сеанса редактирования редактор необходимо закрыть; при этом интерпретатор Hugs перечитает содержимое изменившегося файла. Однако файл можно редактировать и непосредственно из оболочки Windows. В этом случае, для того чтобы интерпретатор смог перечитать файл, необходимо явно вызывать команду:reload.
Рассмотрим пример. Создайте в каком-либо каталоге файл lab1.hs. Пусть полный путь к этому файлу - с:\labs\lab1.hs (это только пример, ваши файлы могут называться по-другому). В интерпретаторе Hugs выполните следующие команды:

Prelude>:load "c:\\labs\\lab1.hs"
Если загрузка проведена успешно, приглашение интерпретатора меняется на Main>. Дело в том, что если не указано имя модуля, считается, что оно равно Main.
Main>:edit
Здесь должно открыться окно редактора, в котором можно вводить текст программы. Введите:
x =
Сохраните файл и закройте редактор. Интерпретатор Hugs загрузит файл
с:\labs\lab1.hs и теперь значение переменной x будет определено:
Main>x
::
Обратите внимание, что при записи имени файла в аргументе команды:load символы \ дублируются. Также, как и в языке Си, в Haskell символ \ служит индикатором начало служебного символа (’\n’ и т.п.) Для того, чтобы ввести непосредственно символ \, необходимо, как и в Си, экранировать его еще одним символом \.
Теперь можно перейти к определению функций. Создайте, в соответствие с процессом, описанным выше, какой-либо файл и запишите в него следующий текст:

square:: Integer -> Integer
square x = x * x

Первая строка (square:: Integer -> Integer) объявляет, что мы определяем функцию square, принимающую параметр типа Integer и возвращающую результат типа Integer. Вторая строка (square x = x * x) является непосредственно определением функции. Функция square принимает один аргумент и возвращает его квадрат. Функции в языке Haskell являются значениями «первого класса». Это означает, что они «равноправны» с такими значениями, как целые и вещественные числа, символы, строки, списки и т.д. Функции можно передавать в качестве аргументов в другие функции, возвращать их из функций и т.п. Как и все значения в языке Haskell, функции имеют тип. Тип функции, принимающей значения типа a и возвращающей значения типа b обозначается как a->b.
Загрузите созданный файл в интерпретатор и выполните следующие команды:

Main>:type square
square:: Integer -> Integer
Main>square 2
4:: Integer
Заметим, что в принципе объявление типа функции square не являлось необходимым: интерпретатор сам мог вывести необходимую информацию о типе функции из ее определения. Однако, во-первых, выведенный тип был бы более общим, чем Integer -> Integer, а во-вторых, явное указание типа функции является «хорошим тоном» при программировании на языке Haskell, поскольку объявление типа служит своего рода документацией к функции и помогает выявлять ошибки программирования.
Имена определяемых пользователем функций и переменных должны начинаться с латинской буквы в нижнем регистре. Остальные символы в имени могут быть прописными или строчными латинскими буквами, цифрами или символами _ и ’ (подчеркивание и апостроф). Таким образом, ниже перечислены примеры правильных имен переменных:

var
var1
variableName
variable_name
var’

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

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

signum:: Integer -> Integer
signum x = if x > 0 then 1
else if x else 0

Условное выражение записывается в виде:
if условие then выражение else выражение. Обратите внимание, что хотя по виду это выражение напоминает соответствующий оператор в языке Си или Паскаль, в условном выражении языка Haskell должны присутствовать и then-часть и else-часть. Выражения в then-части и в else-части условного оператора должны принадлежать одному типу. Условие в определении условного оператора представляет собой любое выражение типа Bool. Примером таких выражений могут служить сравнения. При сравнении можно использовать следующие операторы:
, = - эти операторы имеют такой же смысл, как и в языке Си (меньше, больше, меньше или равно, больше или равно).
== - оператор проверки на равенство.
/= - оператор проверки на неравенство.
Выражения типа Bool можно комбинировать с помощью общепринятых логических операторов && и || (И и ИЛИ), и функции отрицания not.
Примеры допустимых условий:
x >= 0 && x x > 3 && x /= 10
(x > 10 || x Разумеется, можно определять свои функции, возвращающие значения типа Bool, и использовать их в качестве условий. Например, можно определить функцию isPositive, возвращающую True, если ее аргумент неотрицателен и False в противном случае:
isPositive:: Integer -> Bool
isPositive x = if x > 0 then True else False

Теперь функцию signum можно определить следующим образом:
signum:: Integer -> Integer
signum x = if isPositive x then 1
else if x else 0
Отметим, что функцию isPositive можно определить и проще:
isPositive x = x > 0

Информация бралась с: http://sguprog.narod.ru/

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

Часть 1. Введение

Серия контента:

Императивное программирование

Наиболее распространены императивные языки , в которых вычисление сводится к последовательному выполнению инструкций. Решение задачи на императивном языке сводится к описанию того, что необходимо проделать, чтобы получить результат. Классические примеры – FORTRAN (1957), ALGOL (1958) и C (1972).

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

Переменные рассматриваются как изменяющиеся во времени ячейки памяти. Текущие значения переменных в программе образуют изменяющееся состояние.

Пример императивного кода – процедура для вычисления факториала на C:

int fac (int n) { int x = 1; while (n > 0) { x = x*n; n = n-1; } return x; }

Здесь повторение операции умножения выражено через цикл. В процессе вычисления изменяются значения переменных x и n .

Инициализация: n:= 3; x:= 1; Первый виток цикла: x:= 1*3 = 3; n:= 3-1 = 2; Второй виток цикла: x:= 3 * 2 = 6; n:= 2 - 1 = 1; Третий виток цикла: x:= 6 * 1 = 6; n:= 1 - 1 = 0; Результат - 6

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

Функции и функциональность

В математическом смысле функция f: X → Y – это правило, сопоставляющее элементу x из множества X (области ) элемент y = f x из множества Y (кообласти ).

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

Если значения определены для всех элементов области, то функция называется всюду определенной; в противном случае она называется частичной.

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

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

fac 0 = 1 fac n = n * fac (n-1)

n – формальный аргумент функции fac . В правой части после знака = описано, что функция делает со своим аргументом. Базовые функции для умножения и вычитания записаны через инфиксные (указываемые между аргументами) операторы * и - .

Здесь уравнений два. При вычислении функции уравнения просматриваются по порядку. Если n = 0, то будет использовано первое уравнение. Если n ≠ 0, то оно не подойдет, и задействуется второе.

Обратите внимание: аргументы функции перечисляются рядом с ее именем через пробел. Это удобно, потому что применение функции очень часто встречается в функциональных программах (таблица 1).

Запись в математике	Запись в Haskell
f(x)	f x
f(x,y)	f x y
f(g(x))	f (g x)
f(g(x),h(y))	f (g x) (h y)
f(x) + g(x)	f x + g x
f (x+y)	f (x+y)
f(-x)	f (-x)

Таблица 1. Запись применения функции в математике и в Haskell

Уравнения для fac составляют точное определение функции, а не последовательность действий по вычислению, как это было в императивном коде.

Используется рекурсия, т. е. fac определяется через саму себя. Такое определение работает, потому что fac выражается через более простой случай и, в конечном счете (если n ≥ 0), доходит до базового случая n = 0. Вычисление fac 3 по такому определению можно произвести так (на каждом шаге подчеркнуты упрощаемые выражения):

fac 3 → 3 * fac 2 → 3 * (2 * fac 1) → 3 * (2 * (1 * fac 0)) → 3 * (2 * (1 * 1)) → 3 * (2 * 1) → 3 * 2 → 6

Здесь мы применили f к значению 3 . При этом 3 называется фактическим аргументом .

Функциональный подход сосредоточен на вычислении выражений, а не на выполнении команд. Фактически, функциональная программа – это выражение, и ее выполнение соответствует вычислению выражения.

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

Обратите внимание, что для n < 0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

Теперь запишем функцию, вычисляющую для целых k и вещественных r биномиальный коэффициент

При k ≥ 0 мы имеем выражение, где в знаменателе стоит только что определенный факториал числа k, а в числителе – убывающая факториальная степень (falling factorial power)

Запишем для нее рекурсивное определение:

ffp r 0 = 1 ffp r k = (r-k+1) * ffp r (k-1)

В первом уравнении r не используется, поэтому можно использовать заменитель _ и писать ffp _ 0 = 1 .

Можно убедиться, что

(проверьте это). Поэтому уравнения факториала можно заменить на

fac n = ffp n n

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

Рисунок 2. Черный ящик, вычисляющий убывающую факториальную степень

Возьмем еще один черный ящик (/) с двумя входами x и y и выходом, равным частному x/y:

будет вычислять такая схема:

Рисунок 3. Схема из черных ящиков, вычисляющая биномиальный коэффициент

Она соответствует выражению

ffp r k / fac k

Определим искомую функцию:

binc r k | k >= 0 = ffp r k / fac k | otherwise = 0

Такая запись называется уравнением с условиями (сравните с математической записью определения). После | и до знака = стоят условия. « otherwise » означает «иначе». Подробно это будет рассмотрено в последующих статьях.

Пример вычисления binc 6 2:

binc 6 2 → ffp 6 2 / fac 2 → (5 * ffp 6 1) / fac 2 → (5 * (6 * ffp r 0)) / fac 2 → (5 * (6 * 1)) / fac 2 → (5 * 6) / fac 2 → 30 / fac 2 → 30 / ffp 2 2 → 30 / (1 * ffp 2 1) → 30 / (1 * (2 * ffp r 0)) → 30 / (1 * (2 * 1)) → 30 / (1 * 2) → 30 / 2 → 15

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

Это приводит к важному понятию чистоты.

Чистота

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

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

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

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

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

Каждое выражение в функциональном языке соответствует своему значению; вычисление только модифицирует выражение, но на значение не влияет.

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

Язык без побочных эффектов называется чисто функциональным .

Такие языки, как ML и Scheme, в целом являются функциональными по стилю, однако допускают как присваивания, так и побочные эффекты.

Примеры чисто функциональных языков: Miranda , Haskell и Clean .

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

Ленивость и нестрогость

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

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

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

Например, наша функция binc всегда будет требовать значение k , но значение r требуется, только если k ≥ 0.

В соответствии с этим, говорят о языках со строгой семантикой и языках с нестрогой семантикой. («Нестрогость» и «ленивость» – не одинаковые, но близкие понятия.)

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

В нестрогом языке вычисление производится по необходимости. Если f нестрогая, то вычисление f e может завершиться, даже если вычисление e не завершается.

Например,

обозначает список из трех элементов. Вычисление fac (-1) зацикливается. Значит, вычисление списка также зациклится.

Пусть теперь функция length возвращает длину списка. Выражение

length

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

Примеры нестрогих языков: Miranda и Haskell. Строгие языки – ML и Scheme.

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

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

Краткая история

Функциональное программирование черпает идеи из комбинáторной логики и лямбда-исчисления .

Одними из первых языков с функциональным стилем были LISP (1958), APL (1964), ISWIM (1966) и (1977).

К концу 1980-х годов уже имелось много функциональных языков. Среди тех, которые оказали значительное влияние на Haskell:

• (1973) – первый язык с типизацией Хиндли–Милнера.
• SASL , KRC , Miranda (1972–1985) – одни из первых ленивых языков.
• Hope (1980) – один из первых языков с алгебраическими типами данных. Haskell разрабатывался многочисленной группой исследователей с 1987 г. Он назван в честь Хаскелла Карри .

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

Нововведения Haskell – монады и классы типов. Другие сильные стороны, заимствованные из других языков – каррирование, алгебраические типы данных, сопоставление с образцом. (Здесь мы просто приводим набор ключевых слов; все эти понятия скоро будут разъяснены.)

Последнее зафиксированное описание – Haskell 98, однако язык постоянно развивается и усложняется; сейчас планируется выход Haskell" .

Haskell стал самым популярным нестрогим чисто функциональным языком. На Haskell реализовано много сложных проектов:

• Компиляторы и другие средства разработки.
• Распределенная система управления версиями Darcs .
• Оконный менеджер xmonad .
• Сервер Web-приложений HAppS .
• Интерпретатор/компилятор Pugs для языка Perl 6.
• Операционная система House .
• Язык описания аппаратных средств Lava .
• Система обработки натурального языка LOLITA.
• Системы доказательства теорем Equinox / Paradox и Agda .

Основные источники информации по Haskell

У Haskell имеется широкое и дружелюбное сообщество.

Основной источник информации – сервер haskell.org .

• [email protected] – свободное обсуждение.
• [email protected] – более простые темы для новичков.

  Есть очень оживленный IRC-канал #haskell на irc.freenode.net . В нем можно быстро получить любезный ответ практически на любой вопрос.

  Множество тематических блогов собирается на http://planet.haskell.org/

• Хорошим введением в Haskell может быть руководство A Gentle Introduction to Haskell 98 .
• Документацию по обширным библиотекам смотрите по адресу http://haskell.org/ghc/docs/latest/html/libraries/
• Формальный отчет – The Haskell 98 Report .

Редактирование и выполнение кода

Реализации Haskell

Формально, Haskell не имеет какой-то одной «стандартной» реализации.

Для интерактивной работы подойдет легковесный интерпретатор Hugs .

Также есть интересный проект Yhc , компилирующий исходные тексты в байткод, и Helium – учебный вариант Haskell, дружественный к новичкам (например, выдающий более ясные сообщения об ошибках). Однако они еще находятся в процессе разработки.

Де-факто стандартным стал компилятор/интерпретатор GHC. Он является наиболее продвинутым, во всём соответствует стандарту и предлагает ряд экспериментальных расширений. Мы сконцентрируемся на нем.

GHC можно загрузить по адресу http://haskell.org/ghc/ . Если вы используете GNU/Linux, то посмотрите готовые сборки в своем дистрибутиве. Для MacOS X и Windows можно также найти бинарные файлы. (Учтите, что сборка GHC прямо из исходников может быть довольно утомительным занятием.)

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

Итак, после установки GHC вы можете запустить в терминале ghci:

Здесь Prelude – это название загруженного модуля. В Prelude содержатся основные определения, и он всегда задействуется по умолчанию. Изучая или переписывая самостоятельно код Prelude, начинающие могут узнать много нового. (Мы с вами тоже отчасти будем это делать.)

Символ > означает, что ghci ожидает пользовательский ввод. Это могут быть выражения Haskell, а также команды для интерпретатора.

Клавишами ← и → можно перемещать курсор по командной строке ghci. и ↓ пролистывают историю команд назад и вперед.

Вместо Prelude> или других имен модулей мы дальше будем писать ghci> (если хотите сделать так же, выполните в ghci команду:set prompt "ghci> ").

Для начала ghci можно использовать как продвинутый калькулятор:

ghci> 1*2 + 2*3 + 3*5 23 ghci> 23^23 ghci> gcd 3020199 1161615 232323

Операторы совпадают с принятыми в других языках (таблица 2).

Таблица 2. Арифметические операторы из Prelude

Для них используется инфиксная запись и соответствующий приоритет. Например, 2*3+4 соответствует (2*3)+4 , а 2^3^4 – 2^(3^4) . Чтобы изменить принятый приоритет, можно расставить скобки.

В ghci имеется специальная переменная it , равная значению последнего успешно вычисленного выражения.

ghci> 15 - 2 13 ghci> it + 10 23

Редактирование исходного кода

Исходный код можно править в любимом текстовом редакторе. При этом неплохо иметь подсветку синтаксиса Haskell, а также поддержку выравнивания кода (как мы увидим, в Haskell оно играет особую роль).

• Расширение для Emacs : http://www.iro.umontreal.ca/~monnier/elisp/
• Расширение для Vim : http://projects.haskell.org/haskellmode-vim/

Другие средства разработки описаны на странице http://haskell.org/haskellwiki/Libraries_and_tools/Program_development

Для кода Haskell используется расширение файлов.hs .

Если вы запишете код на Haskell в файл foo.hs , то определения загружаются в ghci командой:load foo . Параллельно файл можно редактировать и при необходимости перезагружать определения при помощи:reload .

Текущая директория изменяется командой:cd (например, :cd /home/bob).

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

$ ghci ghci, version 6.10.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> :load fph01.lhs Compiling Main (fph01.lhs, interpreted) Ok, modules loaded: Main. *Main> ffp 6 6 720 *Main> fac 6 720 *Main> binc 6 2 15.0 *Main> binc 6.5 4 23.4609375

Эти и другие команды можно сокращать – вместо:load использовать:l , вместо:reload – :r и так далее.

Список команд интерпретатора выводит:help . Для выхода из ghci нужно набрать:quit .

В ходе нашего изложения часто будут встречаться простые примеры, состоящие из одного-двух уравнений. Их можно сразу вводить в ghci при помощи let:

ghci> let double x = 2*x ghci> double 23 46

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

ghci> let { fac 0 = 1; fac n = n * fac (n-1) } ghci> fac 23 25852016738884976640000

Заключение

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

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

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

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

* Я предполагаю, что вы подразумеваете статическую типизацию здесь, так как вы хотите объявить типы. Techincally, Python - это строго типизированный язык, поскольку вы не можете произвольно интерпретировать, скажем, строку как число. Интересно, что существуют производные Python, которые позволяют статическую типизацию, например Boo .

2018-12-04T00:00Z

Если вам нужен сильный (эр) личный пролог, Mercury - интересный выбор. В прошлом я занимался этим, и мне нравилась другая перспектива, которую он мне дал. Он также имеет moded-ness (какие параметры должны быть свободными / фиксированными) и детерминизм (сколько результатов есть?) В системе типов.

Clean очень похожа на Haskell, но имеет уникальную типизацию, которая используется как альтернатива Monads (более конкретно, монада IO). Уникальность ввода также делает интересный материал для работы с массивами.

2018-12-11T00:00Z

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

• Липский диалект для кода-данных-данных / гомоконичности и потому что они являются хорошими, если не лучшими, примерами динамических (более или менее строгих) языков функционального программирования
• Пролог как преобладающий логический язык программирования
• Smalltalk как единственный истинный язык ООП (также интересный из-за его обычно чрезвычайно ориентированного на изображение подхода)
• возможно, Erlang или Clojure, если вас интересуют языки, выкованные для параллельного / параллельного / распределенного программирования
• Форвард для программирования, ориентированного на стек
• (Haskell для строгого функционального статически типизированного ленивого программирования)

Особенно Lisps (CL не так много, как Scheme) и Prolog (и Haskell) охватывают рекурсию.

Хотя я не гуру ни на одном из этих языков, я провел некоторое время с каждым из них, кроме Эрланг и Форта, и все они дали мне открывающиеся и интересные познавательные впечатления, поскольку каждый из них подходит к решению проблем под другим углом,

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

2018-12-18T00:00Z

С точки зрения того, что подходит вашему майору, очевидный выбор кажется логическим языком, таким как Prolog или его производные. Логическое программирование может быть сделано очень аккуратно на функциональном языке (см., Например, The Reasoned Schemer), но вам может понравиться работать с логической парадигмой напрямую.

Интерактивная теоретическая система доказательства, такая как twelf или coq, может также поразить вашу фантазию.

2018-12-25T00:00Z

Я хотел бы расширить свои знания в области программирования. (...) Я думал, что поставил бы здесь вопрос, а также несколько положений о типе языка, который я ищу. Некоторые из них субъективны, некоторые из них предназначены для облегчения перехода от Haskell.

Сильная система типов. (...) Он также делает неформальные рассуждения о правильности моей программы более легкими. Меня беспокоит правильность, а не эффективность.

Акцент на рекурсии, а не на итерации. (...)

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

Не обращайте внимания на практичность и отправляйтесь на «больше Haskell, чем Haskell» : система типа Haskell полна дыр, из-за прекращения и других беспорядочных компромиссов. Очистите беспорядок и добавьте более мощные функции, и вы получите такие языки, как Coq и Agda , где тип функции содержит доказательство ее правильности (вы можете даже читать функцию arrow -> как логическую импликацию!). Эти языки использовались для математических доказательств и для программ с чрезвычайно высокими требованиями к правильности. Coq, вероятно, является самым выдающимся языком стиля, но у Agda больше чувство Haskell-y (а также написано в Haskell).

Не учитывайте типы, добавляйте больше магии : если Haskell - колдовство, Lisp - это сырая первобытная магия творения. Языки семейства Lisp (включая Scheme and Clojure ) обладают почти беспрецедентной гибкостью в сочетании с экстремальным минимализмом. Языки по существу не имеют синтаксиса, написание кода непосредственно в виде структуры данных дерева; метапрограммирование в Lisp проще, чем не-мета-программирование на некоторых языках.

Компромисс немного и приближайтесь к мейнстриму : Haskell попадает в широкую семью языков, сильно влияющих на ML, любой из которых вы, вероятно, могли бы перейти без особых трудностей. Haskell является одним из самых строгих, когда речь заходит о гарантиях правильности от типов и использования функционального стиля, где другие часто являются либо гибридными стилями, либо / или делают прагматические компромиссы по разным причинам. Если вы хотите подвергнуть ООП и доступ к множеству основных технологических платформ, либо Scala на JVM, либо F # на.NET имеет много общего с Haskell, обеспечивая легкую совместимость с платформами Java и.NET. F # поддерживается непосредственно Microsoft, но имеет некоторые досадные ограничения по сравнению с Haskell и проблемами переносимости на платформах, отличных от Windows. У Scala есть прямые аналоги с системой типов Haskell и кросс-платформенным потенциалом Java, но она имеет более тяжелый синтаксис и не обладает мощной поддержкой сторонних разработчиков, которой пользуется F #.