К сожалению, создается впечатление, что идея о создании отдельного раздела посвященного ФЯ постепенно заглохла. Предлагаю заинтересованным лицам все-таки собраться и написать общими силами хотя бы статью-введение. Поскольку не совсем ясно, о чем стоит писать, а о чем нет, было бы неплохо, если бы незнакомые с ФП, но заинтересованные в его изучении люди, запостили здесь свои вопросы, на которые знакомые с ФП люди написали бы им ответы, объяснили трудные для понимания аспекты ФП и т.п. В общем, как писал 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, строгие поля у типов
данных и т.п. Программист имеет возможность найти слабые места в своей
программе с помощью специальных инструментов и устранить их убрав, например,
ленивые вычисления там, где они не нужны.

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

У меня такой вопрос какие задачи ложатся на ФЯ лучше чем на ИЯ. Просто из своего опыта и из тех веток где была задача с простыми числами, у меня сложилось впечатление что даже многие математические задачи проще решаются ИЯ, например у той же задачи про решето Эратосфена сишная реализация намного прозрачнее и ближе к описанию алгоритма на естественном языке.

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



Q>Чистые ФЯ
Чистый ФЯ — язык в котором единственным результатом работы любой функции является возвращяемое значение.То есть максимально близко к математическому аналогу — функция это отображение множества входных
параметров в выходной.Результат функции не зависит от того когда эта фунция выполняется.Более того различные части одной функции могут быть вычеслены в разное время например result=f1(f2(A,B),f3(C,D))
Может быть вычислена так

A->C->D->B->f2->f3->f1

Это обстоятельсто усложняет отладку программ
Отсюда следут отсутствие глобальных переменных.Так как не одна ф-ия не может их изменить и не может от них зависить.С этим же связано отсутствие операции изменения переменной.



Q>Вызов по имени в целом более выгоден,
Спорно сам пишешь ниже.Выгодно когда то что нужно вычислить достатчно мало (занимает мало памяти для описания)
а вычисления достаточно долгие например 1000000000000! и не выгодно когда вычисленный результат во много раз меньше чем исходный.Например размер дерева или списка — проще сразу получить размер и удалить саму структуру(если она не используется далее) чем хранить ее до последнего

Q>Языки поддерживающие вызов по значению называются строгими, те, что поддерживают вызов по имени,
Q>называются нестрогими. Haskell нестрогий язык, а SML и OCaml строгие.
И Haskell и Ocaml поддерживают оба способа.Просто по умолчанию поведение Haskell нестрогое а OCaml строгое.

Q> Основным типом ФЯ можно назвать список
Основным типом ФЯ Haskell является алгебраический тип данных.Близкий аналог в ИЯ это enum(C).
Списки и кортежи является частным случаем.

2.4 Built-in Types Are Not Special
Earlier we introduced several "built-in" types such as lists, tuples, integers, and characters. We have also shown how new user-defined types can be defined. Aside from special syntax, are the built-in types in any way more special than the user-defined ones? The answer is no. The special syntax is for convenience and for consistency with historical convention, but has no semantic consequences.

We can emphasize this point by considering what the type declarations would look like for these built-in types if in fact we were allowed to use the special syntax in defining them. For example, the Char type might be written as:

data Char = 'a' | 'b' | 'c' | ... -- This is not valid
| 'A' | 'B' | 'C' | ... -- Haskell code!
| '1' | '2' | '3' | ...
...

These constructor names are not syntactically valid; to fix them we would have to write something like:

data Char = Ca | Cb | Cc | ...
| CA | CB | CC | ...
| C1 | C2 | C3 | ...
...

Even though these constructors are more concise, they are quite unconventional for representing characters.

In any case, writing "pseudo-Haskell" code in this way helps us to see through the special syntax. We see now that Char is just an enumerated type consisting of a large number of nullary constructors. Thinking of Char in this way makes it clear that we can pattern-match against characters in function definitions, just as we would expect to be able to do so for any of a type's constructors.

[This example also demonstrates the use of comments in Haskell; the characters -- and all subsequent characters to the end of the line are ignored. Haskell also permits nested comments which have the form {-...-} and can appear anywhere (§2.2).]

Similarly, we could define Int (fixed precision integers) and Integer by:

data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532 -- more pseudo-code
data Integer = ... -2 | -1 | 0 | 1 | 2 ...

where -65532 and 65532, say, are the maximum and minimum fixed precision integers for a given implementation. Int is a much larger enumeration than Char, but it's still finite! In contrast, the pseudo-code for Integer is intended to convey an infinite enumeration.

Tuples are also easy to define playing this game:

