Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 21.03.07 11:16
Оценка:
Вот решил посмотреть чисто функциональный язык. Выбрал Haskell .

Вот читаю YAHT.

Возникла пара вопросов по сокращению записи функций:

1. Есть пример как выразить ф-ю filter с помощью foldr (7.12)

filter p [] = []
filter p (x:xs) =
if p x
then x : filter p xs
else filter p xs


...
Now, suppose that we call the result of calling filter p xs simply b, then we can rewrite this as:

filter p [] = []
filter p (x:xs) =
if p x then x : b else b

filter p = foldr (\a b -> if p a then a:b else b) []


Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs

2. Чуть ниже приводиться подобный пример для ++

(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)

Now, the question is whether we can write this in fold notation. First, we can apply eta reduction to the first line to give:

(++) [] = id


Несколько не понял выделенную замену, что она дает и как её понимает компилятор.

Through a sequence of steps, we can also eta-reduce the second line:

(++) (x:xs) ys = x : ((++) xs ys)
==> (++) (x:xs) ys = (x:) ((++) xs ys)
==> (++) (x:xs) ys = ((x:) . (++) xs) ys --Здесь может имелось в виду ((x:) . (++)) xs ys?
==> (++) (x:xs) = (x:) . (++) xs

Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re: Eta reduction (Haskell)
От: palm mute  
Дата: 21.03.07 11:38
Оценка: 3 (1)
Здравствуйте, dr.Chaos, Вы писали:

DC>Вот решил посмотреть чисто функциональный язык. Выбрал Haskell .

Нормальный выбор .

DC>
DC>(++) [] ys = ys
DC>(++) (x:xs) ys = x : (xs ++ ys)
DC>

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:

DC>

DC>(++) (x:xs) ys = x : ((++) xs ys)
DC>==> (++) (x:xs) ys = (x:) ((++) xs ys)
DC>==> (++) (x:xs) ys = ((x:) . (++) xs) ys --Здесь может имелось в виду ((x:) . (++)) xs ys?
DC>==> (++) (x:xs) = (x:) . (++) xs
DC>

Здесь тоже все на месте. (++) xs — это пример частичного применения. В результате получается функция, которая получает аргумент list и возвращает xs ++ list.
(x: ) — это функция, которая принимае список list и возвращает список с добавленным элементом (x:list).

Композиция этих функций ( (x: ) . (++) xs ), получая аргумент list, сначала вычисляет xs ++ list, затем добавляет новую голову x.
Re[2]: Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 21.03.07 11:47
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, dr.Chaos, Вы писали:



DC>>

DC>>Through a sequence of steps, we can also eta-reduce the second line:

DC>>

DC>>(++) (x:xs) ys = x : ((++) xs ys)
DC>>==> (++) (x:xs) ys = (x:) ((++) xs ys)
DC>>==> (++) (x:xs) ys = ((x:) . (++) xs) ys --Здесь может имелось в виду ((x:) . (++)) xs ys?
DC>>==> (++) (x:xs) = (x:) . (++) xs
DC>>

