DC>Now, the question is whether we can write this in fold notation. First, we can apply eta reduction to the first line to give:
DC>
DC>(++) [] = id
DC>
DC>Несколько не понял выделенную замену, что она дает и как её понимает компилятор.
Все просто. Эта-конверсия (http://en.wikipedia.org/wiki/Lambda_calculus#.CE.B7-conversion) — это преобразование лямбда-выражений. Если f — функция, то очевидно, что f эквивалентно \x -> f x. Эта-редукция — применение этого правила с избавлением от лишней лямбда-абстракции, т.е. замена \x->f x на f.
Теперь рассмотрим уравнение (++) [] ys = ys.
Его можно переписать как (++) [] = \ys -> ys (правило простое: f x = e всегда можно заменить на f = \x -> e).
\ys -> ys — это, очевидно, функция, возвращающая свой аргумент без изменения, в стандартной библиотеке называется id. Таким образом мы и пришли к
(++) [] = id
DC>
DC>Through a sequence of steps, we can also eta-reduce the second line:
Здесь тоже все на месте. (++) xs — это пример частичного применения. В результате получается функция, которая получает аргумент list и возвращает xs ++ list.
(x: ) — это функция, которая принимае список list и возвращает список с добавленным элементом (x:list).
Композиция этих функций ( (x: ) . (++) xs ), получая аргумент list, сначала вычисляет xs ++ list, затем добавляет новую голову x.
PM>Здесь тоже все на месте. (++) xs — это пример частичного применения. В результате получается функция, которая получает аргумент list и возвращает xs ++ list.
Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно
такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Здравствуйте, dr.Chaos, Вы писали:
DC>Вот решил посмотреть чисто функциональный язык. Выбрал Haskell .
DC>Вот читаю YAHT.
DC>Возникла пара вопросов по сокращению записи функций:
DC>1. Есть пример как выразить ф-ю filter с помощью foldr (7.12)
DC>
DC>
DC>filter p [] = []
DC>filter p (x:xs) =
DC>if p x
DC>then x : filter p xs
DC>else filter p xs
DC>...
DC>Now, suppose that we call the result of calling filter p xs simply b, then we can rewrite this as:
DC>
DC>filter p [] = []
DC>filter p (x:xs) =
DC>if p x then x : b else b
DC>filter p = foldr (\a b -> if p a then a:b else b) []
DC>
DC>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs
По-моему, это сказано, чтобы просто пояснить переход от рукописной рекурсии к рекурсии, уже встроенной в fold. Компилятору это понимать не надо. Функция
foldr :: (a -> b -> b) -> b -> [a] -> b
работает так
foldr op r [x, y, z] это x `op` (y `op` (z `op` r))
Выражение (foldr op r) имеет тип [a] -> b, то есть ожидает списка, чтобы его свернуть. У нас r — это пустой список, а функция op, реализованная через лямбду,
\a b -> if p a then a:b else b
имеет тип
a -> [a] -> [a]
и при выполнении предиката добавляет свой первый аргумент в голову второго, а при невыполнении — нет. При выполнении каждого `op` в цепочке наша лямбда делает свою работу, формируя отфильтрованный список.
Здравствуйте, dr.Chaos, Вы писали:
DC>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно DC>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?
Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара. Инфиксный оператор, взятый в скобки, превращается в обычную функцию, т.е.
Здравствуйте, dr.Chaos, Вы писали:
DC>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs
Это следует из определения foldr.
DC>Несколько не понял выделенную замену, что она дает и как её понимает компилятор.
Эта не замена, это применение эта-редукции к строке [] ++ ys = ys. Компилятор как понимает не знаю, тут автор не об этом говорит (насколько я понял), а о замене сверткой рекурсивного определения функции над списком. Дает она
DC>==> (++) (x:xs) ys = ((x . (++) xs) ys --Здесь может имелось в виду ((x . (++)) xs ys?
Нет. Т.к. из
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(x:) :: [t] -> [t]
следует, что
((x:) .) :: (a -> [t]) -> (a -> [t])
А т.к. второй параметр у нас
(++) :: [t] -> [t] -> [t],
то подставить его как значение типа (a -> [t]) мы не сможем, т.к. [t] не ложится на [t] -> [t]
Что касается самой темы — перевод определения (++) в свёртку, то тут проще рассуждать так.
Свёртка для нулевого списка (первый аргумент) возвращает второй список. Т.е. мы можем просто считать, что второй аргумент (ys) — это начальный элемент свертки (т.е. тот, который возвращается, если список свертки пустой), а первый (xs) и есть собственно сворачиваемый список:
xs ++ ys = foldr f ys xs
где нам надо найти f. Т.к. foldr пробегается справа налево по xs:
f x0 (f x1 (f x2 ... (f xN ys)))
то логично предположить, что f — это просто конструктор списка (. Тогда
xs ++ ys = foldr (:) ys xs
или
(++) = flip (foldr (:))
Это интуитивный вывод определения, можно сделать вывод более формально, без всех этих "можно заметить", "логично предположить".
Здравствуйте, dr.Chaos, Вы писали:
DC>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно DC>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?
У функций по умолчанию префиксная запись, т.е. они записываются перед аргументами. Однако, её можно сделать инфиксной, если записать функцию в обратных кавычках:
(^2) `map` [1..10]
У операторов — наоборот: по умолчанию инфиксная. Для того, чтобы оператор сделать префиксным необходимо заключить его в скобки:
(+) 1 2
Частичное применение над инфиксными записями называют секциям, и в них можно писать как первый аргумент, так и второй (один из). Секцию заключают в скобки:
Здравствуйте, dr.Chaos, Вы писали:
DC>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs
Не заметил вопроса о foldr. fold — это настолько базовая для ФП вещь, что она хорошо разобрана в других источниках. В классической статье Why Functional Programming Matters, например.
Здравствуйте, dr.Chaos, Вы писали:
DC>1. Есть пример как выразить ф-ю filter с помощью foldr (7.12) DC>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs
Идея здесь вот какая: foldr, грубо говоря, заменяет конструктор конс-пары : на пользовательскую функцию.
Т.е.
-- было
src = [1,2,3,4]
src = 1 : 2 : 3 : 4 : [] -- не забываем о правой ассоциативности
-- стало
dst = foldr foo end src
dst = (1 `foo` (2 `foo` (3 `foo` (4 `foo` end))))
Теперь ещё раз посмотрим на фильтр.
filter p (x:xs) = if p x then x:filtered_xs else filtered_xs where
filtered_xs = filter p xs
-- представим себе, что filtered_xs мы уже смогли вычислить.
filter_one p x ys = if p x then x:ys else ys
filter p x:xs = (filter_one p) x ((filter p) xs)
-- то есть, (filter_one p) и есть та самая искомая foo из объявления foldr
filter p xs = foldr (filter_one p) [] xs
DC>2. Чуть ниже приводиться подобный пример для ++
DC>(++) [] = id
DC>Несколько не понял выделенную замену, что она дает и как её понимает компилятор.
Это просто трюк, чтобы не писать лишнего (и заодно упростить жизнь компилятору). Эквивалентно выражению
(++) [] ys = ys
что значит: если первый список пуст, то результат склейки — это второй список.
Здравствуйте, palm mute, Вы писали:
PM>Не заметил вопроса о foldr. fold — это настолько базовая для ФП вещь, что она хорошо разобрана в других источниках. В классической статье Why Functional Programming Matters, например.
PM>В SICP тоже разбирается достаточно подробно.
А вот линзы с бананами давать начинающему я бы не советовал. Катаморфизмы с анаморфизмами прекрасны, я не спорю, но есть опасность получить обратный эффект .
Здравствуйте, lomeo, Вы писали:
L>Согласен, это я так — в копилку. Вообще список литературы нужен с кейвордами. citeseer — не то, там рыться
Мне пока del.icio.us хватает. CiteULike, на первый взгляд, еще лучше подходит для этой цели. А вообще интересно, почему citeseer цитаты из статей выдирать умеет, а кейворды — нет, они же практически всегда под абстрактами присутствуют.
Re[6]: Список литературы (was Eta reduction (Haskell))
Здравствуйте, palm mute, Вы писали:
PM>Мне пока del.icio.us хватает. CiteULike, на первый взгляд, еще лучше подходит для этой цели. А вообще интересно, почему citeseer цитаты из статей выдирать умеет, а кейворды — нет, они же практически всегда под абстрактами присутствуют.
Я на CiteULike но редко. А так — да, в принципе хватает.
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, dr.Chaos, Вы писали:
DC>>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно DC>>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?
PM>Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара. Инфиксный оператор, взятый в скобки, превращается в обычную функцию, т.е. PM>
Да, собственно, у меня уже был небольшой опыт знакомства с Лиспом и Прологом в универе, но он прошел немножко мимо меня, т.к. языки в принципе дали, а вот погонять по ним на задачах ИИ не забыли , просто двухсеместровый (а по хорошему и трех) курс засунули в один семестр.
Я эти концепции понимаю, у меня как раз сахар вопросы вызывает .
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, dr.Chaos, Вы писали:
DC>>1. Есть пример как выразить ф-ю filter с помощью foldr (7.12) DC>>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs
К>Идея здесь вот какая: foldr, грубо говоря, заменяет конструктор конс-пары : на пользовательскую функцию.
К>Теперь ещё раз посмотрим на фильтр. К>
К>filter p (x:xs) = if p x then x:filtered_xs else filtered_xs where
К> filtered_xs = filter p xs
К>-- представим себе, что filtered_xs мы уже смогли вычислить.
К>filter_one p x ys = if p x then x:ys else ys
К>filter p x:xs = (filter_one p) x ((filter p) xs)
К>-- то есть, (filter_one p) и есть та самая искомая foo из объявления foldr
К>filter p xs = foldr (filter_one p) [] xs
К>
Я уже понял, что в лямбду уже попадает результат вычисления, как второй параметр.
Меня просто смутила замена
filter p [] = []
filter p (x:xs) =
if p x
then x : filter p xs
else filter p xs
filter p [] = []
filter p (x:xs) =
if p x then x : b else b
Эти две функции не эквивалентны
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Здравствуйте, dr.Chaos, Вы писали:
DC>Меня просто смутила замена
DC>filter p [] = []
DC>filter p (x:xs) =
DC>if p x
DC>then x : filter p xs
DC>else filter p xs
DC>filter p [] = []
DC>filter p (x:xs) =
DC>if p x then x : b else b
DC>Эти две функции не эквивалентны
Там забыто ... where b = filter p xs
тогда эти функции эквивалентны.
После чего авторы предлагают такой паттерн рефакторинга:
foo [] = []
foo x:xs = bar x bwhere b = foo xs
-- заменить наfoo = foldr (\x b -> bar x b) []
где foo — возможно, каррированная функция (например, filter p), а bar x b — некое выражение, содержащее x и b, но не содержащее xs
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, dr.Chaos, Вы писали:
DC>>Меня просто смутила замена К>
DC>>filter p [] = []
DC>>filter p (x:xs) =
DC>>if p x
DC>>then x : filter p xs
DC>>else filter p xs
DC>>filter p [] = []
DC>>filter p (x:xs) =
DC>>if p x then x : b else b
К>
DC>>Эти две функции не эквивалентны
К>Там забыто ... where b = filter p xs К>тогда эти функции эквивалентны. К>После чего авторы предлагают такой паттерн рефакторинга: К>
К>foo [] = []
К>foo x:xs = bar x bwhere b = foo xs
К>-- заменить на
К>foo = foldr (\x b -> bar x b) []
К>
К>где foo — возможно, каррированная функция (например, filter p), а bar x b — некое выражение, содержащее x и b, но не содержащее xs
Да нет этого в YAHT я его недели 2-3 назад скачал .
ЗЫ Хотя так намного понятней
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Интересно, какой диалект Хаскелла там освещается?
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>Я так понимаю, что гиломорфизм (хиломорфизм?) — обощение анаморфизма, параморфизм — катаморфизма. Разница — в использовании фунций вместо конструкторов.
Все эти ката- ана- и пара- легко получаются из хило-. Последний можно рассматривать как общий шаблон итеративного вычисления.
Катаморфизм получается когда вычисления управляются данными алгебраического типа, анаморфизм — когда результат алгебраического типа.
Здравствуйте, Трурль, Вы писали:
Т>Все эти ката- ана- и пара- легко получаются из хило-. Последний можно рассматривать как общий шаблон итеративного вычисления.
Твоя правда, спасибо, сам не увидел. Были сомнения насчёт параморфизма. Проверил — всё очень легко ложится:
hylo p f g c a | p a = c
| True = f b (hylo p f g c a')
where
(b, a') = g a
-- ката и ана легко:
ana p g = hylo p (:) g []
cata f = hylo null f (\(x:xs) -> (x,xs))
-- класс типов для параморфизмаclass Para p a | p -> a where
isStart :: p -> Bool
decompose :: p -> (a, p)
-- например, для спискаinstance Para [a] a where
isStart = null
decompose (x:xs) = (x,xs)
-- обычное определение параморфизма
para f b x
| isStart x = b
| otherwise = f m (para f b n)
where
(m,n) = decompose x
-- а вот он же через хиломорфизм
para' f = hylo isStart f decompose
Здравствуйте, Mirrorer, Вы писали:
M>Здравствуйте, palm mute, Вы писали:
PM>>Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара.
M>Хм. А какой тогда хороший и без сахара ?
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Mirrorer, Вы писали:
M>>Хм. А какой тогда хороший и без сахара ? PM>Схема.
Я кстати, последовал совету и сейчас читаю SICP, но задания делаю на 2х языках. Чтоб и принцип за "сладостью" не потерялся, и сахар потихоньку запоминался.
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы