Интересно, какой диалект Хаскелла там освещается?
1) Необычное определение Maybe a = No | Yes a, вместо Nothing | Just a. Ну допустим, это чисто для иллюстрации.
2) Классы Monad (полугруппа) и Monad0 (моноид)
3) логичное имя для операции сложения — (++), вместо mplus. Удачно складывается то, что конкатенация списков — это и есть сложение в монаде List.
Здравствуйте, Кодт, Вы писали:
К>Интересно, какой диалект Хаскелла там освещается?
Gofer
Gofer может рассматриваться как экспериментальный диалект Haskell. Интерпритатор HUGS первоначально был разработан как реализация Gofer. В Настоящее время полностью влился в Haskell и не существует как самостоятельный язык. Однако часто упоминается в старых публикациях.
Прочёл сейчас статьи про фолды и монады. Понял, что не догоняю базиса. Не, про каждую букву отдельно всё ясно — а вот идею пОнять...
1) Что есть фолд?
Тот факт, что фолд подчиняется некоторым очевидным законам — навевает мысли о том, что это какая-то сущность из абстрактной алгебры.
Не изоморфизм, поскольку отображает структурную монаду в любую другую монаду, какую ему подсунешь в аргументы. Например, в Id.
2) Можно ли фолды классифицировать?
К примеру, у всех монад есть одни и те же функции (по-разному реализованные). Что и даёт Functor => Monad => MonadPlus.
3) Где бы и что бы такое почитать, про теорию категорий или про что угодно относящееся к этому делу, чтобы
— было не заумно
— более-менее практично, т.е. показывалось, как та или иная абстрация проявляется в прикладной задаче (и зачем эту абстракцию проявлять)
У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.
А для чего тогда прямо в Прелюдии есть классы Functor и Arrow? Чисто для красоты и общности, или же чем-то полезны? Это как минимум.
Здравствуйте, Кодт, Вы писали:
К>1) Что есть фолд? К>2) Можно ли фолды классифицировать? К>3) Где бы и что бы такое почитать, про теорию категорий или про что угодно относящееся к этому делу, чтобы К>- было не заумно
Текстов на эту тему полно, например, классические:
1. Erik Meijer, Maarten Fokkinga, Ross Paterson,
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
2. Erik Meijer, Graham Hutton
Bananas in Space: Extending Fold and Unfold to Exponential Types
Небольшой траверс и, можно даже сказать, дюльфер.
A>1. Erik Meijer, Maarten Fokkinga, Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
1 Introduction
There is a well-known Chinese proverb: (one cannot have both fishes and bear palms at the same time), implying that one can hardly obtain two treasures simultaneously.
Японские учёные для мирового сообщества приводят в английском тексте китайскую поговорку, суть которой — нельзя одновременно ухватить два предмета. Воистину, чтобы понять рекурсию...
К>Японские учёные для мирового сообщества приводят в английском тексте китайскую поговорку, суть которой — нельзя одновременно ухватить два предмета. Воистину, чтобы понять рекурсию...
К>Впрочем, остальной текст вменяемый.
Здравствуйте, O N A, Вы писали:
К>>Японские учёные для мирового сообщества приводят в английском тексте китайскую поговорку, суть которой — нельзя одновременно ухватить два предмета. Воистину, чтобы понять рекурсию...
К>>Впрочем, остальной текст вменяемый.
ONA>Японские...
Ну, я по двум последним соавторам судил... А только потом вчитался в имя первого
Здравствуйте, Кодт, Вы писали:
К>1) Что есть фолд? К>Тот факт, что фолд подчиняется некоторым очевидным законам — навевает мысли о том, что это какая-то сущность из абстрактной алгебры. К>Не изоморфизм
Катаморфизм, ссылку на Meijer-а уже дали.
Вкратце, это из теории категорий. Я её не знаю (как большинство, листал по диагонали), поэтому своими словами.
Сначала общее определение.
F-алгебра эндофунктора F (т.е. функтора из категории в саму себя) — это пара объект A из категории C и морфизма FA -> A. Функтор F, разумеется, из категории C в C.
Катаморфизм — это такой гомоморфизм f initial F-алгебры (A,a) в F-алгебру (B,b) (оба объекта, несмотря на то, что сами являются категориями входят в общую категорию F-алгебр), где
f . а = b . Ff
Если проверить по морфизмам "отсюда-туда", то всё сходится: f . a — это морфизм FA -> B, морфизм b . Ff тоже.
Т.е. если мы имеем стандартный катаморфизм для списка, то есть мы сворачиваем [a] -> r, то можно провести здесь аналогию: data [a] == F, a == A, r == B. Тогда для свёртки нам надо каждый конструктор [a] иметь возможность сворачивать. Этот морфизм (?) является группой функций, у которых параметры — это параметры конструктора данных, за исключением рекурсивных — для них уже катаморфизм есть — это то, что мы определяем, поэтому можно взять финальный тип r.
Т.е. для [] : r, для (:) a [a] : a -> r -> r.
cata :: algebra -> object -> result
Для списка
cata :: (r, a -> r -> r) -> [a] -> r
cata (f,_) [] = f
cata alg@(_,f) (x:xs) = f x (cata alg xs)
В принципе, поскольку катаморфизм единственен, то он выводим из конструкторов (по описанной схеме) и его можно сгенерить на Generics или там TH.
Тут что интересно — foldr согласно этому является катаморфизмом, а foldl — нет. Хотя может я и вру.
С другой стороны, ведь foldl можно выразить через foldr, а наоборот нет.
К>2) Можно ли фолды классифицировать? К>К примеру, у всех монад есть одни и те же функции (по-разному реализованные). Что и даёт Functor => Monad => MonadPlus.
Фолд — это же всего одна функция. Для каждого типа её тип может отличаться. Что тут классифицировать?
К>3) Где бы и что бы такое почитать, про теорию категорий или про что угодно относящееся к этому делу, чтобы К>- было не заумно К>- более-менее практично, т.е. показывалось, как та или иная абстрация проявляется в прикладной задаче (и зачем эту абстракцию проявлять)
Эх! Сам ищу постоянно :-(
К>У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.
Есть такое мнение, думаю, оно несправедливо.
К>А для чего тогда прямо в Прелюдии есть классы Functor и Arrow? Чисто для красоты и общности, или же чем-то полезны? Это как минимум.
Здравствуйте, lomeo, Вы писали:
L>Вкратце, это из теории категорий. Я её не знаю (как большинство, листал по диагонали), поэтому своими словами. L>Сначала общее определение.
Ужасужасужас. Мне бананов с разлохмаченными проводами хватило.
L>Тут что интересно — foldr согласно этому является катаморфизмом, а foldl — нет. Хотя может я и вру.
Естественно. foldr заменяет конструкторы на аппликации. А поскольку (:) правоассоциативен, то имеем что имеем.
L>С другой стороны, ведь foldl можно выразить через foldr, а наоборот нет.
Почему это нельзя?
Если по-тупому, то вспомним snoc-списки (для которых foldl является катаморфизмом) и вспомним, как snoc- и cons-списки между собой связаны (зеркальны).
foldr f a xs = foldl (flip f) a (reverse xs)
foldl f b xs = foldr (flip f) b (reverse xs)
Можно попробовать выразить foldl как хиломорфизм...
А собственно, это и сделано:
foldl = (| (flip f), a |) * [( reverse )] -- извините, reverse как анаморфизм распотрошить сходу не вспомнил
К>>2) Можно ли фолды классифицировать? К>>К примеру, у всех монад есть одни и те же функции (по-разному реализованные). Что и даёт Functor => Monad => MonadPlus.
L>Фолд — это же всего одна функция. Для каждого типа её тип может отличаться. Что тут классифицировать?
А фиг знает, если честно. Были бы С++, написал бы type traits, по которым для каждого типа установил бы типы ката- и анаморфизмов.
Мне просто нравится идея того, что параметры морфизма можно завернуть в один кортеж, и установить функции
catamorphism_args `catamorphism` container = result
anamorphism_args `anamorphism` seed = container
Но это, похоже, вылезает слишком далеко за пределы системы типов хаскелла.
К>>У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.
L>Есть такое мнение, думаю, оно несправедливо.
Ну и как эту несправедливость побороть?
К>>А для чего тогда прямо в Прелюдии есть классы Functor и Arrow? Чисто для красоты и общности, или же чем-то полезны? Это как минимум.
L>Arrow нет в прелюдии.
Здравствуйте, Кодт, Вы писали:
К>Ужасужасужас. Мне бананов с разлохмаченными проводами хватило.
Пардон, сам пробиваюсь с трудом
L>>С другой стороны, ведь foldl можно выразить через foldr, а наоборот нет.
К>Почему это нельзя?
Нельзя. Твой foldr через foldl неверный.
Хотел написать почему, потом подумал, что тебе будет интересно найти самому причину.
Кстати, определение foldl через foldr также некорректно.
К>Можно попробовать выразить foldl как хиломорфизм... К>А собственно, это и сделано: К>
К>foldl = (| (flip f), a |) * [( reverse )] -- извините, reverse как анаморфизм распотрошить сходу не вспомнил
К>
Имхо, reverse через операцию анаморфизма выразим по дурацки — проход надо делать справа налево для корректного сбора. Отрывать надо init, т.е. должно быть [( \xs -> (last xs, init xs), null )] Очень неэффективно. Разумеется можно объединить получение last/init в один проход, но всё равно память использоваться будет квадратно.
Поскольку reverse операция законченная (надо дойти до конца списка), то её лучше делать foldl. Или, что то же самое — foldr, т.к. foldl через него выразим.
К>>>2) Можно ли фолды классифицировать? К>>>К примеру, у всех монад есть одни и те же функции (по-разному реализованные). Что и даёт Functor => Monad => MonadPlus.
L>>Фолд — это же всего одна функция. Для каждого типа её тип может отличаться. Что тут классифицировать?
К>А фиг знает, если честно. Были бы С++, написал бы type traits, по которым для каждого типа установил бы типы ката- и анаморфизмов. К>Мне просто нравится идея того, что параметры морфизма можно завернуть в один кортеж, и установить функции
К>
К>Но это, похоже, вылезает слишком далеко за пределы системы типов хаскелла.
Не вылезает.
class Cata c where
cata :: m -> c -> r
Ну разве что нельзя представить в системе типов, что m зависит от c.
Только толку то. Катаморфизм то для каждого типа всё равно надо писать. Или генерить
К>>>У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.
L>>Есть такое мнение, думаю, оно несправедливо.
К>Ну и как эту несправедливость побороть?
А надо? Если серьёзно, то "статьи по тому же Хаскеллу" — имеются в виду туториалы? Если да, то я больше встречал с монадами, если нет, то не монадами едиными...
L>>Arrow нет в прелюдии.
К>Control.Arrow — это за пределами прелюдии?
Здравствуйте, Трурль, Вы писали:
Т>на бесконечных списках загнется.
С другой стороны, это неважно, так как формально foldr определен на свободной алгебре, а бесконечные списки в неё не входят.
Здравствуйте, lomeo, Вы писали:
L>Это не анаморфизм.
Точно, но там речь шла о том, чтобы выразить foldr через foldl.
Делать reverse через анаморфизм действительно глупо получается.
Зато у меня получлся "обобщенный анаморфизм"
ana q r p f g x = if p x then r x else q (f x) (ana q r p f g (g x))
unfold = ana (:) (\x->[])
fold f z = ana f (\x->z) null head tail
Здравствуйте, Трурль, Вы писали:
Т>>на бесконечных списках загнется. Т>С другой стороны, это неважно,
??
T>так как формально foldr определен на свободной алгебре, а бесконечные списки в неё не входят.
Можно ссылку? Я просто не знаю, что такое свободная алгебра.
А так да — конечный список можно представить как initial (кто нибудь перевод знает?) алгебру (правда, я не понимаю, почему точно так же не представим бесконечный?). И следовательно можно над этим типом данных определить катаморфизм.
Здравствуйте, Трурль, Вы писали:
Т>Зато у меня получлся "обобщенный анаморфизм" Т>
Т>ana q r p f g x = if p x then r x else q (f x) (ana q r p f g (g x))
Т>unfold = ana (:) (\x->[])
Т>fold f z = ana f (\x->z) null head tail
Т>
Это у тебя обобщённый преобразователь откуда-хочешь в куда-хочешь :-) Анаморфизм — операция обратная катаморфизму, т.е. порождающая сложную структуру из начального значения a -> t b c двумя функциями — предикатом (a -> Bool) и генератором полей конструктора (кроме рекурсивных — b) и нового начального значения (a -> (a, ...)). Причем порождение должно быть конструкторами, поэтому твоё определение очень напоминает hylo, только ещё более общее (остановку порождает элемент исходного типа — r x).
На самом деле для примитивной рекурсии подходит параморфизм (это такой усложненный fold, функции-параметру которого передаётся ещё и сам список, а не только голова). Unfold, правда через него не выразишь.
Я так понимаю, что гиломорфизм (хиломорфизм?) — обощение анаморфизма, параморфизм — катаморфизма. Разница — в использовании фунций вместо конструкторов. У тебя, так ещё и конечное значение — не значение, а вычисление, т.к. обощение анаморфизма и параморфизма. Трурлеморфизм. Дальше вроде некуда :-)
Здравствуйте, lomeo, Вы писали:
L>Можно ссылку?
На бананы? L>Я просто не знаю, что такое свободная алгебра. L>А так да — конечный список можно представить как initial (кто нибудь перевод знает?) алгебру
Cвободная алгебра — алгебраисткий термин для того, что категористы называют инициальной алгеброй или инициальным объектом. L>(правда, я не понимаю, почему точно так же не представим бесконечный?).
По определению термы не могут быть бесконечными. Да и как можно определить, скажем, сумму бесконечного списка?
Смысл в том, что они объединяют конечные списки как initial algebra в одной категории и final co-algebra в другой (но близкой) в одну алгебру. Приводят кучу законов (в частности там есть и ката/ана морфизмы и различные fusion-ы).
Здравствуйте, lomeo, Вы писали:
L>Я так понимаю, что гиломорфизм (хиломорфизм?) — обощение анаморфизма, параморфизм — катаморфизма. Разница — в использовании фунций вместо конструкторов.
Все эти ката- ана- и пара- легко получаются из хило-. Последний можно рассматривать как общий шаблон итеративного вычисления.
Катаморфизм получается когда вычисления управляются данными алгебраического типа, анаморфизм — когда результат алгебраического типа.
Перекуём баги на фичи!
(one cannot have both fishes and bear palms at the same time), implying that one can hardly obtain two treasures simultaneously.
Ну разве что нельзя представить в системе типов, что m зависит от c.
