Функциональные типы и композиция функций в Хаскелле

Цель данной статьи – познакомить программиста с функциональными типами языка Хаскелл и с системой проверки и вывода типов. В качестве основного примера будет использоваться оператор композиции функций, поскольку единственное, что требуется для его использования – это функции, сущности, которые в функциональном языке имеются в изобилии. Предполагается, что читатель имеет представление о понятии типа, а также наличие опыта программирования на типизированном языке. Знание Хаскелла не обязательно, необходимые для изложения элементы синтаксиса языка вводятся по мере необходимости. Желательно, чтобы читатель был знаком с языком C (и, в какой-то мере, C++); именно с этими языками по ходу изложения проводятся аналогии.

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

Хаскелл представляет собой функциональный язык со строгой статической типизацией. Строгость означает, что любое корректное выражение имеет однозначный (хотя возможно и обобщённый) тип, а статичность – что правильность типа проверяется во время компиляции. Однако сам по себе язык устроен так, что типы указывать не обязательно: компилятор способен сам вывести типы выражений на основании их использования в программе. Тем не менее, в Хаскелле допускается и даже приветствуется указание типов; в рамках этой статьи мы будем поступать именно так.

Типы функций

Как интерпретируется в языке X следующая пара идущих подряд пользовательских идентификаторов?

Ответ на этот вопрос кое-что говорит о языке X. Ясно, что в языках с развитым синтаксисом это не может быть полноценной программой, однако приходящая в голову программисту трактовка такой конструкции указывает на нечто важное, что разработчики хотели вложить в язык. Скажем, для C++ (после добавления ; в конце) сразу приходит в голову такая интерпретация: объявляется и определяется переменная bar, имеющая определённый где-то ранее тип foo, при этом тип foo имеет публичный конструктор без аргументов.

В Хаскелле естественная интерпретация такой конструкции: применение функции foo к bar. Применение функции в Хаскелле не требует никаких скобок. Это свойство обусловлено генезисом языка: именно таково поведение комбинаторов в комбинаторной логике, разработанной в 30-е годы прошлого века Хаскеллом Карри, в честь которого язык и назван.

Итак, foo bar в Хаскелле – это применение функции foo к bar. Для C++ мы смогли провести некоторые рассуждения о связи foo и bar и о возникающих ограничениях. Аналогичным образом мы поступим и для Хаскелла.

Определение функции и сигнатура типа

Пусть bar имеет тип t. (мы не даём формального определения понятия типа, предполагая, что программист интуитивно представляет себе смысл этого термина). В Хаскелле это утверждение о типизации записывается так: bar::t; оператор :: так и читается: “имеет тип”. Тогда функция foo должна принимать “переменную” такого типа в качестве аргумента и, поскольку это функция, возвращать значение какого-то типа, скажем, u. Для выражения идеи о типе функции с аргументом типа t, возвращающей значение типа u, в Хаскелле используется такая нотация: foo::t->u. О таком выражении говорят как о сигнатуре типа функции foo. Например, пусть:

        -- это код на Хаскелле
bar :: Int              -- сигнатура типа
bar = 3                 -- определение

foo :: Int -> Int       -- сигнатура типа
foo x = x + 1           -- определение

Тогда выражениеfoo bar будет иметь значение типа Int, равное 4. Дадим эквивалентные определения на языке C:

        // это код на С
        int bar(){
  return 3;}

int foo(int x){
  return x + 1;}

Эквивалентом выражения foo bar в Хаскелле будет вызов foo(bar()) в C. Сравнение определений одноимённых функций на двух этих языках поможет понять синтаксические соглашения, принятые в Хаскелле. Отметим, что сигнатуры типов в Хаскелле отделены от определения функций и, вообще говоря, могут находиться в любом месте программы или даже вообще отсутствовать.

Оператор =не является оператором присваивания, но понимается (и читается) в математическом смысле: равно по определению. Слева от = расположена определяемая функция и её формальные параметры (если таковые имеются), справа – собственно определение функции, то есть выражение, описывающее операции, которые эта функция должна произвести над своими формальными параметрами.

Слово “переменная” в отношении bar не зря было взято в кавычки; по существу ничего кроме функций (и типов) в Хаскелле нет. И уж чего точно нет, так это переменных в смысле императивного программирования, то есть именованных хранилищ, содержащих некоторое значение, которое можно менять. В этом смысле bar в примере на Хаскелле – это полноценная функция, хотя её определение bar = 3 может навести на мысли о присваивании.

Более того, даже целый литерал 3 тоже можно рассматривать как функцию. Её сигнатура совпадает с сигнатурой функции bar, а именно 3::Int (это совершенно корректная запись!), и она на самом деле представляет собой один из многих нуль-арных (т.е. не имеющих аргументов) конструкторов типа Int.

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

Вернёмся к общему виду выражения foo bar, с сигнатурами bar::t и foo::t->u. Сам по себе тип u может быть структурно сколь угодно сложен. Пусть u – это тип функции v->w, тогда foo::t->(v->w) или foo::t->v->w, поскольку оператор стрелка (->) в Хаскелле правоассоциативен. Причина этой правоассоциативности вскоре станет ясна. Рассмотрим такой пример:

bar :: Int
bar = 3

foo :: Int -> Int -> Int
foo x y = x + y

        // это код на С
        int foo(int x, int y){
  return x + y;}

Ясно, что foo для обоих языков – это просто функция от двух аргументов. Например, foo 5 6 имеет значение 11. Обратим внимание, что в Хаскелле применение функции не только не требует скобок, но и не нуждается в пунктуационных разделителях аргументов, вроде запятой в C, где аналогичный вызов имел бы вид foo(5, 6). Это тоже наследие комбинаторной логики – любой комбинатор (в Хаскелле – функция) считывает справа от себя столько аргументов, сколько ему необходимо в соответствии со своей арностью (унарный – один, бинарный – два, нуль-арный – ни одного).

Однако и при новом определении foo и bar выражение foo bar остаётся правильным выражением языка Хаскелл. Только теперь это выражение представляет собой функцию! В первоначальном примере тип выражения foo bar был Int, теперь же foo bar имеет тип Int->Int. Это пример так называемого частичного применения функции foo. Если мы применим foo bar к числу, то получим число, большее на 3, то есть функция foo bar увеличивает свой аргумент на три. Скажем, значение выражения foo bar 7 равно 10.

Мы можем рассматривать foo bar 7 двояко. С одной стороны, можно сказать, что функции двух аргументов foo передаются два аргумента подходящего типа: bar и 7. С другой стороны, можно сказать, что функции двух аргументов foo передаётся один аргумент bar, связывающий первый аргумент функции foo. Получившаяся в результате функция одного аргумента применяется к 7. С точки зрения Хаскелла оба подхода совершенно эквивалентны!

Функции, допускающие последовательное частичное применение себя к своим аргументам, называются каррированными. В Хаскелле функции именно таковы. Если посмотреть на сигнатуру foo::Int->Int->Int, и воспользоваться правоассоциативностью стрелки: foo::Int->(Int->Int), то видно, что foo при применении к аргументу типа Int возвращает функцию, типа Int->Int. В более общем случае некоторой функции трёх переменных f::t1->t2->t3->t4 имеем эквивалентную запись f::t1->(t2->t3->t4). Если имеются “переменные” v1::t1, v2::t2 и v3::t3, то выражение f v1 имеет тип t2->t3->t4, выражение f v1 v2 имеет тип t3->t4 и, наконец, f v1 v2 v3 имеет тип t4. Теперь ясно, что правоассоциативность функциональной стрелки поддерживает механизм частичного применения функций.

Функции высшего порядка

Вернёмся к исходной, более общей, интерпретации выражения foo bar, а именно bar::t и foo::t->u. Тип t, как и u, может быть структурно сложным. Если, скажем, нам известно, что bar::t1->t2, то тогда foo::(t1->t2)->u. Например:

bar :: Int -> Int
bar x = x - 2

