К сожалению, создается впечатление, что идея о создании отдельного раздела посвященного ФЯ постепенно заглохла. Предлагаю заинтересованным лицам все-таки собраться и написать общими силами хотя бы статью-введение. Поскольку не совсем ясно, о чем стоит писать, а о чем нет, было бы неплохо, если бы незнакомые с ФП, но заинтересованные в его изучении люди, запостили здесь свои вопросы, на которые знакомые с ФП люди написали бы им ответы, объяснили трудные для понимания аспекты ФП и т.п. В общем, как писал VladD2 в соседней ветке, предлагается совместно создать документ, который действительно был бы полезен программистам не знакомым с функциональным стилем, чтобы изучив его, они легко могли бы составить впечатление о возможностях ФЯ, отличиях их от ИЯ, основных приемах программирования под ними и т.д.
Для начала со своей стороны я готов дать информацию по Haskell'ю и общим вопросам, связанным с ФП, а пока пощу здесь свою расшифровку некоторых базовых терминов часто употребляющихся по отношению к ФЯ.



Чистые ФЯ
Когда говорят о чистых ФЯ, обычно имеют ввиду языки, вычисления в которых осуществляются исключительно
при помощи композиции функции и где отсутствуют какие-либо сторонние эффекты. Данное
определение через чур строгое и, собственно говоря, под него не подходит ни один реальный
язык программирования. Т.е. ни один ЯП, который стоило бы использовать на практике.
Тем не менее полностью чистые ФЯП существуют. В качестве примера можно привести лямбда
исчисление.
Однако, имеет смысл несколько ослабить требование отсутствия сторонних эффектов, ибо ни
одна программа, которая принимает данные от пользователя и выдает ему в ответ результат, не
может без них обойтись. Если сторонние эффекты в ЯП "практически" отсутствуют, то ФЯ
называется чистым. К таким языкам относят, например, Haskell, где императивный ввод-вывод
осуществляется с помощью специального механизма монад, которые изолируют чистую
функциональную часть программы от нечистой императивной. В тоже время SML и OCaml
не являются чистыми функциональными языками, поскольку допускают использование императивных
конструкций типа операций присваивания и исключений.

Вызов по значению и вызов по имени
При вызове функции у нас есть два способа передать ей параметры. Первый способ заключается в
том, чтобы сначала вычислить параметры и потом передать в функцию вычисленные значения. А второй
в том, чтобы ничего не вычисляя передать в функцию выражения, по которым можно вычислить
ее параметры. Если функции понадобятся значения этих выражений, она их вычислит по мере
необходимости. Первый способ вызова называется вызовом по значению, поскольку в функцию передается
конкретное значение — целое, строка, список и т.д. Второй способ называется вызовом по имени,
поскольку в функцию передается невычисленное выражение. Вызов по имени в целом более выгоден,
так как экономится время необходимое для вычисления ненужных параметров, но он работает только
в чистых ФЯ, где нет сторонних эффектов. Другой особенностью вызова по имени является устойчивость
к ошибкам. Даже если вычисление одного из параметров приводит к ошибке, выражение в целом может быть
вычисленно, если в нем не задействовано значение этого параметра. В императивных языках есть функции,
которые симулируют вызов по имени. Например логическое "И" — && в С не вычисляет свой второй аргумент,
если первый равен 0. Эта особенность широко используется во многих программах, в том числе и в ядре Linux.
Языки поддерживающие вызов по значению называются строгими, те, что поддерживают вызов по имени,
называются нестрогими. Haskell нестрогий язык, а SML и OCaml строгие.

