23 ноября 2011 в 22:10

Категория Hask

Вступление


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

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

Эта статья во многом повторяет (в том числе заимствует иллюстрации) раздел из английской Haskell Wikibook, но тем не менее не является непосредственным переводом.

Что такое категория?



Примеры


Для наглядности рассмотрим сначала пару картинок изображающих простые категории. На них есть красные кружочки и стрелки:

Красные кружочки изображают «объекты», а стрелки – «морфизмы».

Я хочу привести один наглядный пример из реальной жизни, который даст какое-то интуитивное представление о природе объектов и морфизмов:

Можно считать города «объектами», а перемещения между городами – «морфизмами». Например, можно представить себе карту авиарейсов (как-то не нашёл я удачную картинку) или карту железных дорог – они будут похожи на картинки выше, только сложнее. Следует обратить внимание на два момента, которые кажутся в реальности само собой разумеющимися, но для дальнейшего имеют важное значение:
  • Бывает, что из одного города в другой никак не попасть поездом или самолётом – между этими городами нет морфизмов.
  • Если мы перемещаемся в пределах одного и того же города, то это тоже морфизм – мы как бы путешествуем из города в него же.
  • Если из Санкт-Петербурга есть поезд до Москвы, а из Москвы есть авиарейс в Амстердам, то мы можем купить билет на поезд и билет на самолёт, “скомбинировать” их и таким образом попасть из Санкт-Петербурга в Амстердам – то есть можно на нашей карте нарисовать стрелку от Санкт-Петербурга до Амстердама изображающую этот скомбинированный морфизм.
Надеюсь, с этим примером всё понятно. А теперь немного формализма для чёткости.

Определение


Итак, мы уже знаем, что категория состоит из объектов и морфизмов:
  1. Имеется класс (совокупность) объектов. Объектами могут быть любые сущности.
  2. Для любых двух объектов A и B определён класс морфизмов Hom(A,B). Для морфизма f из этого класса объект A называется областью, а Bкообластью. Это записывают так:
    f ∈ Hom(A,B) или f : A → B.
  3. Для любых двух морфизмов f : A → B и g : B → C определена их композиция – морфизм h = g ∘ f,
    h : A → C. Важно, что область g и кообласть f совпадают.
  4. Композиция ассоциативна, то есть для любых морфизмов f : A → Bg : B → C и h : C → D выполнено равенство
    (h ∘ g) ∘ f = h ∘ (g ∘ f)
  5. Для любого объекта A имеется «единичный» морфизм, который обозначается idA : A → A и он нейтрален относительно композиции, то есть для любого морфизма f : A → B выполнено:
    idB ∘ f = f = f ∘ idA.
В дальнейшем индекс будет мне мешать и я буду писать просто id, поскольку его область/кообласть восстанавливаются из контекста.

Можно проверить, что для приведённых выше примеров все свойства выполнены: композиция когда нужно определена, ассоциативна и соответствующие единичные морфизмы нейтральны относительно неё. Единственная неувязка возникает с ассоциативностью в примере про перемещения между городами – тут нужно думать о композиции, как “комбинировании билетов”, а не просто последовательных перемещениях конкретного человека.

Упражнение для самопроверки: проверить, изображает ли следующая картинка категорию



Категория Hask


А теперь главный пример, основная тема статьи. Категория Hask состоит из типов языка Haskell и функций между ними. Более строго:
  1. Объекты Hask: типы данных с кайндом1 *. Например, примитивные типы: Integer, Bool, Char и т.п. “Тип” Maybe имеет кайнд * → *, но тип Maybe Bool имеет кайнд * и поэтому является объектом в Hask. То же самое с любыми параметризованными типами, но о них позже. Обозначение: a ∷ * ≡ “тип a имеет кайнд *” ≡ “a является объектом в Hask”.
  2. Морфизмы Hask: любые Haskell’евские функции из одного объекта (типа) в другой. Если a, b ∷ *, то функция f ∷ a → b – морфизм с областью a и кообластью b. Таким образом класс морфизмов между объектами a и b – обозначается типом a → b. Для полноты аналогии с математической нотацией можно ввести такой синоним:
    type Hom(a,b) = a → b 
    Но я не буду им дальше пользоваться, так как стрелка, на мой взгляд, нагляднее.
  3. Композиция: стандартная функция (.) ∷ (b → c) → (a → b) → (a → c). Для любых двух функций f ∷ a → b и g ∷ b → c композиция g . f ∷ a → c определяется естественным образом:
    g . f = λx → g (f x) 
  4. Из этого определения очевидна ассоциативность композиции: Для любых трёх функций
    f ∷ a → b, g ∷ b → c и h ∷ c → d выполнено
    (h . g) . f ≡ h . (g . f) ≡ λx → h (g (f x)) 
    Непосредственная проверка:
        (h . g) . f ≡ λx → (h . g) (f x)
                    ≡ λx → (λy → h (g y)) (f x)
                    ≡ λx → h (g (f x))
    
        h . (g . f) ≡ λx → h ((g . f) x)
                    ≡ λx → h ((λy → g (f y)) x) 
                    ≡ λx → h (g (f y))
  5. Для любого типа a ∷ * функция id ∷ a → a определена тоже естественным образом:
    id = λx → x 
    Из этого определения очевидно выполнение требуемых свойств. Пусть f ∷ a → b
    f . id ≡ λx → f (id x) ≡ λx → f x ≡ f
    id . f ≡ λx → id (f x) ≡ λx → f x ≡ f
    