data (a,b) = (a,b) -- more pseudo-code
data (a,b,c) = (a,b,c)
data (a,b,c,d) = (a,b,c,d)
. .
. .
. .

Each declaration above defines a tuple type of a particular length, with (...) playing a role in both the expression syntax (as data constructor) and type-expression syntax (as type constructor). The vertical dots after the last declaration are intended to convey an infinite number of such declarations, reflecting the fact that tuples of all lengths are allowed in Haskell.

Lists are also easily handled, and more interestingly, they are recursive:

data [a] = [] | a : [a] -- more pseudo-code

We can now see clearly what we described about lists earlier: [] is the empty list, and : is the infix list constructor; thus [1,2,3] must be equivalent to the list 1:2:3:[]. (: is right associative.) The type of [] is [a], and the type of : is a->[a]->[a].

[The way ":" is defined here is actually legal syntax---infix constructors are permitted in data declarations, and are distinguished from infix operators (for pattern-matching purposes) by the fact that they must begin with a ":" (a property trivially satisfied by ":").]

At this point the reader should note carefully the differences between tuples and lists, which the above definitions make abundantly clear. In particular, note the recursive nature of the list type whose elements are homogeneous and of arbitrary length, and the non-recursive nature of a (particular) tuple type whose elements are heterogeneous and of fixed length. The typing rules for tuples and lists should now also be clear:

For (e1,e2,...,en), n>=2, if ti is the type of ei, then the type of the tuple is (t1,t2,...,tn).

For [e1,e2,...,en], n>=0, each ei must have the same type t, and the type of the list is [t].

(отсюда)
Или по другому список
data List a = Only a | Pair a (List a)
кортеж
data C1 a = C1 a
data C2 a b = C2 a b
...

Списки — это основной тип данных для Lisp


Q>Карринг
Предположим есть функция — сложение.
Можно рассматривать ее как функцию от 2 аргументов int и возвращающюю int
А можно как функцию 1-ого числа x возвращающюю другую функцию 1-ого аргумента f ,такую что f y =x+y — это карринг или частичное применение функции

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

FR>У меня такой вопрос какие задачи ложатся на ФЯ лучше чем на ИЯ. Просто из своего опыта и из тех веток где была задача с простыми числами, у меня сложилось впечатление что даже многие математические задачи проще решаются ИЯ, например у той же задачи про решето Эратосфена сишная реализация намного прозрачнее и ближе к описанию алгоритма на естественном языке.

Хорошо, давайте сравним.

Быстрая сортировка на ФЯ:

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

Решето эрастофена на ФЯ:

ld n = ldf 2 n

divides d n = rem n d == 0

ldf k n | divides k n = k
        | k^2 > n     = n
        | otherwise   = ldf (k+1) n

prime n | n < 1     = error "not a positive integer"
        | n == 1    = False
        | otherwise = ld n == n

Императивные аналоги, я думаю, Вы себе представляете.

На функциональных языках многое записывается проще. Проблема же состоит только в том, что современные компиляторы функциональных языков не могут сгененрировать эффективный код. Но это не принципиальная проблема. Рано или позно появятся эффективные компиляторы. Еще одна проблема функциональных языков — это убогая семантика массивов. Но и она, скорее всего, тоже окажется в прошлом.
Идея любого языка программирования заключается в том, что бы переложить максимальное количество рутинной работы на компьютер. А для этого задача должна описываться на максимально возможном для машины уровне абстракции. Пока что для этого ничего лучше функционального и логического подхода не придумано.

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

FR>У меня такой вопрос какие задачи ложатся на ФЯ лучше чем на ИЯ. Просто из своего опыта и из тех веток где была задача с простыми числами, у меня сложилось впечатление что даже многие математические задачи проще решаются ИЯ, например у той же задачи про решето Эратосфена сишная реализация намного прозрачнее и ближе к описанию алгоритма на естественном языке.

Как минимум
1.Для манипуляции сложных древовидных структур (попробуй реализовать AVL или RB дерево)- синтаксические деревья и алгебраические выражения — например встроенный язык в программе Mathematica имеет много функциональных конструкций.А ее бесплатный аналог Maxima написан на lisp.
integral x^n,dz =if z==x then x^(n+1)/(n+1) else x^n*z
integral a*x+b = a*x*x+b*x ...
Вообщем pattern matching -та черта ФЯ полезность которой не вызывает сомнений
2.Для реализации алгоритмов легко распадающиеся не составные части
3.Где активно применяется рекурсия например LL — разбор