Строгая типизация
Не все функциональные языки обладают системой типов. Например, Lisp является бестиповым языком. Однако,
здесь речь пойдет только о языках со строгой типизацией. В таких языках каждая константа, каждое выражение
или функция имеют свой тип. Не допускается смешивание разных типов, даже если один из них можно легко
преобразовать в другой. Например, если у функции есть вещественный параметр, ей нельзя передать целое число
как в С++, сначала его нужно явно преобразовать в вещественное. Не допускается обестипливание как,
например, в C#. Невозможно преобразовать целое число к некоторому общему типу object. Эти строгости
компенсируются развитостью системы типов, легкостью работы со сложными типами и полиморфизмом. Легкость
работы обеспечивается сравнением с образцом (объяснено в другом разделе), а другие две темы мы обсудим чуть
ниже. При компиляции программы компилятор проверяет на соответствие все типы в программе и при несовпадении
типов выдает ошибку. В дальнейшем при выполнении программы уже не могут возникнуть исключительные ситуации
связанные с ошибочным типом, как это часто происходит в С++ или даже C#. Вам придется поверить мне на слово,
однако, я (и не только я) утверждаю, что благодаря строгой типизации и рвению компилятора в области
выявления связанных с этим ошибок, удается значительно сократить количество проблем, возникающих при
выполнении программы.
Ранее я упомянул, что строгость системы типов компенсируется ее развитостью. В самом деле, ФЯ позволяют
программисту малыми силами определять сложные типы данных типа списков, деревьев и т.п. Основным типом
ФЯ можно назвать список — создание списков и работа с ними упрощены до безобразия. Например, чтобы создать
список вам достаточно написать

[a,b,c]

где a,b и c — это элементы списка. Хотите создать список в списке? Пожалуйста

[[a,b,c],[],[n,r]]

Для работы со списками существует огромное количество функций, в том числе специальная функция помещения
элемента в список, которая обычно обозначается : или ::

1:[2,3]

Вторым важным конструктором новых типов является кортеж (tuple). Это всего лишь набор разнотипных значений
вроде

(1,"str",'a')

Кортежы используются для возвращения из функций нескольких значений, определения сложных типов типа деревьев
или списков и т.п.
Многие ФЯ допускают использование структур, которые по сути своей являются кортежами с именоваными полями.
Допускается определение древовидных или циклических структур данных. Например, определим тип для выражения
в языке программирования

data Expr = Var String | Integer Int | Str String | Assign Var Expr | Func Var [Expr]

Var, Integer, Str, Func и Assign — это так называемые конструкторы типа. С их помощью можно создать
значение типа Expr

Assign (Var "my_var") (Func (Var "my_func") [(Str "str"),(Integer 10)])

Возможности впечатляют, однако, это еще не все. Система типов в ФЯ полиморфна. Мы можем определять как
полиморфные функции так и полиморфные типы данных и при этом не теряется строгость типизации! Как
определить можно ли в качестве параметра функции типа A подставить значение или выражение типа B? Нужно
просто посмотреть, можно ли свести тип B к типу A. В С++ аналогичная ситуация возникает, если от класса
A унаследованы классы B и C. B можно свести к A, но нельзя свести к C. В ФЯ производится аналогичная
процедура проверки, только ввиду всеобщего полиморфизма она намного сложнее. Например функция

my_func x = [x]

имеет тип

a->[a]

т.е. преобразует значение типа a в список значений типа a.

my_func2 x = (Integer 10):[x]

имеет тип

Expr -> [Expr]

т.е. ee тип является частным случаем типа первой функции.

my_func my_func2
my_func:(my_func my_func2)

типы этих выражений

[Expr->[Expr]]
[Expr->[Expr]]

Заметьте мы смогли положить полиморфную функцию my_func в список специализированных функций. Обратное
было бы невозможно.
Данные примеры довольно просты, в реальных программах типы выражений и функций могут иметь весьма
значительный размер. Тот, кто видел шаблоны в С++ поймет о чем я говорю. Слава богу, в случае с ФЯ
программист не обязан переписывать километровые объявления типов раз за разом. Всю эту тяжелую работу
берет на себя компилятор. Более того, он выводит для каждой функции максимально общий (самый
полиморфный) из всех возможных типов. В принципе, вы можете вообще забыть о них и даже не знать точно
какой тип имеет ваша любимая функция. Если вы сомневаетесь в возможностях компилятора, то смею вас заверить,
что за всем этим стоит особая теория (что в случае ФЯ неудивительно), где строго доказывается возможность
вывода самого общего типа в любой ситуации, где это вообще возможно. Тем не
менее рекомендуется указывать типы по крайней мере у основных функций с тем,
чтобы повысить читаемость программы и облегчить работу компилятору. Иногда, в
сложных случаях, явное указание типа становится необходимостью, поэтому важно
знать, как выглядят объявления типов и уметь указывать из самому.
Остается добавить, что отдельные ФЯ расширяют стандартную систему типов разными способами. Например, в
OCaml добавлены классы, а в Haskell'e существуют классы типов, которые чем-то похожи на интерфейсы в ООП
языках.