Эта функция полиморфная, поэтому одна на всех, но с точки зрения единичного морфизма мы будем воспринимать её как отдельный морфизм для каждого конкретного типа, например для объекта Char это будет мономорфная функция id ∷ Char → Char. Поэтому я и говорил до этого про индекс – в Haskell’е можно не писать каждый раз какой именно id нам нужен, потому что его тип автоматически выводится из контекста.

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

Дальше я расскажу о том, что такое функторы и как они воплощаются в категории Hask.

Функторы


Функторы – это преобразования из одной категории в другую. Поскольку каждая категория состоит из объектов и морфизмов, то и функтор должен состоять из пары отображений: одно будет сопоставлять объектам из первой категории объекты во второй, а другое будет сопоставлять морфизмам из первой категории – морфизмы во второй.

Сначала я дам математическое определение, а потом продемонстрирую, насколько простым оно становится в случае Haskell’а.

Математическое определение


Рассмотри две категории C и D и функтор F из C в D. Обозначения используются такие же как для морфизмов, только функтор обозначается большой буквой: F : CD. Это F выполняет две роли:
  1. Каждому объекту A из категории C ставится в соответствие объект из категории D и обозначается F(A).
  2. Каждому морфизму g : A → B из категории C ставится в соответствие морфизм из категории D и обозначается F(g) : F(A) → F(B).
Ещё раз, функтор – это пара отображений:
    A ↦  F(A)
    g : A → B  ↦  F(g) : F(A) → F(B)

На картинке первое отображение изображено жёлтыми пунктирными стрелками, а второе – синими:


От функтора требуется выполнение двух вполне естественных требований:
  1. Он должен переводить каждый единичный морфизм данного объекта в единичный морфизм его образа:
    F(idA) = idF(A)
  2. Он должен переводить композицию морфизмов в композицию их образов:
    F(h ∘ g) = F(h) ∘ F(g)


Функторы в Hask


Теперь мы рассмотрим функторы из категории Hask в Hask. К слову, такие функторы, которые переводят категорию в неё же саму, называются эндофункторами.

Так вот, значит нам нужно переводить типы в типы, а функции в функции – два отображения. И какая же конструкция языка Haskell воплощает первое? Правильно, типы с кайндом * → *.

Например, упомянутый уже тип Maybe ∷ * → *. Это отображение, которое сопоставляет любому объекту a ∷ * объект из той же категории (Maybe a) ∷ *. Здесь Maybe a следует воспринимать не как конструктор параметризованного типа с данным параметром a, а как единый символ, аналогично F(A) из математического определения.

Итак, первое отображение достаётся нам даром – это любой конструктор типа с параметром.
    data Maybe a = Nothing
                 | Just a

Но как получить второе отображение? Для этого в Haskell определён специальный класс:
    class Functor f where
        fmap ∷ (a → b) → (f a → f b)
где f ∷ * → *. То есть fmap – это полиморфная функция, которая принимает морфизм a → b, а возвращает морфизм f a → f b. Исходя из этого сделаем Maybe настоящим функтором, определив для него такую функцию:
    instance Functor Maybe where
        fmap g = fg
           where fg Nothing  = Nothing
                 fg (Just x) = Just (g x)

Итак, мы получили два отображения:
    a ∷ *  ↦  Maybe a ∷ *
    g ∷ a → b  ↦  fmap g ∷ Maybe a → Maybe b

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

Хорошо, а что с выполнением требований? fmap должен сохранять id и переводить композицию в композицию:
    fmap id ≡ id
    fmap (h . g) ≡ (fmap h) . (fmap g)

Несложно проверить, это в случае приведённого выше определения fmap для Maybe.

Обратите внимание на то, что первое отображение мы получаем, просто объявив конструктор типа с параметром. И для него, как для отображения между объектами не важно, как устроен тип Maybe: он просто сопоставляет объекту a объект Maybe a, что бы за этим ни стояло.

В случае же с отображением морфизмов всё не так просто: нам приходится вручную определять fmap, учитывая структуру типа Maybe. С одной стороны это даёт нам определённую гибкость – мы сами решаем, как какая-либо функция будет преобразовывать конкретную структуру данных. Но с другой стороны, было бы удобно получать это определение даром, если мы хотим, чтобы оно было устроенно естественным образом. Например, для типа
    data Foo a = Bar a Int [a]
               | Buz Char Bool
               | Qux (Maybe a)
функция g ∷ a → b должна рекурсивно обойти все конструкторы данных и везде, где у них есть параметр типа a преобразовать его с помощью g. Причём если встречается [a] или Maybe a, то для них должен сработать свой fmap g, который снова обойдёт их структуру и преобразует её.