N_> Еще одна проблема функциональных языков — это убогая семантика массивов. Но и она, скорее всего, тоже окажется в прошлом.
Вообще-то верно,но посмотри в сторону Haskell — Array не так уж и плох.Плохо массивы вписываюся в pattern matching вот в чем проблема.

Nick_ -> "Re[2]: ФП: вводная статья" :

FR>> математические задачи проще решаются ИЯ, например у той же задачи
FR>> про решето Эратосфена сишная реализация намного прозрачнее и ближе
FR>> к описанию алгоритма на естественном языке.

N> Хорошо, давайте сравним.

N> Быстрая сортировка на ФЯ:

N> Решето эрастофена на ФЯ:

Все клева.... только часто ли необходимо изобретать велосипеды и писать
qsort & ero_filter?
Мне вот интересно, как с помощью ФП пишется бизнес- логика? Как описать
поведение не_знаю_как_будет_в_ФП_объекты? Такие вот банальные
сермяжно-прагматические вопросы

Yury Kopyl aka hrg | http://id.totem.ru |
"Если ты плюнешь на коллектив — коллектив утрется,
но если коллектив плюнет на тебя — ты утонешь" (С)Баралгин

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

_>Вообще-то верно,но посмотри в сторону Haskell — Array не так уж и плох.Плохо массивы вписываюся в pattern matching вот в чем проблема.

Array сделан с помощью монад, чтобы избежать копирования. По моему, это глупо. И пользоваться такими массивами практически невозможно. Как, например, записать независимое обновление двух ячеек массива, что бы компилятор мог это распараллелить? А ведь без этого нельзя сделать эффективную обработку массивов с использованием SIMD инструкций...
Хотя у меня в этом опыта практически нет. Надо будет попробовать реализовать какую-нибудь задачу с обработкой матриц чтобы проверить насколько я прав.

Здравствуйте, hrg, Вы писали:
hrg>Все клева.... только часто ли необходимо изобретать велосипеды и писать
hrg>qsort & ero_filter?
hrg>Мне вот интересно, как с помощью ФП пишется бизнес- логика? Как описать
hrg>поведение не_знаю_как_будет_в_ФП_объекты? Такие вот банальные
hrg>сермяжно-прагматические вопросы

Бизнес-логика пишется абсолютно так же как и моделируются конечные автоматы.
Поведение (последовательное изменение состояние обьекта) обычно описывается функцией которая по исходному состоянию выдает следующее. А для того что бы гарантировать то, что объект при этом не копируется используются монады (я про haskell). Кстати, для ввода-вывода монады нужны только для того, что бы гарантировать последовательную работу с устройством ввода-вывода, что исходное состояние обьекта нигде не будет использовано два раза. Иначе компилятор не поймет в каком месте использовать объект раньше.
Я примеры приводить не буду, потому как пора уже домой. Но может кто-нибудь приведет.

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

N_>> Еще одна проблема функциональных языков — это убогая семантика массивов. Но и она, скорее всего, тоже окажется в прошлом.
_>Вообще-то верно,но посмотри в сторону Haskell — Array не так уж и плох.Плохо массивы вписываюся в pattern matching вот в чем проблема.

import StdClass, StdInt, _SystemArray

Swap i j a =:{ [i] = ai, [j] = aj } = { a & [i] = aj, [j] = ai }

Start:: .{Int}
Start = Swap 3 7 { x \\ x <- [1..10] }

Clean. Меняем местами 3-е и 7-е элементы массива целых чисел от 1 до 10. Изменение деструктивно, массив не копируется. Применяем pattern matching и array comprehensions.

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

N_>Быстрая сортировка на ФЯ:

N_>

N_>qsort []     = []
N_>qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
N_>                 where
N_>                   elts_lt_x   = [y | y <- xs, y < x]
N_>                   elts_greq_x = [y | y <- xs, y >= x]
N_>

Это не быстрая сортировка. Это медленная. Да еще и алгоритм перевран.

Ты классический реализуй. Так чтобы для перекидки брался средний элемент. И что бы перекидка была "по месту" (без создания копий). Вот тогда и объем кода сравним. Ну, и переменные не стоит однобуквенные делать.

Насколько я понял, ОКамл как раз и работает более менее быстро из-за того, что в нем введены императивные средства, на которых и реализованы базовые алгоритмы. И по мне, так очень разумное решение. Вот еще бы более приличный императивный синтаксис. Да и вообще сделать бы синтаксис по ближе к мэйстримным С-подобным языкам. Было бы куда проще осваивать.

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