PM>Здесь тоже все на месте. (++) xs — это пример частичного применения. В результате получается функция, которая получает аргумент list и возвращает xs ++ list.

Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно
такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re: Eta reduction (Haskell)
От: deniok Россия  
Дата: 21.03.07 11:54
Оценка:
Здравствуйте, 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` в цепочке наша лямбда делает свою работу, формируя отфильтрованный список.
Re[3]: Eta reduction (Haskell)
От: palm mute  
Дата: 21.03.07 11:54
Оценка:
Здравствуйте, dr.Chaos, Вы писали:

DC>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно

DC>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?

Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара. Инфиксный оператор, взятый в скобки, превращается в обычную функцию, т.е.
(+) 2 3  <====> 2 + 3
(++) [1,2] [3,4,5] <===> [1,2]++[3,4,5]


Если один из аргументов инфиксного оператора взять в скобки, можно выбирать, будет он левым или правым:
(2/)  <===> \x -> 2/x
(/2)  <===> \x -> x/2
(x:)  <===> \xs -> x:xs
Re: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 21.03.07 12:00
Оценка:
Здравствуйте, 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 (:))


Это интуитивный вывод определения, можно сделать вывод более формально, без всех этих "можно заметить", "логично предположить".
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 21.03.07 12:00
Оценка:
Здравствуйте, dr.Chaos, Вы писали:

DC>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно

DC>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?

У функций по умолчанию префиксная запись, т.е. они записываются перед аргументами. Однако, её можно сделать инфиксной, если записать функцию в обратных кавычках:

(^2) `map` [1..10]


У операторов — наоборот: по умолчанию инфиксная. Для того, чтобы оператор сделать префиксным необходимо заключить его в скобки:

(+) 1 2


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

(xs++) == \ys -> xs ++ ys
(+xs) == \ys -> ys ++ xs
(++) xs == \ys -> ((++) xs) ys == \ys -> (++) xs ys == \ys -> xs ++ ys
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re: Eta reduction (Haskell)
От: palm mute  
Дата: 21.03.07 12:02
Оценка: 1 (1) +1
Здравствуйте, dr.Chaos, Вы писали:

DC>Вопрос в том, как компилятор(интерпретатор) поймет, что b это filter p xs

Не заметил вопроса о foldr. fold — это настолько базовая для ФП вещь, что она хорошо разобрана в других источниках. В классической статье Why Functional Programming Matters, например.

В SICP тоже разбирается достаточно подробно.
Re: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 21.03.07 12:34
Оценка: 3 (1)
Здравствуйте, 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

что значит: если первый список пуст, то результат склейки — это второй список.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 21.03.07 12:40
Оценка: 68 (3)
Здравствуйте, palm mute, Вы писали:

PM>Не заметил вопроса о foldr. fold — это настолько базовая для ФП вещь, что она хорошо разобрана в других источниках. В классической статье Why Functional Programming Matters, например.


PM>В SICP тоже разбирается достаточно подробно.


Более сложные примеры (расширение свертки на другие типы) неплохо объясняется у Erik Meijer в Merging Monads and Folds for Functional Programming.

Ну и ещё можно посоветовать его же и соавторов классическую (и более формальную) Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Eta reduction (Haskell)
От: palm mute  
Дата: 21.03.07 12:44
Оценка: +1
Здравствуйте, lomeo, Вы писали:

L>Более сложные примеры (расширение свертки на другие типы) неплохо объясняется у Erik Meijer в Merging Monads and Folds for Functional Programming.

Спасибо, почитаем.

L>Ну и ещё можно посоветовать его же и соавторов классическую (и более формальную) Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire.


А вот линзы с бананами давать начинающему я бы не советовал. Катаморфизмы с анаморфизмами прекрасны, я не спорю, но есть опасность получить обратный эффект .
Re[4]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 21.03.07 12:55
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>А вот линзы с бананами давать начинающему я бы не советовал.


Согласен, это я так — в копилку. Вообще список литературы нужен с кейвордами. citeseer — не то, там рыться
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Список литературы (was Eta reduction (Haskell))
От: palm mute  
Дата: 21.03.07 13:06
Оценка: +1
Здравствуйте, lomeo, Вы писали:

L>Согласен, это я так — в копилку. Вообще список литературы нужен с кейвордами. citeseer — не то, там рыться


Мне пока del.icio.us хватает. CiteULike, на первый взгляд, еще лучше подходит для этой цели. А вообще интересно, почему citeseer цитаты из статей выдирать умеет, а кейворды — нет, они же практически всегда под абстрактами присутствуют.
Re[6]: Список литературы (was Eta reduction (Haskell))
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 21.03.07 13:26
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Мне пока del.icio.us хватает. CiteULike, на первый взгляд, еще лучше подходит для этой цели. А вообще интересно, почему citeseer цитаты из статей выдирать умеет, а кейворды — нет, они же практически всегда под абстрактами присутствуют.


Я на CiteULike но редко. А так — да, в принципе хватает.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 21.03.07 14:10
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, dr.Chaos, Вы писали:


DC>>Хм, тогда почему она записана так странно? Частичное применение ведь записывается как (++xs), насколько я понял, или оно

DC>>такие записи эквивалентны: (++xs) ys и ((++) xs) ys ?

PM>Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара. Инфиксный оператор, взятый в скобки, превращается в обычную функцию, т.е.

PM>
PM>(+) 2 3  <====> 2 + 3
PM>(++) [1,2] [3,4,5] <===> [1,2]++[3,4,5]
PM>


PM>Если один из аргументов инфиксного оператора взять в скобки, можно выбирать, будет он левым или правым:

PM>
PM>(2/)  <===> \x -> 2/x
PM>(/2)  <===> \x -> x/2
PM>(x:)  <===> \xs -> x:xs
PM>


Да, собственно, у меня уже был небольшой опыт знакомства с Лиспом и Прологом в универе, но он прошел немножко мимо меня, т.к. языки в принципе дали, а вот погонять по ним на задачах ИИ не забыли , просто двухсеместровый (а по хорошему и трех) курс засунули в один семестр.

Я эти концепции понимаю, у меня как раз сахар вопросы вызывает .
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re[2]: Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 21.03.07 14:30
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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


Эти две функции не эквивалентны
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re[3]: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 21.03.07 15:57
Оценка: 8 (1)
Здравствуйте, 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 b where b = foo xs

-- заменить на
foo = foldr (\x b -> bar x b) []

где foo — возможно, каррированная функция (например, filter p), а bar x b — некое выражение, содержащее x и b, но не содержащее xs
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[4]: Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 21.03.07 16:28
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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 b where b = foo xs

К>-- заменить на
К>foo = foldr (\x b -> bar x b) []
К>

К>где foo — возможно, каррированная функция (например, filter p), а bar x b — некое выражение, содержащее x и b, но не содержащее xs

Да нет этого в YAHT я его недели 2-3 назад скачал .

ЗЫ Хотя так намного понятней
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re[5]: Eta reduction (Haskell)
От: deniok Россия  
Дата: 21.03.07 16:58
Оценка: :)
Здравствуйте, dr.Chaos, Вы писали:

DC>Да нет этого в YAHT я его недели 2-3 назад скачал .


Hal Daume III этим "паттерном рефакторинга" скрытно пользуется, а Кодт его выводит на чистую воду
Re[3]: Eta reduction (Haskell)
От: Трурль  
Дата: 22.03.07 06:16
Оценка: 30 (3)
Здравствуйте, lomeo, Вы писали:

Есть еще специальный A tutorial on the universality and expressiveness of fold.
Re[3]: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 30.03.07 20:51
Оценка:
Здравствуйте, lomeo, Вы писали:

L>Более сложные примеры (расширение свертки на другие типы) неплохо объясняется у Erik Meijer в Merging Monads and Folds for Functional Programming.


Интересно, какой диалект Хаскелла там освещается?
1) Необычное определение Maybe a = No | Yes a, вместо Nothing | Just a. Ну допустим, это чисто для иллюстрации.
2) Классы Monad (полугруппа) и Monad0 (моноид)
3) логичное имя для операции сложения — (++), вместо mplus. Удачно складывается то, что конкатенация списков — это и есть сложение в монаде List.
Перекуём баги на фичи!
Re[4]: Eta reduction (Haskell)
От: deniok Россия  
Дата: 30.03.07 21:08
Оценка: 27 (1)
Здравствуйте, Кодт, Вы писали:

К>Интересно, какой диалект Хаскелла там освещается?


Gofer

Gofer может рассматриваться как экспериментальный диалект Haskell. Интерпритатор HUGS первоначально был разработан как реализация Gofer. В Настоящее время полностью влился в Haskell и не существует как самостоятельный язык. Однако часто упоминается в старых публикациях.

отсюда
Re: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 19.04.07 15:58
Оценка:
Здравствуйте, dr.Chaos, Вы писали:

<>

Прочёл сейчас статьи про фолды и монады. Понял, что не догоняю базиса. Не, про каждую букву отдельно всё ясно — а вот идею пОнять...

1) Что есть фолд?
Тот факт, что фолд подчиняется некоторым очевидным законам — навевает мысли о том, что это какая-то сущность из абстрактной алгебры.
Не изоморфизм, поскольку отображает структурную монаду в любую другую монаду, какую ему подсунешь в аргументы. Например, в Id.

2) Можно ли фолды классифицировать?
К примеру, у всех монад есть одни и те же функции (по-разному реализованные). Что и даёт Functor => Monad => MonadPlus.

3) Где бы и что бы такое почитать, про теорию категорий или про что угодно относящееся к этому делу, чтобы
— было не заумно
— более-менее практично, т.е. показывалось, как та или иная абстрация проявляется в прикладной задаче (и зачем эту абстракцию проявлять)
У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.
А для чего тогда прямо в Прелюдии есть классы Functor и Arrow? Чисто для красоты и общности, или же чем-то полезны? Это как минимум.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Eta reduction (Haskell)
От: awson  
Дата: 19.04.07 19:15
Оценка: 50 (4)
Здравствуйте, Кодт, Вы писали:

К>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

Гугль Вам в помощь.
Re[3]: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 20.04.07 10:44
Оценка: 15 (2) :)
Здравствуйте, awson, Вы писали:

Небольшой траверс и, можно даже сказать, дюльфер.

A>1. Erik Meijer, Maarten Fokkinga, Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire


Полез читать эту статью, увидел ключевое слово catamorphism. Ага!
Гугл на "катаморфизм" (по-русски — а вдруг?), первая же ссылка The Algebra of Programming &mdash; отзывы читателей.
Запомним книжку, а пока что смотрю на отзывы. Там человек упоминает Zhenjiang Hu: Program Optimization and Transformation in Calculational Form.



Открыл этот PDF. Первая же фраза просто убила.

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.

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

Впрочем, остальной текст вменяемый.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[4]: Eta reduction (Haskell)
От: O N A Россия  
Дата: 20.04.07 11:16
Оценка:
Здравствуйте, Кодт, Вы писали:

("" `const`) {-оверквотинг-} -- Кодт

К>Японские учёные для мирового сообщества приводят в английском тексте китайскую поговорку, суть которой — нельзя одновременно ухватить два предмета. Воистину, чтобы понять рекурсию...


К>Впрочем, остальной текст вменяемый.


Японские...
SON- солнечный финал (с) азерб-африк :)
Re[5]: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 20.04.07 11:19
Оценка:
Здравствуйте, O N A, Вы писали:

К>>Японские учёные для мирового сообщества приводят в английском тексте китайскую поговорку, суть которой — нельзя одновременно ухватить два предмета. Воистину, чтобы понять рекурсию...


К>>Впрочем, остальной текст вменяемый.


ONA>Японские...


Ну, я по двум последним соавторам судил... А только потом вчитался в имя первого
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 23.04.07 13:42
Оценка:
Здравствуйте, Кодт, Вы писали:

К>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? Чисто для красоты и общности, или же чем-то полезны? Это как минимум.


Arrow нет в прелюдии.
Re[3]: Eta reduction (Haskell)
От: Кодт Россия  
Дата: 23.04.07 15:41
Оценка:
Здравствуйте, 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 нет в прелюдии.


Control.Arrow — это за пределами прелюдии?
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[4]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 23.04.07 19:51
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Ужасужасужас. Мне бананов с разлохмаченными проводами хватило.


Пардон, сам пробиваюсь с трудом

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, по которым для каждого типа установил бы типы ката- и анаморфизмов.

К>Мне просто нравится идея того, что параметры морфизма можно завернуть в один кортеж, и установить функции

К>
К>catamorphism_args `catamorphism` container = result
К>anamorphism_args `anamorphism` seed = container
К>

К>Но это, похоже, вылезает слишком далеко за пределы системы типов хаскелла.

Не вылезает.

class Cata c where
    cata :: m -> c -> r


Ну разве что нельзя представить в системе типов, что m зависит от c.
Только толку то. Катаморфизм то для каждого типа всё равно надо писать. Или генерить

К>>>У меня сложилось впечатление, что монады — это настолько высокая планка, что большинство статей по тому же Хаскеллу проводит читателя-новичка только до неё. Слава богу, мол, если хоть это осилишь.


L>>Есть такое мнение, думаю, оно несправедливо.


К>Ну и как эту несправедливость побороть?


А надо? Если серьёзно, то "статьи по тому же Хаскеллу" — имеются в виду туториалы? Если да, то я больше встречал с монадами, если нет, то не монадами едиными...

L>>Arrow нет в прелюдии.


К>Control.Arrow — это за пределами прелюдии?


Так точно.
Re[4]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 06:25
Оценка: +1
К> извините, reverse как анаморфизм распотрошить сходу не вспомнил
reverse = foldl (flip (:)) []

Но вот
foldr f a xs = foldl (flip f) a (reverse xs)

на бесконечных списках загнется.
Re[5]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 24.04.07 09:02
Оценка: +1
Здравствуйте, Трурль, Вы писали:

К>> извините, reverse как анаморфизм распотрошить сходу не вспомнил

Т>
Т>reverse = foldl (flip (:)) []
Т>


Это не анаморфизм.
Re[5]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 10:00
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>на бесконечных списках загнется.

С другой стороны, это неважно, так как формально foldr определен на свободной алгебре, а бесконечные списки в неё не входят.
Re[6]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 11:54
Оценка:
Здравствуйте, 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
Re[6]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 24.04.07 12:39
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>>на бесконечных списках загнется.

Т>С другой стороны, это неважно,

??

T>так как формально foldr определен на свободной алгебре, а бесконечные списки в неё не входят.


Можно ссылку? Я просто не знаю, что такое свободная алгебра.
А так да — конечный список можно представить как initial (кто нибудь перевод знает?) алгебру (правда, я не понимаю, почему точно так же не представим бесконечный?). И следовательно можно над этим типом данных определить катаморфизм.
Re[7]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 12:44
Оценка:
Здравствуйте, Трурль, Вы писали:

Это же практически хиломорфизм получился.
Re[7]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 24.04.07 13:21
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>Зато у меня получлся "обобщенный анаморфизм"

Т>
Т>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, правда через него не выразишь.

Я так понимаю, что гиломорфизм (хиломорфизм?) — обощение анаморфизма, параморфизм — катаморфизма. Разница — в использовании фунций вместо конструкторов. У тебя, так ещё и конечное значение — не значение, а вычисление, т.к. обощение анаморфизма и параморфизма. Трурлеморфизм. Дальше вроде некуда :-)
Re[7]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 13:22
Оценка: 10 (1)
Здравствуйте, lomeo, Вы писали:

L>Можно ссылку?

На бананы?
L>Я просто не знаю, что такое свободная алгебра.
L>А так да — конечный список можно представить как initial (кто нибудь перевод знает?) алгебру
Cвободная алгебра — алгебраисткий термин для того, что категористы называют инициальной алгеброй или инициальным объектом.
L>(правда, я не понимаю, почему точно так же не представим бесконечный?).
По определению термы не могут быть бесконечными. Да и как можно определить, скажем, сумму бесконечного списка?
Re[8]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 24.04.07 14:05
Оценка:
Здравствуйте, Трурль, Вы писали:

Вот кстати, сам не читал но облизываюсь, просматриваю и пока ничего не понимаю
Maarten M Fokkinga, Erik Meijer "Program Calculation Properties of Continuous Algebras"

Смысл в том, что они объединяют конечные списки как initial algebra в одной категории и final co-algebra в другой (но близкой) в одну алгебру. Приводят кучу законов (в частности там есть и ката/ана морфизмы и различные fusion-ы).
Re[8]: Eta reduction (Haskell)
От: Трурль  
Дата: 24.04.07 16:16
Оценка: 10 (1)
Здравствуйте, lomeo, Вы писали:

L>Я так понимаю, что гиломорфизм (хиломорфизм?) — обощение анаморфизма, параморфизм — катаморфизма. Разница — в использовании фунций вместо конструкторов.


Все эти ката- ана- и пара- легко получаются из хило-. Последний можно рассматривать как общий шаблон итеративного вычисления.
Катаморфизм получается когда вычисления управляются данными алгебраического типа, анаморфизм — когда результат алгебраического типа.
Re[9]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 25.04.07 09:09
Оценка:
Здравствуйте, Трурль, Вы писали:

Т>Все эти ката- ана- и пара- легко получаются из хило-. Последний можно рассматривать как общий шаблон итеративного вычисления.


Твоя правда, спасибо, сам не увидел. Были сомнения насчёт параморфизма. Проверил — всё очень легко ложится:

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
Re[10]: Eta reduction (Haskell)
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 25.04.07 12:47
Оценка:
Можно без fundeps обойтись:

class Para p where
    isStart :: p a -> Bool
    decompose :: p a -> (a,p a)

instance Para [] where
    isStart = null
    decompose (x:xs) = (x,xs)
Re[4]: Eta reduction (Haskell)
От: Mirrorer  
Дата: 25.04.07 16:34
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара.


Хм. А какой тогда хороший и без сахара ?
... << RSDN@Home 1.2.0 alpha rev. 676>>
Re[5]: Eta reduction (Haskell)
От: deniok Россия  
Дата: 25.04.07 18:34
Оценка: :)
Здравствуйте, Mirrorer, Вы писали:

M>Здравствуйте, palm mute, Вы писали:


PM>>Хаскелл — плохой язык для начала изучения ФП именно потому, что в нем куча сахара.


M>Хм. А какой тогда хороший и без сахара ?


Чистая лямбда. Или Unlambda.
Re[5]: Eta reduction (Haskell)
От: palm mute  
Дата: 25.04.07 19:18
Оценка: +1
Здравствуйте, Mirrorer, Вы писали:

M>Хм. А какой тогда хороший и без сахара ?

Схема.
Re[6]: Eta reduction (Haskell)
От: dr.Chaos Россия Украшения HandMade
Дата: 26.04.07 08:49
Оценка: 1 (1) +1
Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, Mirrorer, Вы писали:


M>>Хм. А какой тогда хороший и без сахара ?

PM>Схема.

Я кстати, последовал совету и сейчас читаю SICP, но задания делаю на 2х языках. Чтоб и принцип за "сладостью" не потерялся, и сахар потихоньку запоминался.
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.