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 назад скачал .
ЗЫ Хотя так намного понятней
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
.
.
. (++) xs) ys --Здесь может имелось в виду ((x
Перекуём баги на фичи!
, просто двухсеместровый (а по хорошему и трех) курс засунули в один семестр.
.