_>1.Для манипуляции сложных древовидных структур (попробуй реализовать AVL или RB дерево)- синтаксические деревья и алгебраические выражения — например встроенный язык в программе Mathematica имеет много функциональных конструкций.А ее бесплатный аналог Maxima написан на lisp.

И почему-то все это с успехом делается на ИЯ.

_>Вообщем pattern matching -та черта ФЯ полезность которой не вызывает сомнений

+1

_>2.Для реализации алгоритмов легко распадающиеся не составные части

Для этого нужна поддержка компилятра вот и все. Тот же С++ прекрасно распараллеливается спец. средствами (например, от Интел).

_>3.Где активно применяется рекурсия например LL — разбор

Но опчему-то для постраения парсеров в ФЯ все равно создают постоители парсеров (вроде Яка/Лекса). А ЛЛ(1) легко делается методом рекурсивного спуска на любом ИЯ.

Так что приемущества именно в декларативности и фичах вроде патерн-матчинга и функциях высшего порядка.

Многое же выдаваемое за достоинство ФЯ на самом деле является всего лишь фичами конкретных языков и без проблем может быть реализовано (да и реализуется) на ИЯ.

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

N_>Быстрая сортировка на ФЯ:

N_>

N_>qsort []     = []
N_>qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
N_>                 where
N_>                   elts_lt_x   = [y | y <- xs, y < x]
N_>                   elts_greq_x = [y | y <- xs, y >= x]
N_>

ФЯ тут ни причем, это будет также просто и на императивном языке с
хорошей реализацией встроенных списков, например на питоне:

def qsort(aList): 
        if not aList: 
                return [] 
        ltList=[y for y in aList[1:] if y<aList[0]] 
        gtList=[y for y in aList[1:] if y>=aList[0]] 
        return qsort(ltList)+[aList[0]]+qsort(gtList)

N_>Решето эрастофена на ФЯ:

N_>

N_>ld n = ldf 2 n

N_>divides d n = rem n d == 0

N_>ldf k n | divides k n = k
N_>        | k^2 > n     = n
N_>        | otherwise   = ldf (k+1) n

N_>prime n | n < 1     = error "not a positive integer"
N_>        | n == 1    = False
N_>        | otherwise = ld n == n
N_>

это не решето эратосфена, это алгоритм в лоб (если я конечно не запутался в синтаксисе)

N_>Императивные аналоги, я думаю, Вы себе представляете.

зависит от языка


N_>На функциональных языках многое записывается проще. Проблема же состоит только в том, что современные компиляторы функциональных языков не могут сгененрировать эффективный код. Но это не принципиальная проблема. Рано или позно появятся эффективные компиляторы. Еще одна проблема функциональных языков — это убогая семантика массивов. Но и она, скорее всего, тоже окажется в прошлом.

насколько я понял из чтения документации по ocaml там уже есть обычные императивные
массивы.

N_>Идея любого языка программирования заключается в том, что бы переложить максимальное количество рутинной работы на компьютер. А для этого задача должна описываться на максимально возможном для машины уровне абстракции. Пока что для этого ничего лучше функционального и логического подхода не придумано.

Мне пока больше понравился импреративно-декларативный стиль питона. Не нравится только его динамическая типизация и то что интерпретатор(хотя если psyco доведут до ума то скорость будет очень хорошая).

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

N_>Хорошо, давайте сравним.
Ну давай попробуем
N_>Быстрая сортировка на ФЯ:
ну эту "быструю" сортировку уже со всех сторон обсасали в соседнем флейме.

N_>Решето эрастофена на ФЯ:
Я не спец в ФЯ но из того что мне удалось понять это не решето эратосфена, а тупейшая проверка одного числа на простоту.
N_>Императивные аналоги, я думаю, Вы себе представляете.
И переводится на С++ дословно

bool divides(int k, int n)
{
    return n%k==0;
}
int ldf(int k, int n)
{
    if(divides(k, n))   return k;
    if(k*k>n)           return n;
    return ldf(k+1, n);
}
int ld(int n)
{
    return ldf(2, n);
}
bool prime(int n)
{
    if(n<1)     throw "not a positive integer";
    if(n==1)    return false;
    return ld(n)==n;
}

что эквивалентно

bool prime(int n)
{
    if(n<1)     throw "not a positive integer";
    if(n==1)    return false;
    for(int k=2;k*k<=n;++k)
        if(n%k==0)
            return false;
    return true;
}

А вот простейшая реализация решита Эратосфена

int main()
{
    size_t size=100;
    std::vector<bool> is_prime(size, true);//помечаем все числа как простые
    for(size_t i=2;i<size;++i)//ищем очередное не вычеркнутое число
        if(is_prime[i])
        {
            //i очередное простое число
            for(size_t n=i+i;n<size;n+=i)//вычеркиваем все числа кратные данному числу
                is_prime[n]=false;
        }
}