foo :: (Int -> Int) -> Int
foo f = f 5

При таком определении foo и bar значением выражения foo bar будет число 3. Эквивалент на языке С для функции bar таков:

        // это код на С
        int bar(int x){
  return x - 2;}

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

        // это код на С
        int foo( int (*f)(int) ){
  return f(5);}

В Хаскелле функция, как аргумент другой функции – вполне заурядная ситуация, и запись типизации для этого случая удобнее принятой в C. О функциях с функциональными аргументами иногда говорят как о функциях высшего порядка. Скобки в сигнатуре типа в этом случае существенны! Именно они указывают нам, что параметром функции foo должна служить другая функция, имеющая тип Int->Int, а не два значения типа Int. Функция foo – это функция одного (функционального) аргумента, её определение foo f = f 5 ясно отражает этот факт. Формальный параметр f из определения foo в выражении foo bar связывается функцией bar.

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

Отметим, что данная нами типизация foo::(Int->Int)->Int ограничивает область применимости foo. Предположим, что мы не стали бы указывать явно сигнатуру типа foo. Тогда, если бы bar имела тип Int->Char, то foo bar было бы корректным выражением типа Char, поскольку возвращало бы результат применения bar к 5. Аналогично, если бы bar::Int->Bool, то выражение foo bar имело бы тип Bool. Определение foo f = f 5 не накладывает никаких ограничений на возвращаемый тип f и, следовательно, foo. Функция foo, если не задавать для неё конкретную сигнатуру типа, представляет собой полиморфную функцию. Её обобщённый тип можно записать так

где параметр b – это некий (произвольный) тип. Это пример так называемого параметрического полиморфизма, о котором мы подробнее поговорим ниже.

Тип оператора композиции

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

Рассмотрим сначала тип оператора композиции:

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

Первым аргументом этого оператора служит унарная функция, вторым аргументом тоже унарная функция, которая имеет следующее ограничение: её возвращаемое значение должно совпадать с типом аргумента первой функции. Это ограничение совершенно естественно – иначе композиция f(g(x)) просто не возможна из соображений типизации. Наконец возвращаемым значением оператора служит функция, имеющая как раз правильный “композитный” тип: она принимает в качестве аргумента значение типа аргумента второй (внутренней) функции и возвращает значение типа возвращаемого типа первой (внешней) функции.

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

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

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

Однако оба эти подхода не противоречат друг другу. Фактически, при первом подходе мы просто делаем частичное применение каррированной функции (оператора композиции), и, связав два её первых аргумента, заявляем: мы осуществили частичное применение – результатом является функция типа c->b, представляющая композицию двух функциональных аргументов. Запись f . g (или, в функциональном стиле, (.) f g) означает именно это. Однако мы можем осуществить не частичное, а полное применение оператора композиции: если x имеет тип c, то (f . g) x (или, в функциональном стиле, (.) f g x) – это значение типа b.

Стиль point-free

Дать определение оператора композиции в Хаскелле весьма просто. Например, его можно определить так:

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)

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

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

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

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

        -- обычный последовательный вызов, оператор композиции НЕ используется
compose' :: Int -> Int
compose' x = mult2 (add3 x) -- код здесь самый короткий! -- используем оператор композициии в функциональном стиле
compose'' :: Int -> Int
compose'' x = (.) mult2 add3 x 

-- используем оператор композициии в операторном стиле
compose''' :: Int -> Int
compose''' x = (mult2 . add3) x

Ни упрощения, ни сокращения записи при использовании оператора композиции не наблюдается. Однако в Хаскелле существует возможность использовать так называемый point-free стиль:

        -- используем оператор композициии и point-free стиль
compose :: Int -> Int
compose = mult2 . add3

