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