слово о трансдюсерах
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-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) будет абсолютно везде пролезать в ф-ях, куда попал соответствующий тип. То есть все передается, на самом-то деле, как в кложуре, просто неявно.