И о чудо, это возможно! В GHC есть соответствующее расширение. Пишем в коде:
    {-# LANGUAGE DeriveFunctor #-}
    …
    data Foo a = …
         deriving Functor

И получаем сразу полноценный эндофунктор категории HaskFoo, с соответствующим fmap.

Кстати, стоит сказать, что эти функторы на самом деле отображают категорию Hask в её подкатегорию, то есть в категорию, с меньшим классом объектов и морфизмов. Например, отображением a ↦ Maybe a мы никак не сможем получить простой тип Int – какое бы a мы ни взяли. Тем не менее получающийся подкласс объектов и класс функций на них в качестве морфизмов тоже образуют категорию.

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

Заключение


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

  1. Если кто не встречался раньше с кайндами (kinds), я в двух словах поясню. Кайнды – это что-то вроде системы типов над обычными типами. Кайнды бывают двух видов:
    • * – это кайнд простого, не параметризованного типа. Например Bool, Char и т.п. Пользовательский тип data Foo = Bar | Buz (Maybe Foo) | Quux [Int] тоже будет простым: Foo ∷ *, потому что конструктор типа не имеет параметров (хотя его конструкторы данных имеют)
    • … → … – это более сложный кайнд, у него на местах троеточий могут стоять любые другие кайнды составленные из * и . Например: [] ∷ * → *, или (,) ∷ * → (* → *) или что угодно ещё более сложное: ((* → *) → *) → (* → *).

    Смысл всё это имеет простой: конструкторы типов – это своего рода функции над типами и кайнды описывают, как эти функции правильно взаимодействуют. Например мы не можем написать [Maybe], потому что [] ∷ * → *, то есть аргумент скобочек должен иметь кайнд *, а у Maybe он * → *, то есть Maybe тоже функция и если мы дадим ей аргумент Int ∷ *, то получим Maybe Int ∷ * и уже можем передать это скобочкам: [Maybe Int] ∷ *. Для такого рода контроля кайнды и существуют.

+46
3217
93

комментарии (99)

+7
qrazydraqon, #
Удивительно, но статья оказывается полезной даже тем, кто про Haskell ничего не знает.
+3
laughedelic, #
И это не может не радовать.
На самом деле можно пытаться экстраполировать это всё на другие языки, но я не знаю хороших примеров. Ну вот, наверное, дженерики в Java – тоже функторы в некотором смысле. Но я в этом не силён… Ким писал на эту тему, но у него пост не публичный, если откроет – дам ссылку.
Если кто может провести хорошие аналогии – примеры в студию! ")
+3
qrazydraqon, #
Так сразу пример не придумывается, но надо полагать, их можно найти в каком-нибудь месте типа страницы Джона Баеза. Судя по его знаменитому тексту Physics, Topology, Logic and Computation: A Rosetta Stone он должен быть в курсе таких вещей.
0
Darkus, #
Кстати, перевод этой работы (а также нескольких других статей) можно найти здесь.
+3
jack128, #
частные случае легко: (C#)

IEnumerable
IEnumerable fmap(Func<T, TResult> f, IEnumerable source)
{
var result = new List();
foreach(var item in source) result.Add(f(item));
return item;
}
NullableNullable fmap(Func<T, TResult> f, Nullable source)
{
if (source.HasValue) return new Nullable(f(source.Value));
return new Nullable();
}
вот вполне себе функторы. Проблема .NET'а в слабой системе типов. Из-за этого само понятие functor(точнее обощенную сигнатуру функции fmap) на C# нельзя выразить.
+1
jack128, #
Мдя, в общем дженерик аргументы в квадратных скобках пишу.

IEnumerable[T]
IEnumerable[TResult] fmap(Func[T, TResult] f, IEnumerable[T] source)
{
var result = new List[TResult]();
foreach(var item in source) result.Add(f(item));
return item;
}

Nullable[T]
Nullable[TResult] fmap(Func[T, TResult] f, Nullable[T] source)
{
if (source.HasValue) return new Nullable[TResult](f(source.Value));
return new Nullable[TResult]();
}
0
megalol, #
IEnumerable — это функтор.
fmap имеет название Select, проверить можно по сигнатуре:

public static IEnumerable Select<TSource, TResult>(this IEnumerable source,
Func<TSource, TResult> selector)

Сравнить с

fmap :: Functor f => (a -> b) -> f a -> f b

Также это монада, аналогичная list (bind имеет название SelectMany)
А все эти from .... select ... - это подобие do-нотации с непонятными названиями.
0
lomeo, #
Разве? Т.е. для каждого A: IEnumerable метод Select тоже будет возвращать A? Нет, поэтому IEnumerable — это не функтор. Сравните со Scala:

trait Functor[F[_]] {
    def fmap[A, B](r: F[A], f: A => B): F[B]
}
+1
megalol, #
Конечно не будет. fmap возвращает не А, а B в коробке, что вы и продемонстрировали
0
lomeo, #
Это разные A. Давайте назовём первый A, скажем, Sample. Тогда читать так: «для каждого класса Sample, имплементирующего интерфейс IEnumerable, метод Select не будет иметь return type Sample<TResult>, следовательно IEnumerable — не функтор».
+1
megalol, #
Он будет иметь тип IEnumerable. Вы говорите о том, что
Select не есть Sample f => (a -> b) -> f a -> f b, потому что f b не обязательно должен реализовывать интерфейс Sample. Это так, но IEnumerable f => (a -> b) -> f a -> f b выполняется всегда.
0
lomeo, #
Sample — не интерфейс, а класс, реализующий IEnumerable.

Вот у вас написано: IEnumerable f => (a -> b) -> f a -> f b — это синтаксис Haskell? Если да, то что здесь будет в f, как пример?
0
megalol, #
Слева от => пишутся ограничения на типы. Ограничения говорят о том, что тип обязан реализовывать какой-то интерфейс. У класса тоже есть интерфейс, говоря, что что-то — это Sample, мы говорим о том, что у этого что-то соответствующий интерфейс.
f a — это «тип а, являющийся IEnumerable».
Что в C# нельзя сделать, это обобщение, нельзя объявить функцию «принимающую функтор», которая на равных правах принимала бы и IEnumerable и какой-нибудь IQueryable только на тех основаниях, что и там и там метод Select реализован. Но это не мешает им быть функторами.
0
lomeo, #
Мешает. Т.к. вы подтвердили, что это синтаксис Haskell, то я правильно распарсил ваше замечание «IEnumerable f => (a -> b) -> f a -> f b выполняется всегда».

Однако оно не выполняется: IEnumerable f говорит о том, что тип обязан реализовывать интерфейс IEnumerable, так? Причём таким образом, чтобы тип у Select был (a -> b) -> (f a -> f b). Однако это не так. Такой тип вообще невозможно описать на C# — он не поддерживает higher kinded types. Ср. с примером выше на Scala или функтором на Haskell.

Что я хочу подчеркнуть: в теоретико-категориальном смысле функтор — это отображение, сохраняющее структуру. Т.е. как минимум (=== — структурное равенство):

f.Select(x => x) === f

Если в C# это не так, то это не функтор.
+2
graninas, #
Отличная статья, больше спасибо! Каждый новый штрих добавляет картине реалистичности и глубины.
–6
mikhanoid, #
Эх. Вот было бы ещё в Haskell так же просто байтик по адресу 0xb8000 записать, цены бы ему не было. А так. Ну да, математика, на да, формально, ну да, можно мозг поупражнять. А дальше? А ведь не особо опытные менджеры уже начинают пытаться внедрять Haskell в production. Ужас.
–6
mikhanoid, #
В разработке software — все. Как бы всё равно никому ещё не удалось разработать не-фон-Неймановский универсальный процессор. А там запись байтиков направо и налево :) И вот нам говорят: машина работает одним способом, но нет, мы не будем придумывать язык, который позволит естественное для машины поведение программировать наиболее естественным образом. Мы, наоборот, абстрагируемся, а потом будем ковыряться левой пяткой в правом ухе для решения простейших задач. Не понимаю я, к чему это?

Конечно, Haskell полезен для изучения, и как площадка для разработки некоторых концепций. Но внедрять его в production — это садизм. А вот менеджеры начитавшийсь того, какой Хаскелл весь из себя супер-пупер-продуктивный, надёжный и красивый, уже начинают кое-где компанию. Мне уже три раза предлагали работу такую — с ужасом отказался. Я к тому, что нужно всё же в статьях о Haskell явно писать, что это академический язык.

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

Фанатство это, imho, какое-то.

Ну. И уж тем более, к разработке железа сводится ещё меньше задач, чем к записи байтиков. Так что, ни разу не аргумент.
+1
zw0rk, #
[url=http://www.haskell.org/haskellwiki/Haskell_in_industry]Обчитавшиеся менеджеры вот этим людям насоветовали[/url]. Глупые ребята из AT&T и Meryll Lynch купились на маркетинговый хайп в среде гиков, да.
–2
mikhanoid, #
Ну, парсят они текст — не самая сложная задача. И что? Я тоже транслятор на Haskell написал. Это не самая сложная задача. Даже можно сказать, одна из самых простых (не путать с оптимизирующим компилятором). Средств для автоматического создания парсеров полно для множества языков. А Haskell выбирают, imho, именно для того, чтобы продемонстрировать: а мы тоже можем на Haskell, мы тоже крутые. А что за последние два года случилось с Merril Lynch нам известно :)
+2
zw0rk, #
— We use custom simulation tools developed in Haskell, to model our hardware designs…
— Haskell is being used in the Network Security division to automate processing of internet abuse complaints
Galois
— и т.д. и т.п.

Каждый видит то, что хочет.
0
mikhanoid, #
Не знаю. Логическое моделирование электроники на Haskell ничем не отличается от моделирования на C++, и в этом ничего особо сложного нет, это с технической точки зрения — простые программные системы. Abuse complains — это как раз парсинг текста. В Галуа же вообще production непонятный. У них на сайте в основном речь идёт об автоматическом доказательстве теорем и о том, какие они крутые инженеры. В технологиях написано, что они вообще всем занимаются, а в секции Downloads ссылки на сторонние продукты. Похоже на надувательство какое-то: типа, отстаньте от нас, мы — Haskellers.

Ну и потом. Есть же всякие разные относительно объективные попытки сравнить. Тот же shootout.alioth.debian.org. Ну не видно там особых преимуществ Haskell и других функциональных языков в выразительности над императивными. Нет такого, что на код смотришь, и сразу всё понимаешь. И нет такого, что код существенно короче.

Я вот это вижу. И вижу исходный код в Hackage. И я не вижу, что он красивше. И я знаю, что модифицировать его очень сложно под свои нужды (как раз из-за неотчуждаемости результатов вычислений от самих вычислений). Поэтому меня и напрягает пропаганда без указания слабых мест.
0
zw0rk, #
> Логическое моделирование электроники на Haskell ничем не отличается от моделирования на C++, и в этом ничего особо сложного нет, это с технической точки зрения — простые программные системы.

Насколько вы в теме вообще «моделирования железа»?
0
mikhanoid, #
Мы сотрудничаем с компанией, которая занимается разработкой микропроцессоров. Как раз помогаем им с моделированием и компиляторами.

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

Это я именно о моделировании логики. Понятно, что моделирование уже физическое — это задача совсем другой сложности. Но я не видел, чтобы Haskell применялся для этого. Всё, что показывают — это именно логические модели, иногда с трансляцией в RTL (через какой-нибдь HDL-язык).
0
laughedelic, #
А работу-то где предлагали, поделитесь, если не секрет (;
+3
gricom, #
Конечно, Haskell в продакшне — это ужас. А вот руками байтики писать — это нормально. Да еще и эти менеджеры глупые вечно мешают.
–3
mikhanoid, #
А вы видели Haskell в production'е? Это полная bottom, когда пытаешься разобораться, что код делает. Когда байтики, то можно хоть снизу-вверх восстановить программу. Это не так уж и сложно и существуют автоматизированные средства для разбора и можно использовать хорошие средства символьного исполнения, для отладки смысла.

А в Haskell. Да почитать хотя бы даже тем, чем они хвастаются, Frag или Darcs — это ж тихий ужас. В последнем ещё и куча кода на Си понамешана. И все три раза production на Haskell был похож именно на ужасный Darcs.

Нет, чур меня, чур! Лучше байтики.
+3
gricom, #
Если знать, как он работает — то писать на нем не сложнее, чем на любом другом языке. А если не знать — то и Haskell, и ручная запись байтов в память (хотя это всё же грязный хак) превращает любую систему в черную шайтан-коробку.
–3
mikhanoid, #
Сложнее, даже если и знать, как работает. Тут есть некие принципиальные usability (и тут надо учитывать не только скорость написания, но и скорость чтения) и технические особенности, которые делают чистое функциональное программирование сложным, даже если и понимать, как оно работает. Их можно описать (может быть, когда-нибудь разгребу черновики).

Кроме того, ну ввод/вывод же, управление процессами и всё такое прочее. Разве монады — это не хак? Тем более, что IO работает совсем не так, как State transformer, потому что на чистом ленивом языке ввод/вывод просто даже теоретически нельзя запрограммировать.

Сложности в нетривиальных задачах возникают у большого числа программистов.
+1
lomeo, #
> потому что на чистом ленивом языке ввод/вывод просто даже теоретически нельзя запрограммировать.

Почему?
–1
mikhanoid, #
А как? В таком языке нет концепции адрес ввода/вывода, а без него ничего нельзя ни прочитать, ни записать. Вот хотите вы пользователю в глаз направить пучок фотонов, чтобы он увидел от вашей программы информацию, но вот беда, как бы вы ни старались написать функцию write, она ничего никуда направить не может, кроме как в результат своего вычисления, чистая же :) Это вам придётся глаз пользователя как-то включать в свою программу
+3
lomeo, #
Это не проблема чистого или ленивого языка. Это проблема языка, у которого нет указателей. Добавим их — и вуаля — вдруг чистый и ленивый язык начал испукать пучки фотонов прямо пользователю в глаз :-)
0
mikhanoid, #
Указатели тут ни при чём. И как только вы добавите указатели чистый язык превратится в грязный, а ленивый подстрелит себя в ногу из мегаваттного лазера
+3
lomeo, #
> Указатели тут ни при чём.

