слово о трансдюсерах
Sep. 21st, 2014 04:41 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonПосмотрел тут свежее выступление известного программиста компьютеров в гамаке Р. Хики. Доклад про трансменьшители.
Помните, во всяких учебниках про ФП есть упражнения по выражению различных функций над списками через fold? Почему именно через fold, а не что-то другое? Да потому что это Котоморфизм Всемогущий: тот самый уникальный морфизм, что идет от инициального объекта к каждому другому, в данном случае в категории алгебр заданного эндофунктора. Ведь что такое список с элементами типа Е? Каждое его значение это либо константа 1 (Nil, [] - ей изоморфны), либо пара (произведение) из Е и аналогичного списка - хвоста. Т.е. 1 + Е*Х. Берем функтор F(X) = 1 + E*X. Нам нужна рекурсивная конструкция, чтобы вместо Х везде был "список из Е", а значит надо ListE = 1 + E * (ListE) = F(ListE). Раз получили ListE = F(ListE), значит нужна неподвижная точка. Построить ее несложно:
newtype Fix f = Fx (f (Fix f))
и для конструктора Fx можно сразу записать обратную функцию
Для всякого эндофунктора F и типа Т, если взять функцию alg: F T -> T, то такая тройка из F, T, и alg называется F-алгеброй. Если F - функтор, т.е. в интересующей нас категории это конструктор типов, то Fix F - уже просто тип, вполне конкретный для данного функтора. Подставив его вместо Т в определение F-алгебры, получим F-алгебру (F, Fix F, alg : F (Fix F) -> Fix F). Сравнив тип alg и Fx выше, видим, что Fx и есть такая алгебра. Утверждается, что эта алгебра для F особенная: она инициальная, т.е. служит инициальным объектом в категории F-алгебр для F, т.е. для любой другой алгебры в нем, т.е. любой пары из типа Т и функции alg : F T -> T существует функция g из инициального объекта Fix F в T. Да такая, что вот эта диаграмма коммутирует, т.е. оба пути из f (Fix f) в Т эквивалентны:
Почему такая g существует? Да потому что мы можем взять обратную для Fx функцию unFix, и просто определить g как композицию из unFix, fmap g и alg:
Поскольку g зависит от alg, опишем это как функцию g = cata alg:
Это работает для произвольного эндофунктора, так можно опрелять самые разные рекурсивные индуктивные типы, и катаморфизм для них всегда будет работать сверткой: он позволяет из значения рекурсивного типа (скажем, AST-дерева или списка) получить значение произвольного типа (например, строку), если есть функция-алгебра, умеющая делать один шаг свертки. Например, если у нас есть список интов, и мы хотим его превратить в строку, то
E = Int
F(X) = 1 + Int * X
List_Int = Fix F = 1 + Int * List_Int
T = String
alg : F T -> T = 1 + Int * String -> String
т.е. alg должна уметь делать строку из ничего (1, пустой список) и из пары элемент * строка, где та строка получена из хвоста списка этой же операцией рекурсивно. Передав такую алгебру в котоморфизм cata, получим функцию Fix f -> a т.е. List_Int -> String. Узнаете? Этот котоморфизм и есть foldr для списка! Все, что можно сделать из списка (по крайней мере операциями вроде alg - берущими по одному элементу и некоторым образом наращивающими свой результат), можно сделать fold'ом. Более того, если мы хотим выразить алгебраический тип в языке без оных но с функциями, можно использовать Church encoding или типизированный Boehm-Berarducci encoding, и результат будет выглядить точно как тот fold. А алгебра, что передается в катаморфизм, получила у Хики новое имя - reducerинновация!.
Ну так вот, увидел Хики, что fold это хорошо, но заметил, что реализуя через него операции над списками мы почему-то используем конструкторы списка. А при реализации оных для векторов - конструкторы векторов. Непорядок, недообобщение!
Только один-то конструктор он заметил, а про второй забыл:
Если conj заменить на построитель не-векторов, а [] оставить, будет банальная ошибка типов. В этой его кложури - еще и в рантайме. Ибо про функторы с алгебрами не думал, там-то тип сразу показывает о каких вариантах надо заботиться. Ну и предложил абстрагироваться, вынести конструктор из кода в параметр:
Получилось, что внутри там функция принимает такой конструктор (вроде cons или conj), фрагмент алгебры, a.k.a. reducer, и возвращает такой же. Ну а функции вида Хрень -> Хрень хорошо композятся. Придумал для такого преобразования reducer -> reducer новое имя: transducerинновация!. Но поскольку половину алгебры он в самом начале потерял, в таком виде оно не работает, конечно. Пришлось добавлять хаки. Хак первый: писал он на кложури, а она позволяет функции принимать разное число аргументов и в зависимости от этого вести себя по-разному. Ну и сделал, что ежели аргументов не дали, то пусть работает как вторая половина алгебры: пусть возвращает значение, соответствующее пустому списку. А еще захотел уметь прерывать обработку, не доходя до конца списка. Всякие хаскели это в foldr делают легко за счет ленивости: не обращайся к вычисленному хвосту, он и не будет вычисляться. А в кложури все иначе, поэтому сделал сигналирование о конце заворачиванием значения в специальную обертку, такой вот модный динамически-типизированный способ передать булев флаг. Ну и сделал третий вариант функции от двух аргументов, принимающий лишь один аргумент, в таком случае там она что-то сигналирует. В результате то, что выглядит как композиция функций, есть композиция троек функций (от 0, 1 и 2 аргументов), работающих с неожиданно типизированными вещами. Теперь весь мир побежал это дело переписывать на другие языки. Но мы-то знаем, что, учитывая форму этих алгебр-уменьшателей, речь все равно только о списках и эквивалентных им вещах, и поскольку среди всех таких структур список - самый общий (свободный моноид, панимаиш), то все эти трансменьшители сводятся к такому типу:
transducer: [a] -> [b]
Зато инновации!
Помните, во всяких учебниках про ФП есть упражнения по выражению различных функций над списками через fold? Почему именно через fold, а не что-то другое? Да потому что это Котоморфизм Всемогущий: тот самый уникальный морфизм, что идет от инициального объекта к каждому другому, в данном случае в категории алгебр заданного эндофунктора. Ведь что такое список с элементами типа Е? Каждое его значение это либо константа 1 (Nil, [] - ей изоморфны), либо пара (произведение) из Е и аналогичного списка - хвоста. Т.е. 1 + Е*Х. Берем функтор F(X) = 1 + E*X. Нам нужна рекурсивная конструкция, чтобы вместо Х везде был "список из Е", а значит надо ListE = 1 + E * (ListE) = F(ListE). Раз получили ListE = F(ListE), значит нужна неподвижная точка. Построить ее несложно:
newtype Fix f = Fx (f (Fix f))
и для конструктора Fx можно сразу записать обратную функцию
unFix :: Fix f -> f (Fix f) unFix (Fx x) = x
Для всякого эндофунктора F и типа Т, если взять функцию alg: F T -> T, то такая тройка из F, T, и alg называется F-алгеброй. Если F - функтор, т.е. в интересующей нас категории это конструктор типов, то Fix F - уже просто тип, вполне конкретный для данного функтора. Подставив его вместо Т в определение F-алгебры, получим F-алгебру (F, Fix F, alg : F (Fix F) -> Fix F). Сравнив тип alg и Fx выше, видим, что Fx и есть такая алгебра. Утверждается, что эта алгебра для F особенная: она инициальная, т.е. служит инициальным объектом в категории F-алгебр для F, т.е. для любой другой алгебры в нем, т.е. любой пары из типа Т и функции alg : F T -> T существует функция g из инициального объекта Fix F в T. Да такая, что вот эта диаграмма коммутирует, т.е. оба пути из f (Fix f) в Т эквивалентны:
Почему такая g существует? Да потому что мы можем взять обратную для Fx функцию unFix, и просто определить g как композицию из unFix, fmap g и alg:
Поскольку g зависит от alg, опишем это как функцию g = cata alg:
cata :: Functor f => (f a -> a) -> Fix f -> a cata alg = alg . fmap (cata alg) . unFix
Это работает для произвольного эндофунктора, так можно опрелять самые разные рекурсивные индуктивные типы, и катаморфизм для них всегда будет работать сверткой: он позволяет из значения рекурсивного типа (скажем, AST-дерева или списка) получить значение произвольного типа (например, строку), если есть функция-алгебра, умеющая делать один шаг свертки. Например, если у нас есть список интов, и мы хотим его превратить в строку, то
E = Int
F(X) = 1 + Int * X
List_Int = Fix F = 1 + Int * List_Int
T = String
alg : F T -> T = 1 + Int * String -> String
т.е. alg должна уметь делать строку из ничего (1, пустой список) и из пары элемент * строка, где та строка получена из хвоста списка этой же операцией рекурсивно. Передав такую алгебру в котоморфизм cata, получим функцию Fix f -> a т.е. List_Int -> String. Узнаете? Этот котоморфизм и есть foldr для списка! Все, что можно сделать из списка (по крайней мере операциями вроде alg - берущими по одному элементу и некоторым образом наращивающими свой результат), можно сделать fold'ом. Более того, если мы хотим выразить алгебраический тип в языке без оных но с функциями, можно использовать Church encoding или типизированный Boehm-Berarducci encoding, и результат будет выглядить точно как тот fold. А алгебра, что передается в катаморфизм, получила у Хики новое имя - reducerинновация!.
Ну так вот, увидел Хики, что fold это хорошо, но заметил, что реализуя через него операции над списками мы почему-то используем конструкторы списка. А при реализации оных для векторов - конструкторы векторов. Непорядок, недообобщение!
Только один-то конструктор он заметил, а про второй забыл:
Если conj заменить на построитель не-векторов, а [] оставить, будет банальная ошибка типов. В этой его кложури - еще и в рантайме. Ибо про функторы с алгебрами не думал, там-то тип сразу показывает о каких вариантах надо заботиться. Ну и предложил абстрагироваться, вынести конструктор из кода в параметр:
Получилось, что внутри там функция принимает такой конструктор (вроде cons или conj), фрагмент алгебры, a.k.a. reducer, и возвращает такой же. Ну а функции вида Хрень -> Хрень хорошо композятся. Придумал для такого преобразования reducer -> reducer новое имя: transducerинновация!. Но поскольку половину алгебры он в самом начале потерял, в таком виде оно не работает, конечно. Пришлось добавлять хаки. Хак первый: писал он на кложури, а она позволяет функции принимать разное число аргументов и в зависимости от этого вести себя по-разному. Ну и сделал, что ежели аргументов не дали, то пусть работает как вторая половина алгебры: пусть возвращает значение, соответствующее пустому списку. А еще захотел уметь прерывать обработку, не доходя до конца списка. Всякие хаскели это в foldr делают легко за счет ленивости: не обращайся к вычисленному хвосту, он и не будет вычисляться. А в кложури все иначе, поэтому сделал сигналирование о конце заворачиванием значения в специальную обертку, такой вот модный динамически-типизированный способ передать булев флаг. Ну и сделал третий вариант функции от двух аргументов, принимающий лишь один аргумент, в таком случае там она что-то сигналирует. В результате то, что выглядит как композиция функций, есть композиция троек функций (от 0, 1 и 2 аргументов), работающих с неожиданно типизированными вещами. Теперь весь мир побежал это дело переписывать на другие языки. Но мы-то знаем, что, учитывая форму этих алгебр-уменьшателей, речь все равно только о списках и эквивалентных им вещах, и поскольку среди всех таких структур список - самый общий (свободный моноид, панимаиш), то все эти трансменьшители сводятся к такому типу:
transducer: [a] -> [b]
Зато инновации!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-09-29 12:40 pm (UTC)Вы не поняли, оно СПЕЦИАЛЬНО убрано в отдельный тайпкласс, потому что как раз если объединить все в один, то работать аналогично оригиналу оно не будет :)
Отдача empty редюсером не композится (как может вообще композиться нульарная функция, нэ?). Просто элемент empty передается в итоговый фолд для того, чтобы определить тип результата свертки (один единственный раз!). Когда вы пишете:
fold (xf conj) empty coll
то у вас пара (empty, conj) задает функтор, который ВЕРНЕТ этот фолд и определяет, в некотором смысле, интерфейс конструкции, а пара (fold, coll) задает ПРИНИМАЕМЫЙ функтор и определяет интерфейс деконструкции. И это разные функторы. То есть мы можем дать на вход список и получить вектор. Или наоборот. Если вы засунете это дело в один тайпкласс то у вас будет один функтор с соответствующей реализацией и нельзя будет сфолдить коллекцию одного типа в коллекцию другого.
То есть empty композить не нужно, так же как не нужно композить conj. Мы просто берем некоторый Transducer b a, указываем Foldable функтор входа, Conjable функтор выхода и получаем fun: (Foldable f, Conjable g) => f a -> g b
То есть там действительно косяк - но не столь серьезныЙ, он в ф-и xlist, которая должна быть:
xlist: (Foldable f, Conjable g) => Transducer b a -> f a -> g b
no subject
Date: 2014-09-29 01:18 pm (UTC)Как только определена начальная алгебра с катаморфизмом, нам уже больше не нужны сами алгебры - т.к. есть естественная биекция между стрелками из начальной алгебры в другие и другими алгебрами, то есть мы можем определить любую алгебру как эту стрелку. Применяя наш катаморфизм к конкретному трансдьюсеру, мы и получаем такую стрелку (или алгебру). То есть мы можем композировать стрелки в категории F-алгебр и только их, все. Нам абсолютно пофиг чо там с редюсерами. Их вообще нет. Мы их не видим, не знаем, не щупаем. Только стрелки, только хардкор. По-этому не важно как и чего там определены редьсюры - а хоть бы и не определены вообще.
no subject
Date: 2014-09-29 02:38 pm (UTC)Каждый конкретный редюсер знает тип элементов, с которым работает (например, он прибавляет единицы - значит работает с интами). По Хики, мы можем написать такой редюсер, который берет последовательность интов, умножает каждый из них на два, а в конец дописывает 3,2,1. Ибо его можно вызвать без аргументов, и тогда он вернет этот заготовленный хвост.
Кстати, редюсеры как раз работают в фиксированном функторе.
От этого Хики абстрагируется, передавая empty и conj функтора-результата в виде редюсера на вход, получив тем самым трансменьшитель.
Результат трансменьшителя, будучи вызван с 0 аргументов, способен вернуть [3,2,1], используя конструкторы empty и conj из переданного ему на вход редюсера.
В "переводе" на хаскель сделали все не так, и потому неправильно.
no subject
Date: 2014-09-29 03:16 pm (UTC)Мы получаем редьюсеры, после применения катаморфизма к инициальной алгебре в виде стрелок из этой алгебры. Иначе говоря - единственное место, где мы пишем редьюсер, это в выборе той самой алгебры, а там нам никто не мешает указать empty. Еще раз - это _единственное_ место где мы описываем алгебру и там мы ее описываем вполне корректно как алгебру. Остальные алгебры (редьюсеры) получаем как стрелки из инициальной в нужную, НЕ ПИШЕМ! То есть как выделенные стрелки в категории F-алгебр: (f a -> b ~ (b, b*a -> b)) <=> (f a ~ List a). Внутри самих трансдьюсеров мы empty не используем.
То есть вам никто не мешает определить редьюсер Conjable так, чтобы он дописывал в конец [1,2,3] (просто задать empty = [1,2,3]), и полученная алгебра кстати будет так же инициальной, а потом вызываем на ней наш fold, задавая нужный результирующий тип (чтобы получился нужный инстанс Conjable).
no subject
Date: 2014-09-30 06:30 am (UTC)Посмотрите на композицию из нескольких трансменьшителей. Первый берет некоторый редюсер (алгебру с conj и empty), превращает ее в другой редюсер, его получает следующий трансменьшитель и превращает в третий и т.д. Каждый из них волен вызывать empty из предыдущего редюсера. Каждый из них волен описать свой empty, который будет отдан следующему трансменьшителю. В результате, в частности, каждый может дописать что-то в конец последовательности. Если же empty вынесена в Conjable и используется лишь единожды в fold'e, то ничего подобного не выходит. Т.е. проблема все та же - алгебру не всю передают, и потому нормального морфизма алгебр не выходит.
no subject
Date: 2014-09-30 08:48 am (UTC)Нет :) Empty вызывается только в самом начале. Внутри их вызывать нлеьзя. И редьюсеры тоже вызывать нельзя :)
Вообще забудьте, что трансдьюсер возвращает редьюсер. Он мог бы и не возвращать :) Это просто случайность, и нам на нее плевать, важно то, что мы при помощи cata alg можем превратить трансдьюсер в алгебру.
> Т.е. проблема все та же - алгебру не всю передают
Как же не всю? В том месте, где передают алгебру (при вызове фолда) - ее передают всю. И это единственное место, где вообще надо что-то знать об алгебрах. Мы работаем не с алгебрами (редьюсерами), а с трандьюсерами. И весь смысл именно в этом, потому что трансдьюсеры лучше и удобнее чем алгебры. При этом имея трансдьюсер (который получается прямым написанием, комбинированием существующих, или является cata alg), мы можем засунуть его в cata alg и получить алгебру (опять-таки - полноценную алгебру, то есть с empty) в виде ф-и, которая уже напрямую применяется к данным.
> и потому нормального морфизма алгебр не выходит.
Где он не выходит-то? Котоморфизм - он по определению "нормальный морфизм алгебр" (и сам по себе нормальная алгебра). Если не выходит - значит ваш котоморфизм не котоморфизм, на самом деле?
ЗЫ: конечно вполне допускаю что ошибся и понял идею Хики не так, можете тогда скинуть ссылку, где он empty в трансдьюсерах вызывает?
no subject
Date: 2014-09-30 09:30 am (UTC)Почему нельзя, кто сказал?
Редюсеры не может быть нельзя вызывать - кроме них там больше и нечего вызывать. См. примеры трансдюсеров на слайдах в посте.
>Вообще забудьте, что трансдьюсер возвращает редьюсер. Он мог бы и не возвращать :) Это просто случайность
Нет, напротив, это его определение.
Еще раз, на всякий случай:
редюсер - алгебра (alg), всякий редюсер содержит и conj и empty.
fold - cata (еще не катаморфизм, но шаблон для него)
передача редюсера в fold дает котоморфизм (cata alg)
no subject
Date: 2014-09-30 10:17 am (UTC)А какой в этом вообще может быть смысл? То есть вообще тот факт что редьюсер может вернуть empty - не более чем сахарок, который запилен "а потому что в кложуре так можно". То есть если мы даже и вернем такое - это будет просто константный трансдьюсер, а потом можно просто в конце укзаать нужный тип и получится тот же результат. То есть все равно оказывается, что алгебру надо передать единожды.
> Редюсеры не может быть нельзя вызывать - кроме них там больше и нечего вызывать.
Имелся ввиду empty-редьюсер. Есть хоть один пример вызова нульарного редьюсера внутри ветки трансдьюсера, которая отвечает за генерацию редьюсера с 2 аргументами?
> Нет, напротив, это его определение.
Нам трансдьюсеры нужны только постольку, поскольку:
1. мы можем легко делать из трансдьюсеров алгебры, то есть можно заменить алгебры трансдьюсерами, при этом трансдьюсеры лучше алгебр, потому что:
2. трансдьюсеры естественным образом композятся, алгебры - не композятся в принципе никак.
3. определяя алгебру мы определяем алгебру, определяя трансдьюсер - мы сразу определяем _много_ алгебр (по одной для каждой пары cata/alg)
4. некоторые трансдьюсеры сами являются катаморфизмами, определять такие - двойной профит
При этом тот факт, что трансдьюсер на самом деле принимает и возвращает редьюсеры (алгебры), нам не важен совершенно. Ну возвращает и возвращает. Мог бы и не возвращать - если условия 1-4 выполнены, то все ок.
> передача редюсера в fold дает котоморфизм (cata alg)
Угу. При этом котоморфизм - сам является полноценной алгеброй (с empty и conj). А находящийся внутри трансдьюсер (который применяем к conj) эти котоморфизмы прааметризует - на каждый трансдьюсер по котоморфизму-алгебре. Таким образом мы даем на вход алгебру (с empty/conj) получаем на вхыоде алгебру (с empty/conj). Редьюсеров нет вообще (в "канонической" форме, катаморфизм представляет редьюсер уже в виде готовой свертки) - то есть задача, которой мы хотели достигнуть (избавиться от алгебр, т.к. с ними работать неудобно) решена. Profit, не?
ЗЫ: давайте еще вспомним, что тайпкласс - это на самом деле неявный аргумент, и этот аргумент (с empty и conj) будет абсолютно везде пролезать в ф-ях, куда попал соответствующий тип. То есть все передается, на самом-то деле, как в кложуре, просто неявно.