То есть мы можем не указывать “точку применения” функции (в данном примере – формальный параметр x), если в её определении эта “точка применения” оказывается в правой части на крайнем правом месте последовательности применений функций. Функция compose – это то же самое, что и compose''', просто записанная в point-free стиле. Функция compose'' тоже может быть записана в этом стиле, а вот не использующая оператора композиции compose' – нет, поскольку её “точка применения” x, “спрятана внутри” определения функции.

Фактически при использовании point-free стиля мы смещаем акцент с программирования над данными к программированию функциями. Последовательное применение унарных функций f(g(h(x))) требует вложенных скобок и немедленного обеспечения аргумента самой внутренней функции, а выражение с оператором композиции f . g . h выглядит более элегантно и, что самое главное, может использоваться в качестве функционального аргумента функций высшего порядка.

Параметрический полиморфизм

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

        // это код на С
        typedef
        int a
typedefint b
typedefint c

c compose( c (*f)(b), b (*g)(a), a var){
  return f(g(var));}

Первая связана с тем, что из-за отсутствия самой возможности point-free стиля в C эта функция не имеет практического смысла. В отличие от Хаскелла, мы не можем программировать в C, игнорируя наличие третьего параметра var.

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

Оператор композиции представляет собой пример использования так называемого параметрического полиморфизма. Этот оператор строго типизирован, но с использованием не конкретных (Int, Char, Int->Int->Bool, и т.д.), а обобщённых типов. Величины a, b и с в сигнатуре типа оператора (.) называют переменными типа.

При использовании полиморфной функции (например, оператора композиции) на стадии компиляции происходит подстановка конкретных типов вместо переменных типа. Скажем, выражение (.) mult2 add3 7 типизируется так: mult2 имеет тип Int->Int, и оно замещает первый аргумент оператора композиции с типом b->c; система типов констатирует, что арность соответствует, и, следовательно, b отождествляется с Int и c тоже отождествляется с Int. Функция add3 тоже имеет тип Int->Int, и в результате замещения второго аргумента оператора композиции имеем, что a отождествляется с Int, а b тоже отождествляется с Int, причём уже второй раз. Если бы это второе отождествление b произошло с отличным от Int типом, результатом была бы статическая ошибка типизации. Наконец, третий параметр, числовой литерал 7, является перегруженным, но тип a, с которым он отождествляется, уже известен – это Int, поэтому 7 трактуется как 7::Int.

Обратим внимание, что типизация происходит на стадии компиляции, а вычисление самого выражения, если оно потребуется, произойдёт во время исполнения. В качестве упражнения: а каково значение выражения (.) mult2 add3 7?

Вывод типов

Как уже упоминалось, типы в Хаскелле указывать не обязательно – статическая система типов языка способна сама вывести правильный тип для любого корректного выражения языка. Но какой тип является правильным в полиморфном случае? Система типов Хиндли-Милнера, расширенная версия которой применяется в Хаскелле, даёт ответ на этот вопрос. В ней вводится понятие основного типа (principle type) выражения и доказывается, что для корректного выражения языка существует единственный основной тип.

Например, для оператора композиции основной тип именно таков, как, мы указывали выше: (.) :: (b -> c) -> (a -> b) -> a -> c. Такие типы, как, например, (Int -> Bool) -> (a -> Int) -> a -> Bool, являются допустимыми, но слишком частными, a такие, как a -> b -> c -> d – слишком общими.

Рассмотрим на примере оператора композиции, как может происходить вывод основного типа. Из левой части определения оператора композиции

ясно, что этот оператор является функцией трёх аргументов: f, g и x. То есть, неформально записывая ожидаемый тип, имеем:

        -- Это псевдо-Хаскелл!
(.) :: тип f -> тип g -> тип x -> возвращаемый тип

Исследуем правую часть определения оператора композиции на предмет ограничений, накладываемых на f, g и x производимыми в ней операциями. Из применения g x по аналогии с foo bar из начала статьи выводим x::a и g::a->b, где переменные типа a и b находятся под квантором общности. Выражение в скобках (g x) при этом имеет тип b. Поскольку в выражении f (g x) функция f применяется к (g x), имеем f::b->c, где новая переменная типа c тоже находятся под квантором общности. Возвращаемый тип всего оператора композиции – это возвращаемый тип f, то есть c. Итак, f::b->c, g::a->b и x::a; объединяя эти выводы, имеем: (.) :: (b -> c) -> (a -> b) -> a -> c

Подробно о системах проверки и вывода типов можно прочитать в [3].

Исследуем композицию

Частичное применение композиции

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

и осуществим частичное применение оператора композиции к этой функции, то есть рассмотрим выражение (.) mult2. Первый аргумент в (.) :: (b -> c) -> (a -> b) -> a -> c является унарной функцией b -> c, которая замещается унарной же mult2 :: Int -> Int, то есть арность подходит. Типы b и c при этом свяжутся типом Int. Тип выражения с частично применённой композицией (.) mult2 будет таков: (a -> Int) -> a -> Int.

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

(.) :: (t -> u) -> (a -> t) -> a -> u

Тип композиции, связывающий первый аргумент исходной (t->u), запишем в виде:

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

На первый взгляд связывание невозможно – не совпадают арности. Однако в Хаскелле всякая функция может рассматриваться как унарная и оператор композиции – не исключение. Перепишем его в виде унарной функции (напомним, что оператор -> правоассоциативен):

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

Отсюда, сравнивая с первым аргументом исходной композиции t->u, выводим, что

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

Именно таков основной тип (.) (.). Эта функция осуществляет композицию, которая в стандартной математической нотации имеет вид: f(x g(y)). Для этого в Хаскелле следует осуществить такой вызов:

Например, значение выражения (.) (.) (+) 3 mult2 4 будет равно 11. Заметим, что полученная конструкция не идеально подходит для point-free стиля – аргументы-функции f и g перемешаны здесь с аргументами-данными x и y.

Композиция композиций

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

(.) (.) :: (s -> t -> u) -> s -> (c -> t) -> c -> u

а тип композиции, связывающей первой аргумент данной, в виде

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

Сравнивая первый аргумент (.) (.), имеющий вид бинарной функции, и композицию (.), выводим:

(.) (.) (.) :: s -> (c -> t) -> c -> u

Подстановка полученных выше типов для s, t и u даёт:

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

В стандартной математической нотации эта композиция может быть записана так: f(g(x y)). Теперь мы можем осуществить её в Хаскелле с помощью следующего вызова:

Например, значение выражения (.) (.) (.) mult2 (+) 3 4 будет равно 14.

Функция (.) (.) (.) весьма полезна при программировании в point-free стиле. Дело в том, что оператор композиции (.) требует в качестве аргументов две унарные функции. Это может показаться странным, поскольку мы безо всяких проблем связывали аргументы композиции тернарными функциями (композициями же). Однако то, что допустимо для обобщённых типов, а именно возможность трактовки обобщённого t как u->v, невозможно для конкретного типа: Int, например, нельзя трактовать таким образом. Поэтому для композиции унарной и бинарной функций с арностью, “фиксированной” конкретными типами или иным образом, следует пользоваться (.) (.) (.). Ещё удобней ввести для такой композиции специальный оператор, например (.##)

        -- f(g(x y))
(.##) :: (a -> b) -> (c -> d -> a) -> c -> d -> b
(.##) =  (.) . (.)

Тогда композицию из предыдущего примера можно записать так: mult2 .## (+). При её применении к аргументам 3 4 мы по-прежнему получим 14.

Более того, внешних унарных функций может быть сколько угодно. Например, композицию с математической нотацией f(g(h(x y))), где внутренняя функция композиции – бинарная, легко можно записать в point-free стиле:

Например, значение выражения add3 .## mult2 .## (+) при применении его к аргументам 3 4 будет равно 17. В качестве упражнения для читателей оставляем разрешение следующего парадокса: почему композиция унарной f, унарной g и бинарной h имеет вид f .## g .## h, а не f . g .## h? (предполагается, что оператор (.##) имеет тот же приоритет, что и (.), и тоже правоассоциативен).

Повышаем арность

А что делать в случае, если внутренняя функция композиции имеет более высокую арность, например f(g(h(x y z)))? Для ответа на этот вопрос нам придётся рассмотреть работу композиции (.) (.) в несколько другом ракурсе. Введём для этой композиции именованную функцию

addArity :: (s -> t -> u) -> s -> (c -> t) -> (c -> u)
addArity =  (.) (.)

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

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

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

Его определение теперь можно записать в виде (.##) = addArity (.). Сравнивая две последние сигнатуры типа, мы видим, что фактически функция addArity просто добавила ко второму и третьему аргументу дополнительную единицу арности (c->). Если внимательно поглядеть на сигнатуру типа addArity, то видно, что она, собственно, и обещает это сделать (мы просто ещё чуть-чуть модифицировали эту сигнатуру, добавив скобки, необязательные из-за правоассоциативности стрелки):

addArity :: (s -> t -> u) -> (s -> (c -> t) -> (c -> u))

Мы можем рассматривать addArity как функцию, принимающую функцию и возвращающую функцию с повышенной кое-где арностью.

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

 (.###) :: (a -> b) -> (e -> c -> d -> a) -> (e -> c -> d ->b)
(.###) = addArity (.##) –- то есть (.) (.) (.##) или же (.) (.) ((.) (.) (.))

Получилось именно то, что надо: арность двух последних аргументов подросла на единицу (вывод этого факта оставляем в качестве упражнения). Иными словами, этот оператор предназначен для обслуживания композиций вида f(g(x y z)): в point-free стиле она имеет вид f .### g.

Развивая эту идею, можно породить целое семейство подобных операторов:

        -- f(g(x y z u))
(.####) :: (a -> b) -> (c -> d -> e -> f -> a) -> c -> d -> e -> f -> b
(.####) = addArity (.###) -- (.) . (.###)
-- f(g(x y z u v))
(.#####) :: (a -> b) -> (c -> d -> e -> f -> g -> a) -> c -> d -> e -> f -> g -> b
(.#####) = addArity (.####) -- (.) . (.####)
-- f(g(x y z u v w))
(.######) :: (a -> b) -> (c -> d -> e -> f -> g -> h -> a) -> c -> d -> e -> f -> g -> h -> b
(.######) = addArity (.#####) -- (.) .  (.#####)
-- и т.д.

        -- f(g(x))
(.#) :: (a -> b) -> (c -> a) -> c -> b
(.#) =  (.)

то получившееся семейство можно рассматривать, как модель нумералов Чёрча. При этом в качестве SUCC выступает addArity, а обычный оператор композиции играет роль сложения; то есть верно любое соотношение такого типа: (.##) . (.###) = (.#####) (данное выражает равенство 2+3=5).

(.##) f g x y    = f (g x y)
(.###) f g x y z = f (g x y z)

Литература и ссылки

Эта статья опубликована в журнале RSDN Magazine #3-2007. Информацию о журнале можно найти здесь

Функциональные типы и композиция функций в Хаскелле

Автор: Денис Москвин
SoftJoys Computer Academy
Источник: RSDN Magazine #3-2007

Опубликовано: 14.11.2007
Исправлено: 10.12.2016
Версия текста: 1.0

Введение

Типы функций

Определение функции и сигнатура типа

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

Функции высшего порядка

Тип оператора композиции

Стиль point-free

Параметрический полиморфизм

Вывод типов

Исследуем композицию

Частичное применение композиции

Композиция композиций

Повышаем арность

Литература и ссылки

Функциональные типы и композиция функций в Хаскелле

Автор: Денис МосквинSoftJoys Computer AcademyИсточник: RSDN Magazine #3-2007

Опубликовано: 14.11.2007Исправлено: 10.12.2016Версия текста: 1.0

Введение

Типы функций

Определение функции и сигнатура типа

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

Функции высшего порядка

Тип оператора композиции

Стиль point-free

Параметрический полиморфизм

Вывод типов

Исследуем композицию

Частичное применение композиции

Композиция композиций

Повышаем арность

Литература и ссылки

Автор: Денис Москвин
SoftJoys Computer Academy
Источник: RSDN Magazine #3-2007

Опубликовано: 14.11.2007
Исправлено: 10.12.2016
Версия текста: 1.0