А что причём? И почему — объясните. Про указатели я могу объяснить — как только мы добавили указатели, мы получили прямой доступ к памяти и значит можем в неё писать и читать из неё :-)

> И как только вы добавите указатели чистый язык превратится в грязный…

См. безопасная работа с указателями в Haskell. О некоторых вариантах я уже писал вам.
0
mikhanoid, #
А что причём? И почему — объясните. Про указатели я могу объяснить — как только мы добавили указатели, мы получили прямой доступ к памяти и значит можем в неё писать и читать из неё :-)

Дело не собственно в памяти. Чтобы организовать обмен данными с внешним миром, нам нужно иметь канал связи с этим миром. А канал связи — это система, у которой нужно явно менять состояния. Если мы рассматриваем сам Haskell (ну, или любой чистый функциональный язык), то там нет такой концепции. Нельзя изменить состояние канала, можно только лишь создать новый канал. Но как внешний мир может узнать об изменении канала связи?

Вот в чём проблема. В Haskell, конечно, есть и указатели, и ссылки, и IO, но их невозможно запрограммировать на самом Haskell, поэтому они создаются искусственно, через специальные монады связанные со внешними библиотеками на Си. И эти монады отличаются от тех, которые можно создать на самом Haskell (если я хоть немного понимаю исходники GHC, то это так. Впрочем, могу ошибаться).
+2
lomeo, #
Чтобы подчеркнуть — я спорю исключительно с замечанием о том, что чистота и ленивость языка как-то мешает, например, читать/писать из памяти.