Находит все простые числа меньше заданного. Изобрази этот алгоритм на функциональном языке, а мы посмеемся...

N_>На функциональных языках многое записывается проще.
Я бы сказал кое что
N_>Проблема же состоит только в том, что современные компиляторы функциональных языков не могут сгененрировать эффективный код.
N_>Но это не принципиальная проблема.
А! Ну-ну... интересно когда появится компилятор который будет способен превратить то что написал ты в решито Эратосфена... Тут настоящий AI нужен.
N_>Рано или позно появятся эффективные компиляторы.
Ой не скоро если вобще появятся... Алгоритм преобразовать это вам не рекурсию развернуть...
N_>Идея любого языка программирования заключается в том, что бы переложить максимальное количество рутинной работы на компьютер. А для этого задача должна описываться на максимально возможном для машины уровне абстракции.
Кто бы спорил.
N_>Пока что для этого ничего лучше функционального и логического подхода не придумано.
А вот это уже спорно.

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

VD>Это не быстрая сортировка. Это медленная. Да еще и алгоритм перевран.

VD>Ты классический реализуй. Так чтобы для перекидки брался средний элемент.

Удивительно, но у Кнута тогда он тоже перевран.

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

WH>А вот простейшая реализация решита Эратосфена
WH>

WH>int main()
WH>{
WH>    size_t size=100;
WH>    std::vector<bool> is_prime(size, true);//помечаем все числа как простые
WH>    for(size_t i=2;i<size;++i)//ищем очередное не вычеркнутое число
WH>        if(is_prime[i])
WH>        {
WH>            //i очередное простое число
WH>            for(size_t n=i+i;n<size;n+=i)//вычеркиваем все числа кратные данному числу
WH>                is_prime[n]=false;
WH>        }
WH>}
WH>

WH>Находит все простые числа меньше заданного. Изобрази этот алгоритм на функциональном языке, а мы посмеемся...

main = putStr (show (filter primes [1..100]))

primes определен как я писал выше.

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

VD>И почему-то все это с успехом делается на ИЯ.

VD>Для этого нужна поддержка компилятра вот и все. Тот же С++ прекрасно распараллеливается спец. средствами (например, от Интел).

VD>Но опчему-то для постраения парсеров в ФЯ все равно создают постоители парсеров (вроде Яка/Лекса). А ЛЛ(1) легко делается методом рекурсивного спуска на любом ИЯ.

VD>Так что приемущества именно в декларативности и фичах вроде патерн-матчинга и функциях высшего порядка.

VD>Многое же выдаваемое за достоинство ФЯ на самом деле является всего лишь фичами конкретных языков и без проблем может быть реализовано (да и реализуется) на ИЯ.

Голодная кума Лиса залезла в сад,
В нем винограду кисти рделись.
У кумушки глаза и зубы разгорелись;
А кисти сочные как яхонты горят;
Лишь то беда, висят они высоко:
Отколь и как она к ним ни зайдет,
Хоть видит око,
Да зуб неймет.
Пробившись попусту час целой,
Пошла и говорит с досадою: "Ну, что ж!
На взгляд-то он хорош,
Да зелен — ягодки нет зрелой:
Тотчас оскомину набьешь".

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

WH>>Находит все простые числа меньше заданного. Изобрази этот алгоритм на функциональном языке, а мы посмеемся...


N_>

N_>main = putStr (show (filter primes [1..100]))
N_>

N_>primes определен как я писал выше.

нет на самом деле уже смешно, про эффективность конечно вообще забываем, но ладно но различий с ИЯ тут тоже нет на C++ это тоже одна строка с готовой то функцией primes.

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

Насчет басни, лиса все-таки добралась до винограда, но не съедобный он для нее, вот и спрашивает как его вкуснее приготовить.

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

FR>ФЯ тут ни причем, это будет также просто и на императивном языке с
FR>хорошей реализацией встроенных списков, например на питоне:
Питон позволяет писать в функциональном стиле, было-бы желание. Что мы и видим в твоем примере. Так что ФЯ здесь причем — откуда, ты думаешь, в питоне взялись list comprehensions?

FR>

FR>def qsort(aList): 
FR>        if not aList: 
FR>                return [] 
FR>        ltList=[y for y in aList[1:] if y<aList[0]] 
FR>        gtList=[y for y in aList[1:] if y>=aList[0]] 
FR>        return qsort(ltList)+[aList[0]]+qsort(gtList) 
FR>