Сравнение с образцом (pattern matching)
Поскольку в ФЯ широко используются сложные типы данных, для эффективной работы с ними существуют
мощные инструменты, а именно сравнение с образцом. Суть данного метода заключается в том, что мы
указываем некоторый каркас предполагаемого значения (образец), а программа пытается подогнать под этот
образец полученное значение. Например в этом примере

case list of
    head:tail -> ...
  | [] -> ...

мы пытаемся сравнить список list с двумя образцами head:tail и []. Если список не пустой, то сработает
первый образец, при этом head будет равен первому элементу списка, а в tail будет сохранен его хвост.
Если же список пустой, то сработает второй образец. Сложность образцов неограничена, вы можете использовать
для их создания все методы, с помощью которых можно создавать данные. Например в данном примере

case expr of
   Assign (Var my_var) (Func my_func [(Str "str"),(Integer 10)]) -> ...

если expr имеет указанную структуру, то my_var будет равен имени переменной, my_func будет равен
Var some_string. Заметим, что в образце можно указывать не только переменные, которые в случае
успешного сравнения будут связаны с частями сложного типа, но и константы.

Карринг
Одна из первых деталей, которая бросается в глаза человеку, привыкшему к императивным языкам
программирования, когда он видит функциональную программу, это отсутствие скобок вокруг параметров при
объявлении функций:
my_func a b c = ...
Это так называемая карринговая форма записи, которая получила свое название от имени Карри, который
первый указал на преимущества, которые она дает в ФЯП. В самом деле, поскольку в ФЯП функции и данные
равноправны, при такой записи параметров появляется ценная возможность использовать частичное определение
функций. Рассмотрим, например, функцию сложения двух чисел

add a b = a + b

Имея эту функцию мы можем создать новые функции типа

inc x = add 1 x
add10 x = add 10 x

первая из которых увеличивает свой аргумент на 1, а вторая на 10. Разница с обычным вызовом более
общей подфункции с некоторыми фиксированными аргументами заключается в том, что функция add 1 будет
частично вычислена один раз и при дальнейших вызовах перевычислятся не будет. В данном простом примере
это врядли приведет к существенному сокращению вычислений, однако, в более сложных случаях, выгода может
быть значительной. Дополнительно устраняется необходимость отдельного объявления специализированных
функций, что было бы неизбежно в случае обычной формы записи.

Функции высшего порядка (higher order functions)
Это функции, которые могут принимать в качестве аргумента и возвращать другие функции. Такие функции
повсеместно используются в ФЯП. Одной из классических функций такого рода является функция map, которая
принимает в качестве аргументов список элементов и функцию, которая преобразует эти элементы и возвращает
список с преобразоваными элементами. Вот как выглядит ее объявление

map f (head:tail) = (f head):(map f tail)
map f [] = []

Если мы объявим f как

f x = x*2

И применим map к f и списку [1,2,3], то получим список [2,4,6].

Ленивые вычисления
Как уже было сказано ранее, ФЯ делятся на строгие и нестрогие. Нестрогие языки
еше называют ленивыми. Это значит, что реальные вычисления в них откладываются
до того момента, когда они действительно становятся необходимы. На вопрос о том
насколько полезны ленивые вычисления нельзя дать однозначного ответа. В одних
случаях ленивость позволяет уменьшить количество вычислений и использовать
ленивые структуры данных типа бесконечных списков, а в других она становится
проблемой, когда память забивается недовычисленными выражениями, о которых
пока неизвестно, нужно их вычислять или нет. Такая ситуация возникает,
например, в LL(inf) парсере — парсере с произвольным заглядыванием вперед.
Для борьбы с лишней ленивостью применяются различные средства — форсирование
вычислений, специальные методы программирования типа CPS, строгие поля у типов
данных и т.п. Программист имеет возможность найти слабые места в своей
программе с помощью специальных инструментов и устранить их убрав, например,
ленивые вычисления там, где они не нужны.