> А канал связи — это система, у которой нужно явно менять состояния. Если мы рассматриваем сам Haskell (ну, или любой чистый функциональный язык), то там нет такой концепции.

Чистота не мешает наличию канала связи в языке. Ведь канал связи можно реализовать по разному. Необязательно менять его состояние. Например, можно последовательно читать и возвращать новые состояния. Можно реализовать монадами, как сделано сейчас. Можно использовать cps. Внешний мир в любом случае узнает об изменении канала связи через натив. Как и в Java, который не чистый. Хотя бы поэтому — понятия IO и чистоты ортогональны.

> В Haskell, конечно, есть и указатели, и ссылки, и IO, но их невозможно запрограммировать на самом Haskell, поэтому они создаются искусственно, через специальные монады связанные со внешними библиотеками на Си

«Через монады» — например, да, «связанные с внешними библиотеками на Си» — не обязательно. Если вы про теоретическую возможность («невозможно запрограммировать»), то IORef можно написать на State (Map Address Value), например. Натив не потребуется.
0
gricom, #
Вы совсем не похожи на человека, который не знает, что говорит, тем не менее, пока я с вами согласиться не могу. Если вы заметили, то ваши комменты минусуют уже просто за то, что они ваши, поэтому предлагаю вам не тратить аргументы и карму в комментах, а написать статью, на основе ваших мыслей и упомянутых выше черновиков на тему функционального программирования.

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

Заранее спасибо.
+4
lomeo, #
poke (intPtrToPtr 0xb800) 0x00? Только это сломается.

В Haskell с указателями можно работать как напрямую (через Foreign.Ptr), так и безопасно (например, через IORef).

