Как создать простой проект
В каталоге проектов набираем (name это имя проекта)
Для создания проекта можно использовать схему simple - она создаёт меньше файлов в проекте.
Сборка
После этого внутри каталога .stack-work появиться исполняемый файл, его можно запустить так
Форматировать (отступы и всякое такое) файл
Установить форматтер можно командой:
Форматировать каталог
В каталоге проектов набираем (name это имя проекта)
stack new name
Для создания проекта можно использовать схему simple - она создаёт меньше файлов в проекте.
stack new name simple
Сборка
stack build
После этого внутри каталога .stack-work появиться исполняемый файл, его можно запустить так
stack exec name
Форматировать (отступы и всякое такое) файл
fourmolu -i Module.hs
Установить форматтер можно командой:
stack install fourmolu
Форматировать каталог
fourmolu -i src
Что такое функция?
В языке Haskell функция — это основная единица вычисления и центральный элемент языка. Это чистое, математическое отображение входных значений в выходные, без побочных эффектов, и с мощной поддержкой композиции, полиморфизма и каррирования.
Функции в Haskell следуют трём обязательным правилам:
1. все функции должны принимать аргументы,
2. все функции должны возвращать значение,
3. функция возвращает один и тот же результат для одного и того же набора аргументов (чистота, ссылочная прозрачность).
Функции в Haskell не могут иметь побочных эффектов (на самом деле могут, но это нужно специально указывать).
Функции в Haskell — это значения, как числа или строки. Их можно:
- Передавать как аргументы другим функциям.
- Возвращать из функций.
- Присваивать переменным.
- Хранить в структурах данных.
В Haskell все функции по умолчанию каррированы — то есть функция от нескольких аргументов на самом деле является функцией от одного аргумента, возвращающей другую функцию.
Примеры функций
Простая функция:
Функция высшего порядка (принимает другую функцию):
Рекурсивная функция:
В языке Haskell функция — это основная единица вычисления и центральный элемент языка. Это чистое, математическое отображение входных значений в выходные, без побочных эффектов, и с мощной поддержкой композиции, полиморфизма и каррирования.
Функции в Haskell следуют трём обязательным правилам:
1. все функции должны принимать аргументы,
2. все функции должны возвращать значение,
3. функция возвращает один и тот же результат для одного и того же набора аргументов (чистота, ссылочная прозрачность).
Функции в Haskell не могут иметь побочных эффектов (на самом деле могут, но это нужно специально указывать).
Функции в Haskell — это значения, как числа или строки. Их можно:
- Передавать как аргументы другим функциям.
- Возвращать из функций.
- Присваивать переменным.
- Хранить в структурах данных.
В Haskell все функции по умолчанию каррированы — то есть функция от нескольких аргументов на самом деле является функцией от одного аргумента, возвращающей другую функцию.
Примеры функций
Простая функция:
square :: Int -> Int
square x = x * x
Функция высшего порядка (принимает другую функцию):
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
Рекурсивная функция:
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)
Алонзо Чёрч (Alonzo Church, 14 июня 1903 — 11 августа 1995) — выдающийся американский математик и логик, один из основоположников теоретической информатики и математической логики. Оказал огромное влияние не только на математику и логику, но и на зарождение информатики как науки.
Лямбда-исчисление
В 1930-х годах Чёрч разработал лямбда-исчисление — формальную систему для описания функций и вычислений. Эта система стала фундаментом для функционального программирования и повлияла на развитие многих языков программирования, таких как Lisp, Haskell, ML и другие.
Тезис Чёрча — Тьюринга
Вместе с Аланом Тьюрингом он сформулировал тезис Чёрча — Тьюринга, утверждающий, что любая функция, которую можно "вычислить алгоритмически", может быть вычислена либо с помощью машины Тьюринга, либо в рамках лямбда-исчисления. Этот тезис лёг в основу теории вычислимости.
Теорема Чёрча о неразрешимости
В 1936 году он доказал, что проблема разрешения (Entscheidungsproblem) — задача определения истинности любого логического утверждения в рамках формальной системы — неразрешима. Это было сделано независимо и почти одновременно с Тьюрингом.
Логика и философия
Чёрч внёс значительный вклад в интенсиональную логику и разработал так называемую "теорию типов Чёрча", а также занимался философскими вопросами смысла и референции.
Лямбда-исчисление
В 1930-х годах Чёрч разработал лямбда-исчисление — формальную систему для описания функций и вычислений. Эта система стала фундаментом для функционального программирования и повлияла на развитие многих языков программирования, таких как Lisp, Haskell, ML и другие.
Тезис Чёрча — Тьюринга
Вместе с Аланом Тьюрингом он сформулировал тезис Чёрча — Тьюринга, утверждающий, что любая функция, которую можно "вычислить алгоритмически", может быть вычислена либо с помощью машины Тьюринга, либо в рамках лямбда-исчисления. Этот тезис лёг в основу теории вычислимости.
Теорема Чёрча о неразрешимости
В 1936 году он доказал, что проблема разрешения (Entscheidungsproblem) — задача определения истинности любого логического утверждения в рамках формальной системы — неразрешима. Это было сделано независимо и почти одновременно с Тьюрингом.
Логика и философия
Чёрч внёс значительный вклад в интенсиональную логику и разработал так называемую "теорию типов Чёрча", а также занимался философскими вопросами смысла и референции.
Как создать простой проект шаг за шагом
В каталоге проектов набираем
это создаст каталог шаблона простого проекта. Заглянем внутрь:
Нас интересует файл
Внутри там написан простой
Соберём ...
... и запустим его
Далее в файле
В каталоге проектов набираем
stack new firstpro simple
это создаст каталог шаблона простого проекта. Заглянем внутрь:
|- src
|- - Main.hs
|- CHANGELOG.md
|- LICENSE
|- README.md
|- Setup.hs
|- firstpro.cabal
|- stack.yaml
Нас интересует файл
Main.hs - это отправная точка для работы нашего проекта.Внутри там написан простой
hello worldmodule Main (main) where
main :: IO ()
main = do
putStrLn "hello world"
Соберём ...
stack build
... и запустим его
stack exec firstpro
Далее в файле
Main.hs можно добавлять свои функции, добавлять свои модули в проект, но это уже совсем другая история.👍1
Haskell Playground
Что делать, если нет возможности или желания ставить haskell на комп, но нужно что-то попрогать? Для этого есть онлайн песочницы.
Для haskell это https://play.haskell.org/
Как и многие подобные платформы она позволяет выбрать версию компилятора и уровень оптимизации, посмотреть ассемблерный код и код, транслируемый в haskell core (это внутренний язык компилятора GHC).
Что делать, если нет возможности или желания ставить haskell на комп, но нужно что-то попрогать? Для этого есть онлайн песочницы.
Для haskell это https://play.haskell.org/
Как и многие подобные платформы она позволяет выбрать версию компилятора и уровень оптимизации, посмотреть ассемблерный код и код, транслируемый в haskell core (это внутренний язык компилятора GHC).
Haskell Core
Это внутренний язык компилятора GHC (Glasgow Haskell Compiler) языка Haskell. Он представляет собой расширение системы полиморфного λ-исчисления высших порядков System Fω.
Core используется для трансляции кода на Haskell в промежуточное представление, которое упрощает анализ программ и оптимизацию.
Код на Haskell транслируется в Core во время компиляции. Это происходит с помощью дешугаринга (убираем синтаксический сахар) — перевода программы, которая использует многие конструкции языка, в программу, использующую только несколько.
Core имеет гораздо меньше синтаксических форм по сравнению с исходным языком Haskell.
Некоторые особенности Core:
- Привязки функций — всегда имеют одно имя переменной в левой части, преобразуются в лямбды.
- Многоаргументные функции — переводятся во вложенные лямбды, в Core все лямбды — одноаргументные.
- Полиморфные функции — в Core нужно указывать аргументы типов, в исходном Haskell — только аргументы значений.
- Конструкторы данных — например, при построении кортежа из трёх элементов в Core передаются шесть аргументов: сначала типы элементов, затем элементы.
Это внутренний язык компилятора GHC (Glasgow Haskell Compiler) языка Haskell. Он представляет собой расширение системы полиморфного λ-исчисления высших порядков System Fω.
Core используется для трансляции кода на Haskell в промежуточное представление, которое упрощает анализ программ и оптимизацию.
Код на Haskell транслируется в Core во время компиляции. Это происходит с помощью дешугаринга (убираем синтаксический сахар) — перевода программы, которая использует многие конструкции языка, в программу, использующую только несколько.
Core имеет гораздо меньше синтаксических форм по сравнению с исходным языком Haskell.
Некоторые особенности Core:
- Привязки функций — всегда имеют одно имя переменной в левой части, преобразуются в лямбды.
- Многоаргументные функции — переводятся во вложенные лямбды, в Core все лямбды — одноаргументные.
- Полиморфные функции — в Core нужно указывать аргументы типов, в исходном Haskell — только аргументы значений.
- Конструкторы данных — например, при построении кортежа из трёх элементов в Core передаются шесть аргументов: сначала типы элементов, затем элементы.
Переменные
Математические аналогии в Haskell не заканчиваются на функциях. В Haskell не переменные, а объявления, или константные переменные, если брать аналогию из других языков.
Например, записать где-то
не получится, компилятор откажется такое компилировать.
Если рассматривать переменные, как естественный способ упрощения записи вычислений, то Haskell предлагает 2 варианта, которые можно комбинировать - блоки let и where:
или
такая запись больше походит на определение математической формулы и привычнее для использования в академических задачах.
Математические аналогии в Haskell не заканчиваются на функциях. В Haskell не переменные, а объявления, или константные переменные, если брать аналогию из других языков.
Например, записать где-то
x = 3
...
x = 5
не получится, компилятор откажется такое компилировать.
Если рассматривать переменные, как естественный способ упрощения записи вычислений, то Haskell предлагает 2 варианта, которые можно комбинировать - блоки let и where:
calcChange :: Int -> Int -> Int
calcChange owed given =
let change = given - owed
in
if change > 0
then change
else 0
или
calcChange :: Int -> Int -> Int
calcChange owed given = if change > 0
then change
else 0
where change = given - owed
такая запись больше походит на определение математической формулы и привычнее для использования в академических задачах.
🔥1
GHCI
GHCi — это интерактивная среда (REPL — Read-Eval-Print Loop) для языка программирования Haskell, входящая в состав компилятора GHC (Glasgow Haskell Compiler).
Основные функции GHCi
- Выполнение Haskell-выражений в реальном времени;
- Можно вводить выражения, функции, определения и сразу видеть результат;
- Загрузка и тестирование модулей;
- Можно загрузить .hs-файлы (например,
- Отладка и инспекция типов. GHCi позволяет проверять типы выражений с помощью команды
Когда GHCi особенно полезен
- изучение Haskell;
- быстрое прототипирование кода;
- тестирование функций без компиляции всего проекта.
Полезные команды
Пример использование GHCI
Запускаем интерпретатор командой
и далее пишем что хотим
GHCi — это интерактивная среда (REPL — Read-Eval-Print Loop) для языка программирования Haskell, входящая в состав компилятора GHC (Glasgow Haskell Compiler).
Основные функции GHCi
- Выполнение Haskell-выражений в реальном времени;
- Можно вводить выражения, функции, определения и сразу видеть результат;
- Загрузка и тестирование модулей;
- Можно загрузить .hs-файлы (например,
:load MyModule.hs) и работать с их содержимым;- Отладка и инспекция типов. GHCi позволяет проверять типы выражений с помощью команды
:type (сокращённо :t).Когда GHCi особенно полезен
- изучение Haskell;
- быстрое прототипирование кода;
- тестирование функций без компиляции всего проекта.
Полезные команды
:load / :l - загрузить файл:reload / :r - перезагрузить текущий файл:type / :t - показать тип выражения:info / :i - информация о функции, типе или классе типов:help / :? - справка по командам:quit / :q - выйти из GHCi:set +t - После выполнения команды интерпретатор будет выводить на экран не только результат вычисления выражения, но и его тип.:set +s - После выполнения команды интерпретатор будет выводить на экран не только результат вычисления выражения, но и статистику вычислений.Пример использование GHCI
Запускаем интерпретатор командой
ghci
и далее пишем что хотим
ghci> let factorial 0 = 1; factorial n = n * factorial (n - 1)
ghci> factorial 5
120
ghci> :t factorial
factorial :: (Eq p, Num p) => p -> p
Такое разное ветвление
В языке
Условный оператор if
отличается от аналогов в императивных языках тем, что он является выражением, а не управляющей конструкцией.
Это означает, что:
-
-
- обе ветки (
Пример:
Охраняющие (или охранные) выражения (guards)
это удобный и читаемый способ определения функций с несколькими условиями. Они особенно полезны, когда нужно проверить несколько логических условий (например, в зависимости от значений аргументов), и выглядят гораздо элегантнее вложенных
При этом:
- Все ветки (результаты) должны иметь один и тот же тип.
- Если ни одно условие не выполнено и нет
Пример:
Сопоставление с образцом (pattern matching)
одна из самых мощных и характерных черт языка Haskell. Оно позволяет разбирать структуры данных (списки, кортежи, пользовательские типы и т.д.) прямо в определении функций, присваиваниях или ветвлениях, проверяя их форму и извлекая значения.
При этом:
- Порядок важен: сопоставление проверяется сверху вниз.
- Образцы должны быть исчерпывающими: если возможен случай, не охваченный ни одним паттерном, компилятор выдаст предупреждение (или ошибка, если включён
- Нельзя использовать произвольные функции в образцах - только конструкторы данных, константы и переменные.
Пример:
В языке
haskell существует несколько способов поменять линейный ход выполнения программы.Условный оператор if
отличается от аналогов в императивных языках тем, что он является выражением, а не управляющей конструкцией.
Это означает, что:
-
if всегда должен иметь и then, и else;-
if ... then ... else ... возвращает значение, которое можно использовать, например, присвоить переменной или передать в функцию;- обе ветки (
then и else) должны иметь один и тот же тип.Пример:
signum' :: Int -> Int
signum' x = if x > 0
then 1
else if x < 0
then -1
else 0
Охраняющие (или охранные) выражения (guards)
это удобный и читаемый способ определения функций с несколькими условиями. Они особенно полезны, когда нужно проверить несколько логических условий (например, в зависимости от значений аргументов), и выглядят гораздо элегантнее вложенных
if-then-else.При этом:
- Все ветки (результаты) должны иметь один и тот же тип.
- Если ни одно условие не выполнено и нет
otherwise - функция завершится исключением (ошибка времени выполнения). Поэтому почти всегда следует добавлять otherwise в конец.Пример:
signum'' :: Int -> Int
signum'' x
| x > 0 = 1
| x < 0 = -1
| otherwise = 0
Сопоставление с образцом (pattern matching)
одна из самых мощных и характерных черт языка Haskell. Оно позволяет разбирать структуры данных (списки, кортежи, пользовательские типы и т.д.) прямо в определении функций, присваиваниях или ветвлениях, проверяя их форму и извлекая значения.
При этом:
- Порядок важен: сопоставление проверяется сверху вниз.
- Образцы должны быть исчерпывающими: если возможен случай, не охваченный ни одним паттерном, компилятор выдаст предупреждение (или ошибка, если включён
-Werror).- Нельзя использовать произвольные функции в образцах - только конструкторы данных, константы и переменные.
Пример:
isEmpty :: [a] -> Bool
isEmpty [] = True
isEmpty _ = False
👍2
Лямбда-исчисление
Это формальная система в математической логике и теоретической информатике, предназначенная для описания вычислений с помощью функций. Оно было разработано в 1930-х годах Алонзо Чёрчем как способ формализовать понятие вычислимой функции и лежит в основе функционального программирования.
Основные идеи
1. Всё - это функция. В лямбда-исчислении нет чисел, строк или других типов данных в привычном смысле. Всё представляется как функции. Даже числа, логические значения и операции над ними кодируются с помощью функций (например, через кодировку Чёрча).
2. Лямбда-выражения - это основные "строительные блоки" системы. Есть три типа выражений:
- Переменные: например, x, y.
- Абстракции (определения функции): записываются как
- Аппликации (применение функции): записывается как
3. β-редукция - основное правило вычисления. Это процесс подстановки аргумента в тело функции:
То есть, функция
4. α-конверсия - переименование связанных переменных. Например,
5. η-эквивалентность - принцип расширяемости. Говорит, что если две функции ведут себя одинаково на всех аргументах, то они эквивалентны:
Значение лямбда-исчисления
Теоретическое:
- Эквивалентно машине Тьюринга по вычислительной мощности (тезис Чёрча–Тьюринга).
- Лежит в основе теории типов, формальных языков и логики.
Практическое:
- Влияние на функциональные языки программирования: Haskell, Lisp, ML, Scheme, Scala, F# и др.
- Концепция анонимных функций (лямбда-выражений) в современных языках (Python, JavaScript, Java и др.) идёт именно отсюда.
Типизированное и нетипизированное λ-исчисление
- Нетипизированное - самый простой и выразительный вариант, но в нём возможны "странные" выражения, не имеющие нормальной формы (например, (λx.x x)(λx.x x) - зацикливается).
- Типизированное - каждое выражение имеет тип, что исключает некоторые виды ошибок и делает систему безопасной (например, простое типизированное λ-исчисление, система F, исчисление конструкций и т.д.).
Это формальная система в математической логике и теоретической информатике, предназначенная для описания вычислений с помощью функций. Оно было разработано в 1930-х годах Алонзо Чёрчем как способ формализовать понятие вычислимой функции и лежит в основе функционального программирования.
Основные идеи
1. Всё - это функция. В лямбда-исчислении нет чисел, строк или других типов данных в привычном смысле. Всё представляется как функции. Даже числа, логические значения и операции над ними кодируются с помощью функций (например, через кодировку Чёрча).
2. Лямбда-выражения - это основные "строительные блоки" системы. Есть три типа выражений:
- Переменные: например, x, y.
- Абстракции (определения функции): записываются как
λx.M, что означает "функция от аргумента x, возвращающая выражение M".- Аппликации (применение функции): записывается как
(M N), что означает "применить функцию M к аргументу N".3. β-редукция - основное правило вычисления. Это процесс подстановки аргумента в тело функции:
(λx.M) N → M[x := N]
То есть, функция
λx.M применяется к N, и все вхождения x в M заменяются на N.4. α-конверсия - переименование связанных переменных. Например,
λx.x и λy.y считаются эквивалентными, потому что имена связанных переменных не важны.5. η-эквивалентность - принцип расширяемости. Говорит, что если две функции ведут себя одинаково на всех аргументах, то они эквивалентны:
λx.(f x) ≡ f, если x не свободен в f
Значение лямбда-исчисления
Теоретическое:
- Эквивалентно машине Тьюринга по вычислительной мощности (тезис Чёрча–Тьюринга).
- Лежит в основе теории типов, формальных языков и логики.
Практическое:
- Влияние на функциональные языки программирования: Haskell, Lisp, ML, Scheme, Scala, F# и др.
- Концепция анонимных функций (лямбда-выражений) в современных языках (Python, JavaScript, Java и др.) идёт именно отсюда.
Типизированное и нетипизированное λ-исчисление
- Нетипизированное - самый простой и выразительный вариант, но в нём возможны "странные" выражения, не имеющие нормальной формы (например, (λx.x x)(λx.x x) - зацикливается).
- Типизированное - каждое выражение имеет тип, что исключает некоторые виды ошибок и делает систему безопасной (например, простое типизированное λ-исчисление, система F, исчисление конструкций и т.д.).
👍1
Лямбда-функции в Haskell
это функция без имени, которая создаётся на месте и может быть передана в качестве аргумента или использована в выражении. В Haskell синтаксис лямбда-функций основан на лямбда-исчислении, где
Haskell — один из самых чистых функциональных языков, и его дизайн во многом основан на лямбда-исчислении, что делает лямбда-функции естественной частью языка.
Лямбда-функции так же являются значениями и при именовании они становятся эквивалентны обычным функциям:
Внутренне Haskell воспринимает все функции как лямбда-выражения.
Синтаксис
-
-
-
-
Когда использовать лямбда-функции?
Рекомендуется использовать, когда:
- Функция короткая и используется однажды.
- Она передаётся в функцию высшего порядка (например, map, filter, foldr).
- Нужно захватить переменные из окружения (замыкание).
Не рекомендуется, если:
- Лямбда-функция слишком сложная.
- Она используется несколько раз — лучше дать ей имя.
- Код становится менее читаемым.
Примеры
это функция без имени, которая создаётся на месте и может быть передана в качестве аргумента или использована в выражении. В Haskell синтаксис лямбда-функций основан на лямбда-исчислении, где
λ обозначается как \. Haskell — один из самых чистых функциональных языков, и его дизайн во многом основан на лямбда-исчислении, что делает лямбда-функции естественной частью языка.
Лямбда-функции так же являются значениями и при именовании они становятся эквивалентны обычным функциям:
-- Лямбда-функция
addOne = \x -> x + 1
-- То же самое как именованная функция
addOne x = x + 1
Внутренне Haskell воспринимает все функции как лямбда-выражения.
Синтаксис
\аргументы -> выражение
-
\ — начало лямбда-выражения (напоминает греческую букву λ).-
аргументы — список параметров функции (через пробел).-
-> — стрелка, обозначающая тело функции.-
выражение — то, что возвращает функция.Когда использовать лямбда-функции?
Рекомендуется использовать, когда:
- Функция короткая и используется однажды.
- Она передаётся в функцию высшего порядка (например, map, filter, foldr).
- Нужно захватить переменные из окружения (замыкание).
Не рекомендуется, если:
- Лямбда-функция слишком сложная.
- Она используется несколько раз — лучше дать ей имя.
- Код становится менее читаемым.
Примеры
Prelude> (\x -> x + 1) 3
4
Prelude> (\x -> x ++ "!") "Hello"
"Hello!"
Prelude> map (\x -> x ^ 2) [1..5]
[1,4,9,16,25]
Prelude> filter (\(a, b) -> a > b) [(1,2), (3,2), (4,4), (5,3)]
[(3,2),(5,3)]
Хаскелл Брукс Карри
американский математик и логик, чьи работы оказали огромное влияние на развитие математической логики, теории вычислений и функционального программирования.
Хотя Карри не был первым, кто открыл идею, названную его именем, именно его систематическая работа привлекла к ней широкое внимание.
Результатами его работы являются:
1. Каррирование (Currying). Это преобразование функции от нескольких аргументов в последовательность функций от одного аргумента. Например, функция f(x, y) преобразуется в g(x)(y). Хотя идея восходит к Мозесу Шёнфинку и Готтлобу Фреге, именно Карри глубоко исследовал её в контексте комбинаторной логики - поэтому процесс получил его имя.
2. Комбинаторная логика. Карри развил комбинаторную логику - систему, в которой функции строятся без переменных, с использованием базовых "комбинаторов" (например, S, K, I). Эта система стала альтернативой лямбда-исчислению и важной вехой в теории вычислимости.
3. Парадокс Карри. Выявил логический парадокс (называемый парадоксом Карри), показывающий, что в некоторых системах логики можно вывести любое утверждение из самоссылающегося высказывания вида:
Это важный вклад в понимание ограничений формальных систем.
Почему язык программирования называется Haskell?
Язык программирования Haskell (созданный в 1990 году) назван именно в честь Хаскелла Карри - как дань уважения его вкладу в основы функционального программирования, особенно:
- лямбда-исчисление,
- каррирование,
- теорию типов.
Интересный факт: сам Карри не работал с компьютерами - он был чистым математиком и логиком. Но его идеи стали фундаментом для функциональных языков, включая Haskell, ML, Lisp и другие.
Хаскелл Карри - один из отцов современной логики и теоретической информатики. Его имя носит:
- Процесс каррирования (currying),
- Язык программирования Haskell,
- Парадокс Карри,
- Единица измерения "карри" в шуточной академической культуре (для "логической выразительности").
американский математик и логик, чьи работы оказали огромное влияние на развитие математической логики, теории вычислений и функционального программирования.
«Logic is the anatomy of thought.»
Хотя Карри не был первым, кто открыл идею, названную его именем, именно его систематическая работа привлекла к ней широкое внимание.
Результатами его работы являются:
1. Каррирование (Currying). Это преобразование функции от нескольких аргументов в последовательность функций от одного аргумента. Например, функция f(x, y) преобразуется в g(x)(y). Хотя идея восходит к Мозесу Шёнфинку и Готтлобу Фреге, именно Карри глубоко исследовал её в контексте комбинаторной логики - поэтому процесс получил его имя.
2. Комбинаторная логика. Карри развил комбинаторную логику - систему, в которой функции строятся без переменных, с использованием базовых "комбинаторов" (например, S, K, I). Эта система стала альтернативой лямбда-исчислению и важной вехой в теории вычислимости.
3. Парадокс Карри. Выявил логический парадокс (называемый парадоксом Карри), показывающий, что в некоторых системах логики можно вывести любое утверждение из самоссылающегося высказывания вида:
«Если это утверждение истинно, то 1 = 2».
Это важный вклад в понимание ограничений формальных систем.
Почему язык программирования называется Haskell?
Язык программирования Haskell (созданный в 1990 году) назван именно в честь Хаскелла Карри - как дань уважения его вкладу в основы функционального программирования, особенно:
- лямбда-исчисление,
- каррирование,
- теорию типов.
Интересный факт: сам Карри не работал с компьютерами - он был чистым математиком и логиком. Но его идеи стали фундаментом для функциональных языков, включая Haskell, ML, Lisp и другие.
Хаскелл Карри - один из отцов современной логики и теоретической информатики. Его имя носит:
- Процесс каррирования (currying),
- Язык программирования Haskell,
- Парадокс Карри,
- Единица измерения "карри" в шуточной академической культуре (для "логической выразительности").
Функции как значения первого класса
Функции в haskell выступают как полноценные значения, которые можно передавать как аргумент в другие функции, возвращать из функций, присваивать переменным.
Функции как аргументы
Передача функций как аргументов позволяет обобщить процесс повторяющихся вычислений.
Допустим у нас есть функция
Если позже нам понадобятся функции ifEvenDouble и ifEvenSquare, то мы будем вынуждены дублировать условие, а когда оно измениться, то переписывать синхронно все эти функции.
НО можно параметризовать функцию
Не стоит забывать, что лямбда-функции - это полноценные функции и их так же можно передавать как значение.
Наиболее частым примером такого использования функций, не только в haskell, но и в других языках, является сортировка пользовательских типов сортировкой из стандартной библиотеки. Например
Функции как результат
В haskell все функции принимают ровно один аргумент и возвращают одно значение - которое может быть другой функцией. Это называется каррированием, и это фундаментальный принцип функционального программирования - если функция принимает несколько аргументов, она на самом деле возвращает функцию на каждом шаге.
Даже в простом примере:
Тип Int -> Int -> Int на самом деле означает Int -> (Int -> Int) — то есть add принимает Int и возвращает функцию Int -> Int.
Функции можно возвращать и явно. Например, можно изменить нашу функцию
Функции в haskell выступают как полноценные значения, которые можно передавать как аргумент в другие функции, возвращать из функций, присваивать переменным.
Функции как аргументы
Передача функций как аргументов позволяет обобщить процесс повторяющихся вычислений.
Допустим у нас есть функция
ifEvenInc, которая увеличивает число n на единицу, если оно чётное, оставляя его неизменным в противном случае:module Main (main) where
ifEvenInc :: Int -> Int
ifEvenInc n = if even n
then n+1
else n
main :: IO ()
main = do
putStrLn $ show $ ifEvenInc 20
Если позже нам понадобятся функции ifEvenDouble и ifEvenSquare, то мы будем вынуждены дублировать условие, а когда оно измениться, то переписывать синхронно все эти функции.
НО можно параметризовать функцию
ifEven..., передав ей в качестве аргумента функцию-модификатор для x.module Main (main) where
ifEven :: (Int -> Int) -> Int -> Int
ifEven func x = if even x
then func x
else x
ifEvenInc :: Int -> Int
ifEvenInc n = ifEven (\x -> x+1) n
main :: IO ()
main = do
putStrLn $ show $ ifEvenInc 20
Не стоит забывать, что лямбда-функции - это полноценные функции и их так же можно передавать как значение.
Наиболее частым примером такого использования функций, не только в haskell, но и в других языках, является сортировка пользовательских типов сортировкой из стандартной библиотеки. Например
sortBy или std::sort (в C++).Функции как результат
В haskell все функции принимают ровно один аргумент и возвращают одно значение - которое может быть другой функцией. Это называется каррированием, и это фундаментальный принцип функционального программирования - если функция принимает несколько аргументов, она на самом деле возвращает функцию на каждом шаге.
Даже в простом примере:
add :: Int -> Int -> Int
add x y = x + y
Тип Int -> Int -> Int на самом деле означает Int -> (Int -> Int) — то есть add принимает Int и возвращает функцию Int -> Int.
Функции можно возвращать и явно. Например, можно изменить нашу функцию
ifEven. Если она принимает четный первый аргумент, то будет возвращена функция, которая увеличивает свой аргумент на 1, иначе - функция, которая увеличивает свой аргумент в 2 раза:module Main (main) where
ifEven :: Int -> (Int -> Int)
ifEven x = if even x
then (\a -> a+1)
else (\b -> b*2)
main :: IO ()
main = do
let func = ifEven 21
putStrLn $ show $ func 3
❤1
Замыкание
Концепция замыкания довольно простая - когда лямбда-функция захватывает некоторое значение из внешней области видимости, то это называется замыкание.
Например:
тут
Замыкания в Haskell захватывают значения, а не ссылки на изменяемую память, и поскольку значения неизменны, разницы между «по значению» и «по ссылке» в привычном смысле не существует. Но стоит отметить, что haskell может делить (share) подвыражения в памяти - то есть, если замыкание захватывает большое значение, оно не обязательно копируется полностью, а может ссылаться на уже существующую структуру в памяти. Но это оптимизация реализации, а не семантика: с точки зрения программы, это всё равно «значение», и оно неизменно.
Концепция замыкания довольно простая - когда лямбда-функция захватывает некоторое значение из внешней области видимости, то это называется замыкание.
Например:
genIfEven f = (\x -> ifEven f x)
тут
f - захватывается лямбда-функцией.Замыкания в Haskell захватывают значения, а не ссылки на изменяемую память, и поскольку значения неизменны, разницы между «по значению» и «по ссылке» в привычном смысле не существует. Но стоит отметить, что haskell может делить (share) подвыражения в памяти - то есть, если замыкание захватывает большое значение, оно не обязательно копируется полностью, а может ссылаться на уже существующую структуру в памяти. Но это оптимизация реализации, а не семантика: с точки зрения программы, это всё равно «значение», и оно неизменно.
Частичное применение
Это мощный механизм, который позволяет зафиксировать значения некоторых аргументов функции и на её основе получить функцию с меньшим количеством аргументов.
Например у нас есть функция
В языке haskell существует полезная практика
Это связано именно с использованием частичного применения и позволяет делать его более выразительным. Если же, вдруг, нужно частично применить второй аргумент, а не первый, то можно воспользоваться стандартной функцией
Не трудно написать свой аналог
Не стоит путать частичное применение с каррированием — это связанная, но другая концепция:
- каррирование — это преобразование функции от нескольких аргументов в цепочку функций от одного аргумента.
- частичное применение — это процесс применения функции к части её аргументов, чтобы получить новую функцию. Но в Haskell все функции изначально каррированы, поэтому частичное применение работает «из коробки».
Это мощный механизм, который позволяет зафиксировать значения некоторых аргументов функции и на её основе получить функцию с меньшим количеством аргументов.
Например у нас есть функция
add которая складывает два числа. На её основе можно создать функцию increment, которая выполняет увеличение аргумента на 1.add :: Int -> Int -> Int
add x y = x + y
increment :: Int -> Int
increment = add 1
В языке haskell существует полезная практика
"Всякий раз, когда вы хотите использовать замыкание, нужно располагать аргументы функции в порядке от наиболее общего к наименее общему".
Это связано именно с использованием частичного применения и позволяет делать его более выразительным. Если же, вдруг, нужно частично применить второй аргумент, а не первый, то можно воспользоваться стандартной функцией
flip - она меняет местами аргументы у функции с двумя аргументами:flip :: (a -> b -> c) -> b -> a -> c
Не трудно написать свой аналог
flip для замены 3 и 4, 4 и 5 или еще полного порядка аргументов. Однако, такое легаси довольно поддерживать. Не стоит путать частичное применение с каррированием — это связанная, но другая концепция:
- каррирование — это преобразование функции от нескольких аргументов в цепочку функций от одного аргумента.
- частичное применение — это процесс применения функции к части её аргументов, чтобы получить новую функцию. Но в Haskell все функции изначально каррированы, поэтому частичное применение работает «из коробки».
Списки
Списки это очень важная структура данных в функциональном программировании. Определение списка является рекурсивным - это или пустой список, или элемент, за которым следует список. Список разделяется на два элемента - голова (
Все элементы списка должны быть одного типа.
Примеры списков:
Строки в haskell это тоже списки символов.
Перечисления
Списки можно создавать с помощь перечисления
Списки в Haskell ленивы, т.е. элементы вычисляются только тогда, когда они нужны. Это позволяет работать с бесконечными списками:
Функции для работы со списками
head - возвращает голову списка
tail - формирует другой список, представляющий собою всё от первоначального списка, кроме головы
last - получить последний элемент
init - вернёт всё кроме последнего элемента
length - возвращает длину списка
null - проверка на пустоту
reverse - обращает список
take N [lst] - отбирает N элементов из списка
drop N [lst] - вырезает N элементов из списка
X 'elem' [lst] - проверяет, входит ли элемент в список
!! - взять элемент по индексу
take N - возвращает N первых элементов списка
[2,4 ..] - бесконечный список чётных чисел
cycle [] - зацикливает список в бесконечный
repeat X - делает бесконечный список из X
zip - скомбинировать два списка в пары
++ - конкантенация списков
: - добавление в начало списка
Примеры:
Списки это очень важная структура данных в функциональном программировании. Определение списка является рекурсивным - это или пустой список, или элемент, за которым следует список. Список разделяется на два элемента - голова (
head) и хвост (tail). По умолчанию список всегда заканчивается пустым списком.Все элементы списка должны быть одного типа.
Примеры списков:
[1, 2, 3]
[1.3, 45.7899]
["TCP", "UDP", "DCCP", "SCTP"]
Строки в haskell это тоже списки символов.
GHCi>[’п’,’р’,’и’,’в’,’е’,’т’]
"привет"
GHCi> ’п’:’р’:’и’:’в’:’е’:’т’:[]
"привет"
Перечисления
Списки можно создавать с помощь перечисления
[1..10] = [1,2,3,4,5,6,7,8,9,10]
[2,4..10] = [2,4,6,8,10]
[9,8..1] = [9,8,7,6,5,4,3,2,1]
['a'..'z'] = "abcdefghijklmnopqrstuvwxyz"
Списки в Haskell ленивы, т.е. элементы вычисляются только тогда, когда они нужны. Это позволяет работать с бесконечными списками:
naturals = [1..] -- бесконечный список натуральных чисел
Функции для работы со списками
head - возвращает голову списка
tail - формирует другой список, представляющий собою всё от первоначального списка, кроме головы
last - получить последний элемент
init - вернёт всё кроме последнего элемента
length - возвращает длину списка
null - проверка на пустоту
reverse - обращает список
take N [lst] - отбирает N элементов из списка
drop N [lst] - вырезает N элементов из списка
X 'elem' [lst] - проверяет, входит ли элемент в список
!! - взять элемент по индексу
take N - возвращает N первых элементов списка
[2,4 ..] - бесконечный список чётных чисел
cycle [] - зацикливает список в бесконечный
repeat X - делает бесконечный список из X
zip - скомбинировать два списка в пары
++ - конкантенация списков
: - добавление в начало списка
Примеры:
GHCi> [1,2,3] !! 0
1
GHCi> length [(10,20),(1,2),(15,16)]
3
GHCi> zip "пёс" "кролик"
[(’п’,’к’),(’ё’,’р’),(’с’,’о’)]
Генераторы списков
Математические аналогии в haskell не заканчиваются на функциях. Замечательной возможностью этого языка является генерация списков.
Вот пример простого описания множества. Множество, состоящее из первых десяти чётных чисел, это
, где выражение перед символом
а
Это означает, что множество содержит удвоенные натуральные числа, которые удовлетворяют условию выборки.
Чтобы выразить это в языке haskell потребуется написать такое:
Тут мы извлекаем элементы из списка
В генераторы можно добавить условия выборки, они перечисляются после задания источника данных и отделяются запятыми.
Для удобства, выражение генератора можно поместить в функцию и вызывать её для разных интервалов.
Математические аналогии в haskell не заканчиваются на функциях. Замечательной возможностью этого языка является генерация списков.
Вот пример простого описания множества. Множество, состоящее из первых десяти чётных чисел, это
S = {x · 2 | x ∈ N, x<=10}, где выражение перед символом
| называется производящей функцией, x - переменная, N - входной набор,а
x ∈ 10 - условие выборки. Это означает, что множество содержит удвоенные натуральные числа, которые удовлетворяют условию выборки.
Чтобы выразить это в языке haskell потребуется написать такое:
ghci> [x*2 | x <– [1..10]]
[2,4,6,8,10,12,14,16,18,20]
Тут мы извлекаем элементы из списка
[1..10], т. е. x последовательно принимает все значения элементов списка. Иногда говорят, что x связывается с каждым элементом списка. Часть генератора, находящаяся левее вертикальной черты |, определяет значения элементов результирующего списка.В генераторы можно добавить условия выборки, они перечисляются после задания источника данных и отделяются запятыми.
-- только те элементы, которые, будучи удвоенными, больше либо равны 12.
ghci> [x*2 | x <– [1..10], x*2 >= 12]
[12,14,16,18,20]
-- все числа от 50 до 100, остаток от деления на 7 которых равен 3
ghci> [ x | x <– [50..100], x `mod` 7 == 3]
[52,59,66,73,80,87,94]
Для удобства, выражение генератора можно поместить в функцию и вызывать её для разных интервалов.
boomBangs xs = [if x < 10 then "БУМ!" else "БАХ!" | x <– xs, odd x]
...
boomBangs [7..13] -- ["БУМ!","БУМ!","БАХ!","БАХ!"]
Рекурсия
В функциональном программировании нет циклов. Это значит, что все итерационные задачи должны решаться через рекурсию. Для людей, которые уже имеют опыт работы с императивными языками, понятие рекурсии кажется сложным. Хотя почти все повторяющиеся действия в нашей жизни имеют рекурсивное описание.
Функция называется рекурсивной, если она вызывает саму себя в своём определении.
Главное правило при работе с рекурсивными алгоритмами - точно знать, когда нужно выходить из рекурсии (базовый случай).
Самыми распространёнными и заезженными примерами работы с рекурсией являются вычисление факториала и наибольшего общего делителя. Но в haskell рекурсия применяется еще, например, для работы со списками:
Оптимизация хвостовой рекурсии
Программисты не любят рекурсию еще за то, что она сильно расходует оперативку. При шаге рекурсивного алгоритма нужно запомнить стэк текущего вызова, чтобы раскрутить алгоритм обратно. Однако, если рекурсивный вызов является последней операцией в функции (хвостовая рекурсия) и в неё передаются все нужные данные как аргументы, то компилятор оптимизирует этот вызов и избежать роста стэка.
В функциональном программировании нет циклов. Это значит, что все итерационные задачи должны решаться через рекурсию. Для людей, которые уже имеют опыт работы с императивными языками, понятие рекурсии кажется сложным. Хотя почти все повторяющиеся действия в нашей жизни имеют рекурсивное описание.
Функция называется рекурсивной, если она вызывает саму себя в своём определении.
Главное правило при работе с рекурсивными алгоритмами - точно знать, когда нужно выходить из рекурсии (базовый случай).
Самыми распространёнными и заезженными примерами работы с рекурсией являются вычисление факториала и наибольшего общего делителя. Но в haskell рекурсия применяется еще, например, для работы со списками:
-- вычисление длины списка
length' :: [a] -> Int
length' [] = 0
length' (_:xs) = 1 + length' xs
-- сумма элементов списка
sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
Оптимизация хвостовой рекурсии
Программисты не любят рекурсию еще за то, что она сильно расходует оперативку. При шаге рекурсивного алгоритма нужно запомнить стэк текущего вызова, чтобы раскрутить алгоритм обратно. Однако, если рекурсивный вызов является последней операцией в функции (хвостовая рекурсия) и в неё передаются все нужные данные как аргументы, то компилятор оптимизирует этот вызов и избежать роста стэка.
Кортежи
Это упорядоченная коллекция фиксированного размера, содержащая элементы разных типов (в отличие от списков, которые однородны).
Кортежи обозначаются круглыми скобками, а их компоненты отделяются запятыми:
Кортежи хорошо подходят для возврата нескольких значений из функции и для временного объединения двух-трёх значений (аналог анонимной структуры).
Но стоит помнить, что кортежи - не замена алгебраическим типам (a.k.a. структуры), их использование может снижать читаемость и выразительность кода.
Важное
- Кортежи с разным количеством элементов — это разные типы. Например,
- Несмотря на то что есть списки с одним элементом, не бывает кортежей с одним компонентом.
Полезными функциями для работы с кортежами из двух элементов являются
Распаковка кортежей
Получить значение из кортежа в переменную можно с помощью сопоставления с образцом. В примере аргументом функции является кортеж
Это упорядоченная коллекция фиксированного размера, содержащая элементы разных типов (в отличие от списков, которые однородны).
Кортежи обозначаются круглыми скобками, а их компоненты отделяются запятыми:
ghci> (1, 3)
(1,3)
ghci> (50, 50.4, "привет", 'b')
(50,50.4,"привет",'b')
ghci> :t (50, 50.4, "привет", 'b')
(50, 50.4, "привет", 'b')
:: (Fractional b, Num a) => (a, b, String, Char)
Кортежи хорошо подходят для возврата нескольких значений из функции и для временного объединения двух-трёх значений (аналог анонимной структуры).
minMax :: [Int] -> (Int, Int)
minMax xs = (minimum xs, maximum xs)
Но стоит помнить, что кортежи - не замена алгебраическим типам (a.k.a. структуры), их использование может снижать читаемость и выразительность кода.
Важное
- Кортежи с разным количеством элементов — это разные типы. Например,
(Int, String) и (Int, String, Bool) несовместимы.- Несмотря на то что есть списки с одним элементом, не бывает кортежей с одним компонентом.
Полезными функциями для работы с кортежами из двух элементов являются
fst и snd, которые возвращают первый и второй элементы кортежа:ghci> fst ("Вау", False)
"Вау"
ghci> snd ("Вау", False)
FalseРаспаковка кортежей
Получить значение из кортежа в переменную можно с помощью сопоставления с образцом. В примере аргументом функции является кортеж
(Int, Int), эти два числа складываются в теле функции:addPair :: (Int, Int) -> Int
addPair (x, y) = x + y
👍1🤓1