Для многих задач не нужны Foreign.Ptr и можно использовать что-то более безопасное. Например, для сравнения указателей можно использовать Foreign.StablePtr. Если нужно выделить память, поработать с ней напрямую, подсчитав что-то, то для этого есть безопасные механизмы Foreign.Marshall (см. Foreign.Marshal.Alloc, Foreign.Marshal.Utils).
0
mikhanoid, #
Foreign — это же уже не Haskell. Ну да, язык умеет работать с библиотеками на Си — это известно :) И многие этим пользуются для взрыва мозга.
+3
lomeo, #
Так всё не Haskell. Синус тоже, наверное, не на Haskell, или вывод на консоль. Важно где мы этим пользуемся.
–4
mikhanoid, #
Так это и есть философская проблема. Скажем, для Си или даже, допустим, Lua, вывод на консоль может быть написан на самих Си или Lua. А чистый функциональный язык уже не допускает этого.

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

Но ладно. Это вообще тема для одного большого топика, и здесь не уместно это обсуждать. Этот топик совсем не о том.
+3
lomeo, #
Дело не в том, функциональный язык или нет. На Java, например, нельзя написать вывод на консоль. Тоже нужно использовать нативные функции. Чем это мешает, не пойму — раскройте философскую подоплёку проблемы :)
–1
mikhanoid, #
Почему? В Java запросто можно писать в консоль на самой Java. Даже консоль можно всю на самой Java написать, если есть reflection. В самом простом варианте: настроить массив на видеопамять и писать туда буковки через операцию присваивания значения элементу. Реализовать свои read, и write, и что угодно. Есть такая операционная система JNode, там примерно так всё и сделано — на Java.

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

В чистом функциональном языке этого сделать нельзя. Какой-нибудь console.read всегда должен выдавать одно и то же, console.write — это вообще не понять, что такое, потому что он может лишь создать новое значение, а не разместить его в определённой позиции.

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

Поэтому нельзя на функциональном языке выразить работу с оборудованием и внешним миром. Нужны всякие костыли разной степени костыльности.
+3
lomeo, #
Как настроить массив на видеопамять в Java, не используя натив? И да, если мы имеем Ptr, настроенный на видеопамять в Haskell, то тоже можем записывать и считывать в/из него данные.

Console.Read пускай нам возвращает одно и то же, чем это может мешать? Главное, чтобы из этого «одного и того же» мы могли брать разные значения по мере того, как их вводит пользователь, например. Сделать это можно монадами, потоками, продолжениями…

Аналогично с Console.Write.

Про примеры с клиент и сервером — не понял. Я писал такие приложения на Haskell, писал отдельно сервер на Haskell, клиент на Java, например, писал клиент на Haskell… Поэтому замечание про «клиент и сервер — это часть одной программы» совершенно не понимаю. Объясните, будьте добры.

> Нужны всякие костыли разной степени костыльности.

Согласен, но вы так говорите, как будто это что-то плохое :) В подходе чистый-ленивый есть плюсы и для этого — мы можем легко комбинировать действия, т.к. они первоклассны в языке.
–1
mikhanoid, #
Как настроить массив на видеопамять в Java, не используя натив? И да, если мы имеем Ptr, настроенный на видеопамять в Haskell, то тоже можем записывать и считывать в/из него данные.

Настройка массива — это создание структуры с определёнными значениями полей. Заполнение структуры пишется на Java. Потом эта структура передаётся в специальный ClassLoader (который тоже написан на Java), превращающий эту структуру в языковый массив. Так сделано в JNode, в которой используется стандартная JRE. И в этой JNode native код используется только для переключения контекстов и для реализации операций с портами ввода-вывода для x86. Я даже сам удивился, что там так мало Си, когда смотрел. (Кстати, я не люблю Java, если что. Haskell мне нравится больше, но просто есть такой факт, JNode написана на Java, с драйверами на Java).

Про примеры с клиент и сервером — не понял. Я писал такие приложения на Haskell, писал отдельно сервер на Haskell, клиент на Java, например, писал клиент на Haskell… Поэтому замечание про «клиент и сервер — это часть одной программы» совершенно не понимаю. Объясните, будьте добры.

Моя вина. Я имел в виду то, что на Haskell нельзя написать канал обмена между клиентом и сервером. Во всех примерах message-queue, которые я видел на Haskell, клиент и сервер должны быть частью того же вычислительного процесса, в котором реализован этот канал.

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

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

Иногда он действительно и надёжнее и удобнее, но не всегда. И для очень многих случаев не подходит.
+1
lomeo, #
> Я даже сам удивился, что там так мало Си, когда смотрел.

Ну так об этом и речь! В этих языках своя песочница, для связи с внешним миром им нужен натив. (Мы, кажется, уже в двух потоках дискутируем о тезисе «чистота мешает IO»)

> Во всех примерах message-queue, которые я видел на Haskell, клиент и сервер должны быть частью того же вычислительного процесса, в котором реализован этот канал.

Distributed Haskell. Куча библиотек с Erlang-like исполнением. Там же ничего умного не надо. Есть библиотеки сериализации, пишем/читаем из сокета. Да и вообще, практически любой обмен с сетью организуется через пару каналов в двух потоках. Ничем не отличается от обычного кода на императивном языке, ну может чаще TChan используют :)

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

Уже то, что мы с вами ведём этот спор говорит о том, что в этом подходе есть ограничения ;-) И да — нет в мире совершенства.
+2
voidlizard, #
В хаскелле есть указатели. Пишите что хотите куда хотите на свой страх и риск.
–1
mikhanoid, #
Хых. Они не в Haskell. Почему Foreign считается частью Haskell? Это хардкорная либа, которая написана на Си и опирается на твики основного поведения процесса вычисления в Haskell. Считать Foreign частью Haskell то же самое, например, что считать работу с процессами частью Си, потому что в Unix есть fork.
+3
voidlizard, #
А в Си нет операторов ввода-вывода. Только во внешних библиотеках. И что? Си — академический язык, на котором невозможно писать приложения реального мира?

Кстати, не поделитесь, где вы видели толпы менеджеров, которые тянут хаскелл в продакшен?

Остальное даже не хочу комментировать.
+1
Darkus, #
Благодарю, отличная статья. Единственное замечание — «очевидные» вещи далеко не всегда оказываются очевидными. Например, ассоциативность композиции (.) в языке Haskell ещё надо доказать. Да, это очень просто, но не очевидно. Особенно тем, кто с такими понятиями не накоротке.

Ну и «кайнд» = «сорт» :).

Неистово ждём продолжения.
+1
laughedelic, #
Спасибо. Постараюсь меньше ссылаться на очевидность, хотя не хочется писать слишком подробно — читатель может заскучать в сплошных выкладках и забыть о чем была речь.
Про ассоциативность композиции добавлю сноску, там на самом деле нужно сделать одну оговорку.
А про кайнд = сорт, Вам правда кажется, что так лучше? Есть ли какие-то прецеденты такого перевода в литературе? ")
0
Darkus, #
М-м-м. Меня в институте (МИФИ) на кафедре Кибернетики на курсах по ФП учили, что kind = сорт. Оттуда этот термин и переместился в мои книги. Так что прецедентов такого перевода в литературе полно :).
+1
laughedelic, #
Хорошо. Возьму на заметку. «Сорта типов...» (: Непривычно несколько. Мне просто само слово kind нравится («по-доброму» звучит). Но это не важно. Я, кстати, тоже поступал на эту кафедру в МИФИ, но учиться решил всё же на матмехе в СПбГУ.
0
Darkus, #
Кайнд кайндом, но это всё же непереведённый англицизм (а с немецкого языка вообще переводится «ребёнок»). Я когда первую книгу писал, то советовался с некоторыми коллегами по ФП-сообществу. Сошлись на термине «сорт», который я предложил по своей памяти курсов по ФП, как я уже написал.
+1
laughedelic, #
Это хорошо, что советовались ") стало быть, общепринятая терминология. Буду использовать.
0
Darkus, #
Ну а куда без советов-то? :)
+2
youngmysteriouslight, #
Если тип назвать «характеристикой» терма, кайнд (kind) — типа, то «характеристикой» kind будет нечто, что [в частности] Барендрегт называет sort, например, в «Introduction to generalised type systems».
Да и в речи «тип терма, вид типа, сорт вида» звучит приемлемо.
Впрочем, если в русской литература используется перевод «сорт», то следует использовать именно его, как бы непривычно это не звучало. Нужно использовать единообразные обозначения.
+1
laughedelic, #
хм… «тип терма, вид типа, сорт вида» – звучит действительно хорошо!
0
Darkus, #
Я видал такое использование у Барендрегта, но, к сожалению, уже намного позже того, как написал свою первую книгу.

У меня ещё в своё время была идея воспользоваться наименованиями таксонов в биологической систематике живых видов, однако там тип — один из наивысших таксонов. Было бы иначе, можно было бы оттуда почерпнуть, кстати. А то ведь и сорта в понимании Барендрегта можно классифицировать и разбивать на непересекающиеся классы эквивалентности.
+1
zw0rk, #
В книжке Душкина, афаик, тоже сорт.
0
Darkus, #
Именно.
+1
laughedelic, #
Забавно. А кроме Ваших книг и ПФП, есть нынче какие-нибудь ещё издания на русском о ФП в общем и Haskell в частности? Знаю ещё вроде книжку от ИНТУИТ'а, но не читал…
0
Darkus, #
Книжка ИНТУИТ'а, насколько мне известно, про LISP. Есть ещё методичка Натальи Рогановой, но она очень поверхностна. Скоро выйдет перевод Learn Haskell for a Great Good. И на этом всё ограничивается. Про Haskell больше нет.

Про ФП в общем в последнее время вышло несколько книг. В частности, учебник Сергиевского и Волчёнкова в МИФИ, книга по F#.
+1
laughedelic, #
Спасибо, буду знать
+2
Darkus, #
Думаю, Вы видели, но всё же: Обзор литературы о функциональном программировании от Алекса Отта. Он обещался его актуализировать в ближайшее время.
+2
Qrilka, #
Книга Типы в Языках Программирования вот совсем недавно на русском вышла, в «столицах» уже можно пробрести вроде как. Хотя не совсем Хаскель, конечно.
+1
laughedelic, #
Спасибо за наводку! ") Стоит почитать
+2
ControlFlow, #
Ещё один вариант перевода «kind» — «типаж», но лично мне оно не нравится :) «типаж типа» — брр :)

Однако если kinds называть «сортами», то как называть сами sorts, предназначенные для классификации kinds? В языке code.google.com/p/omega/ все уровни выше kind'ов называются «sorts» :)
+1
Darkus, #
Вчера некоторое время думал над этим вопросом. Пришло на ум слово «семейство». Семейство типов. Как?
+2
ControlFlow, #
неплохо :) но, например, в том же Haskell уже есть механизм перегрузки данных, который называется «type families» — семейства типов :)
+1
Darkus, #
Блин, точно!

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

Кстати, Лингво переводит sort как:

вид, разновидность, класс, разряд, род, сорт, тип

Синонимы:

variety, quality, kind


Чудеса…
+1
megalol, #
Все переводят kind как вид, кроме читавших Душкина наверное
+1
Darkus, #
Все — это кто?

Повторюсь, что в моих книгах перевод «сорт» появился не с бухты-барахты. Выше в комментариях я разъяснил историю появления термина.
+1
laughedelic, #
О, кстати опять же в Мягком введении в Haskell увидел, что тоже пишут «вид»…
Всё же, имхо, с учётом сказанного в комментариях 1 и 2, «тип терма, вид типа, сорт вида» – самый хороший вариант.
+2
Darkus, #
Ладно, спорить не буду, ибо не о чем. Употребляйте, как Вам нравится. Только при первом использовании надо каждый раз говорить, какое английское понятие имеется в виду. Ну и я также буду поступать теперь.

А когда терминология устоится, тогда уж…

:)
+1
megalol, #
Моя преподша по английскому, например. Т.е. если, например, я переводил types of lasers как «виды лазеров», меня поправляли, что это kind, и нефиг гнать отсебятину в технических статьях. С другим переводом не встречался ни разу
+1
Darkus, #
Вы меня уж извините, но я Вас немного не понял.
+2
megalol, #
Kind не только в мире ФП встречается, но и в других научных статьях. Намного более вероятно, что переведут как «вид» в любом контексте.
+1
Darkus, #
Теперь понял.
+1
jtootf, #
Статья хорошая, но момент с требованием на кайнд мне не нравится: то, что у инстанса должен быть кайнд *- > * не мешает описать нам его для типов с более сложным кайндом. Контрпримеры — Either, a -> b: инстанс определяется игнорированием одного из типов.
+1
laughedelic, #
Простите, но я Вас не очень понял. Если говорить конкретно о классе Functor, то все его воплощения должны иметь вид ∗ → ∗. У вас не получится написать
instance Functor Either where ...
– каков должен тогда быть тип у fmap?
Поясните, пожалуйста, что Вы имели ввиду.
+1
Darkus, #
все его воплощения должны иметь вид — читая, переводил в голове для себя с русского на русский :).
+1
laughedelic, #
Ну ё-моё )= опять ну туда ответил. и что я делаю не так…
+1
Darkus, #
Вы на последний комментарий так отвечаете, поскольку нажимаете на «Написать комментарий», а не на «Ответить», скорее всего.
+1
laughedelic, #
не, точно на «ответить». Но вот когда куда-нибудь отвлечёшься, а потом вернёшься и… бац! не туда ")
0
jtootf, #
Я имел ви виду то, что инстанс функтора можно написать для неоднопараметрического типа — что, собственно, в Prelude и сделано для того же Either: Functor (Either a). Инстанс, естественно, будет однопараметрическим — но сам тип Either имеет кайнд * -> * -> *.
+1
laughedelic, #
instance Functor (Either a) – это да. Только это инстанс для типа (Either a) :: ∗ → ∗, а не для типа Either. Когда Вы дали конструктору типа Either один параметр – это уже другой тип, однопараметрический. Так же как и обычные функции, конструкторы в Haskell каррированные, то можно всегда считать, что они имеют один параметр:
Either :: ∗ → (∗ → ∗)
+1
jtootf, #
Я понимаю. Я, собственно, и имел в виду то, что в статье на этот счёт нет ни слова.
+1
laughedelic, #
Это признаю ") Но я намеренно не касался этой темы, чтобы не пришлось говорить о каррировании – это ведь надо отдельно подробно объяснять, но это не входит в основную тему статьи. Я вроде бы аккуратно обошёл эту тему – примеры функторов с одним параметром. Я рассуждал так, что у того, кто не знает про каррирование скорее всего не возникнет такого вопроса, а тот, кто знает, поймёт сам то, что я написал в комментарии выше – Вы же это понимали ")
+1
laughedelic, #
Вот писал и, Вас поминая, три раза исправлял:
«кайнд» (как было в комментарии jtootf) → «сорт» (как Вы рекомендуете) → «kind» (чтобы не заморачиваться) → ну и наконец «вид» – я подумал, Вы не заметите… (;
+2
Darkus, #
Я всё замечаю :).
+1
648a7844, #
Ответ на упражнение «да», я надеюсь?
+1
laughedelic, #
Не хочется Вас огорчать, но нет, это не так. Подумайте ещё и скажите почему (; а если не получится, я объясню.
+1
648a7844, #
Странно. Но все из пяти «аксиом», приведённых под определением, выполняются.
+1
laughedelic, #
Нет, не все ") Сказать, что не выполняется?
+1
648a7844, #
Да.
+2
laughedelic, #
Не выполняется ассоциативность:
должно быть: f ∘ (g ∘ h) ≡ (f ∘ g) ∘ h
Распишем левую часть:
В скобках: g ∘ h ≡ id ∷ B → B
следовательно: f ∘ (g ∘ h) ≡ f ∘ id ≡ f

Теперь правая часть:
В скобках: f ∘ g ≡ id ∷ A → A
следовательно: (f ∘ g) ∘ h ≡ id ∘ h ≡ h

Получилось, что левая часть – это f, а правая – h, но f ≠ h, т.к. это разные морфизмы (разные стрелки).
Думаю стоит пояснить, почему в скобках получался id. По определению композиции, для любых двух морфизмов с совпадающей областью/кообластью (читай стрелок с общим концом/началом) существует морфизм, называемый их композицией, то есть такая стрелка, что она действует из области первой в кообласть второй:
h ∷ B → A
g ∷ A → B
g ∘ h ∷ B → B
А единственная стрелка из B в B – это id ∷ B → B, значит она и является этой композицией. Аналогично с композицией f ∘ g.

Если что-то не пояснил – спрашивайте (;
+1
648a7844, #
Выходит, если есть в категории существует такая пара объектов А и В, что существует несколько морфизов из А в B, то это уже не категория?
+2
laughedelic, #
Нет, если в данном примере убрать стрелку g, то всё будет в порядке, будет категория с двумя стрелками из B в A. Количество морфизмов не ограничивается таким образом. Просто нужно чтобы они не «конфликтовали» между собой.

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