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

V> По всему видно, что использование ООД в чистых ФЯ затруднительно. А что же ФЯ предлагают в замен? А ничего.Приходится использовать старую структурную декомпозицию. Иногда этого хватает, например в случае с телекомом, но далеко не всегда.

ФЯ много чего предлагают, в том числе и объекты как OCaml. В Haskell'е есть классы типов, например, и монады.

V>1) Окружающий мир по своей природе императивен и непрерывно изменчив. Электроны вертятся вокруг ядра, молекулы находятся в броуновском движении, Земля вращается вокруг Солнца, люди рождаются и умирают и т.д. В этом смысле ФЯ не имеют ничего общего с реальным миром, они являются исключительно плодом человеческого воображения. Поэтому, ФЯ мало подходят для моделирования предметной области, связанной с окружающим миром, например для бухгалтерских систем.

Бездоказательные утверждения. В чем конкретно императивен мир? Разве есть какое-то глобальное состояние мира, которое дискретно меняется каждый такт времени?

V>2) Человек мыслит императивно. Если у Вас спросить, как приготовить чай, что вы ответите? Вы опишете последовательность действий: налить в чайник воду, вскипятить и пр. Врядли кто-то опишет набор функций,каскадный вызов которых приведет к появлению чая. То есть ИЯ ближе к человеческому мышлению, и, следовательно,более доступны ему.

В современной алгебре широко используется теория категорий, которая пришла на смену "императивной" теории множеств. А ФЯ основаны на лямбда исчислении, которое имеет прямую связь с так называемыми декартово-замкнутыми категориями. Так что бытовому разуму может быть императивный подход и ближе, но когда речь заходит о решении реально сложных задач, функциональный подход оказывается предпочтительней.
Кроме того, я сомневаюсь в императивности человеческого мышления вообще и уж точно оно не объектно-ориентированное. Лично я, когда думаю как приготовить чай, ищу решение проблемы отталкиваясь от предполагаемого результата. Т.е. нужен чай => нужна горячая вода и сам чай => нужно согреть воду => нужно набрать воду и т.д. Это не императивный подход.

B>О как у вас все запущено.

B>Будь добр, поделись со мной, и с другими, если это конечно не очень секретная информация, которая может быть передана исключительно Чистякову, при условии его личной заинтересованности.
RUP.

B>И вообще, ребята, давайте будем более терпимыми в отношении приверженцев других культур, религий, технологий и подходов, я понимаю что монотеистическое существование общества накладывает отпечатки на мышление и на стиль отношений с другими "конфессиями", от этого очень сложно отделаться всем без исключения, но давайте включим рационализм, свойственный программерам, и скажем себе что от того что кто то будет применять ФЯ ничего плохого не случится, равно как и от того, что кто то будет работать исключительно на ИЯ, в этом нет никакой ереси и крамолы.
У меня предложение попроще, способное на порядок поднять культуру общения. Давайте Чистякоа перестанет хамить и переходить на личности. Объясни это Чистякову. Я ему недавно объяснял подробно, он видимо не понимает.

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

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

VD>>>Так не трепался бы.
G>>Я и не треплюсь. В отличие от некоторых, я веду предметные разговоры.
VD> Я плякль...
Поплачь. Легче станет.

G>>Если пропасть состоит в том, что мэйнстрим-программистов интересует только то, что использует МС — то ее не увеличишь и не уменьшишь разговорами. И с такими людьми, которые не слушая аргументов долдонят одно и тоже, мне разговаривать не интересно, пусть думают что хотят.

VD>Значит не понял. Ну, тут ничего не поделашь.
А ты еще чего нибудь скажи, зачем так сразу сдаваться. Про демагогию, например, что-то давно слушно не было. Усомнись в моей профпригодности, в способности понимать русский язык. Побей себя копытом в грудь — скажи, что у тебя на дефект уходит 5 — нет, 3 минуты. Ну как ты там еще объясняешь? О, тяжелая артилерия. Попроси меня поверить тебе на слово. Все это разбавь безграмотными рассуждениями.

Репутацию свою ты уже не испортишь, а, как говорил поручик Ржевский, "можно и впердолить".

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

Q>Во всех этих 3-х строках кода неявно подразумевается ленивость вычислений. В реальности ни списки не будут бесконечно большими, ни filter не будет обрабатывать весь список и sieve тоже.
А теперь давай сравним производительность с этим
Re[2]: Решение в лоб мы решето Эратосфена

Автор: WolfHound
Дата: 23.06.04

Вот результаты
Re[3]: Решение в лоб мы решето Эратосфена

Автор: WolfHound
Дата: 24.06.04

ЗЫ Зы я знаю что сравнение не корректоно ибо у тебя алгоритм "в лоб"
ЗЗЫ А теперь попробуй на ФЯ написать решето эратосфена и так чтобы памяти жрало не больше чем моя реализация

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

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

Q>>Во всех этих 3-х строках кода неявно подразумевается ленивость вычислений. В реальности ни списки не будут бесконечно большими, ни filter не будет обрабатывать весь список и sieve тоже.
WH>А теперь давай сравним производительность с этим
WH>Re[2]: Решение в лоб мы решето Эратосфена

Автор: WolfHound
Дата: 23.06.04

WH>
WH>Вот результаты
WH>Re[3]: Решение в лоб мы решето Эратосфена

Автор: WolfHound
Дата: 24.06.04

WH>ЗЫ Зы я знаю что сравнение не корректоно ибо у тебя алгоритм "в лоб"
WH>ЗЗЫ А теперь попробуй на ФЯ написать решето эратосфена и так чтобы памяти жрало не больше чем моя реализация

На интерпретаторе (!) ghci под Windows на моей не самой быстрой машине первые 5000 (до 48619) чисел вычислились за 40 секунд, что примерно в 2 раза быстрее, чем на твоей программе . Знаю, знаю. Твоя программа сразу знала верхний предел и поэтому вычеркивала числа сразу до него . Но что же делать, я то имел ввиду ленивые вычисления, и моя программа могла бы быть написана более эффективно, если бы был задан верхний предел. Т.е. задачи решаются разные. Для сравнения нужна программа, которая заранее не знает сколько от нее потребуют простых чисел.
Кстати, OCaml, думаю, вообще не проиграл бы в производительности, поскольку на него твою программу можно перенести 1 в 1.

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


V>>1) Окружающий мир по своей природе императивен и непрерывно изменчив.
V>>Электроны вертятся вокруг ядра, молекулы находятся в броуновском

Q> Бездоказательные утверждения. В чем конкретно императивен мир? Разве
Q> есть какое-то глобальное состояние мира, которое дискретно меняется
Q> каждый такт времени?

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

Q> Так что бытовому разуму может быть
Q> императивный подход и ближе, но когда речь заходит о решении реально
Q> сложных задач, функциональный подход оказывается предпочтительней.
Q> Кроме того, я сомневаюсь в императивности человеческого мышления
Q> вообще и уж точно оно не объектно-ориентированное. Лично я, когда
Q> думаю как приготовить чай, ищу решение проблемы отталкиваясь от
Q> предполагаемого результата. Т.е. нужен чай => нужна горячая вода и
Q> сам чай => нужно согреть воду => нужно набрать воду и т.д. Это не
Q> императивный подход.

Допустим командир отряда с уже обученными десантннками обучает новичков, которые сидят на где-то на трибуне. Допустим он даже не отдает команд типа "стоять", "вперед"... а как-то руководит в функциональном стиле. Как будет обучатся новичок?

Для начала он локализует область наблюдения, потом станет отмечать то что он видит.

"Группа А переместилась из квадрата А в квадрат Б. Они стеляли. Со стороны открылась пальба, отряд залег."

И уже потом (позже) он опишет свой опыт как

"взятие высотки состоит в перемещении к ней со стрельбой и залегании при открытии ответного огня".

Как-то так. Причем, если ученика кинут в атаку, до того как он сумел сформулировать окончательную свою мысль, то его программа по всему будет походить на императивную.

PS. Я могу понять почему ФЯ торкнуло Гапертона, у него уже есть императивная база в виде 60 мегов. Если бы изначально был выбран только Хаскель, а условия предполагали меняющиеся требования к задаче, невозможность медлить с решением (более или менее качественным), то...

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

Q>ФЯ много чего предлагают, в том числе и объекты как OCaml. В Haskell'е есть классы типов, например, и монады.

Все так, вот только классы типов в Haskell к ООП отношения не имеют Класс типов — это просто набор функций, который должен бвть определен для всех типов, входящих в этот класс. Аналог интерфейса Java, вобщем.

Кстати, в ОКамле аналогом классом типов являются модули.

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

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

Q>>ФЯ много чего предлагают, в том числе и объекты как OCaml. В Haskell'е есть классы типов, например, и монады.

INT>Все так, вот только классы типов в Haskell к ООП отношения не имеют Класс типов — это просто набор функций, который должен бвть определен для всех типов, входящих в этот класс. Аналог интерфейса Java, вобщем.

INT>Кстати, в ОКамле аналогом классом типов являются модули.

А я и не говорил, что имеют. На интерфейсы они похожи, но реально есть определенные отличия.

Hello, VladD2!
You wrote on Sat, 04 Sep 2004 03:51:56 GMT:

S>> Воистину так. Я тоже однажды решил сэкономить чуть-чуть на спичках
S>> (лень было расчитывать, когда надо вид обновлять, а когда нет) и завяз
S>> в отложенных вычислениях по самые уши, когда код слегка разросся.

V> И естествнно даже не задумался, над тем что нужно было более тщательно
V> все спроектировать...

И без "ленивых" вычислений, естественно.

V> Переписал все на ФЯ и все само сабой заработала. Причем быстрее белее и
V> пушистее...

Ленивые вычисления — да. Белее и пушистее.

With best regards, Sergey.

G>Сомневаюсь, что на С++ получится проще.

Конечные автоматы нет нужды писать на С/C++. Проще писать на чем-то более подходящем (например на SDL), а затем генерить C(или C++) код. Получается эффективней.

Если очень хочется писать их реализацию ручками, то тоже можно. Это хорошо описано здесь :
"Practical Statecharts in C/C++: Quantum Programming for Embedded"
http://www.amazon.com/exec/obidos/tg/detail/-/1578201101/qid=1094468408/sr=1-1/ref=sr_1_1/002-6078401-9507225?v=glance&s=books

Причем можно писать не только обычные, плоские автоматы, но и иерархические, включая наследование и переопределение state-ов с transition-ами.

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


V>У меня появилось нестерпимое желание вставить свои пять копеек в этот очень интересный разговор, что я сейчас и сделаю

V>Вот несколько мыслей о жизни, все ИМХО, и если я не прав, поправте меня.

V>Начну из далека. Как всем хорошо известно, совпеменное ПО характеризуется высокой сложностью. Разрешить сложность таких систем можно с помощью декомпозиции их на мелкие и следовательно простые части. Эту самую декомпозицию можно проводить различными способами, причем задача декомпозиции сама по себе весьма нетривиальна. Исторически первым подходом к решению данной проблемы была структурная декомпозиция. Поначалу всё было хорошо, и все были довольны. Но время шло и ПО становилось все сложнее и сложнее. Выяснилось, что сделать эффективную декомпозицию сложной системы с помощью структурного подхода крайне трудно. Поэтому, был предложен объектно-ориентированный сбособ декомпозиции сложной системы, имеющий ряд весомых преимуществ по сравнению со стуктурным. На данный момент, ООД является доминирующим подходом, что будет дальше неизвестно. Напомню вкраце основные принципы ООП. Система состоит из объектов и каждый объект имеет изменяемое состояние. Он может посылать сообщения другим объектам и тем самым вызывать изменение их состояния.

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

Все ФЯ позволяют делать инкапсуляцию.

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

А что до наследования реализации, то это поддерживается явно в OCaml, и никаких принципиальных сложностей с реализацией этого в ФЯ нет. А в тех, где не поддерживается, подобное поведение достигается достаточно легко благодаря более развитому полиморфизму. Благодаря ему же, необходимость в применении наследования уменьшается (посмотрите STL в качестве иллюстрации, хоть С++ и не ФЯ, но дизайн похож).

V> По всему видно, что использование ООД в чистых ФЯ затруднительно. А что же ФЯ предлагают в замен? А ничего. Приходится использовать старую структурную декомпозицию. Иногда этого хватает, например в случае с телекомом, но далеко не всегда.

Во первых, это не так. В случае телекома применяется т. н. Concurrent Programming, где программа на высшем уровне декомпозиции состоит из большого (десятки тысяч и больше) количества взаимодействующих процессов. Декомпозиция является с одной стороны объектной (в терминах Алана Кея), т. к. процесс имеет инкапсулированное состояние, и взаимодействует с миром через посылку сообщений. С другой стороны — функциональной (в терминах Data Flow Diagram).

А во вторых,нет необходимости предлагать что-то взамен, если можно предложить в дополнение.

V> Читая эту ветку, у меня сложилось впечатление, что основной лейтмотив защитников ФЯ таков: "ввиду наличия состояний программы написанной на императивном языке, её труднее отлаживать и сопровождать, поэтому надо перейти к ФЯ, лишенных этих недостатков". Можно провести аналогию с таким утверждением: "Автомобили загрязняют атмосферу, поэтому надо перейти на велосипеды". Эти утверждения выглядят вполне логично, но есть одно "НО". Можно ли применять велосипеды в той же мере, в какой применяются автомобили? Очевидно, что не всегда. Но можно говорить о рамках применимости. Это же касается и ФЯ. Так, например, я считаю, что ФЯ плохо подходят для разработки мощного текстового редактора, типа ворда (я не имею ввиду "экстремальный спорт", понятно что "раком" можно и до Китая доскакать).

В этой ветке кое-кто уперся рогом на тему, что неопределенный порядок вычислений якобы не представляет опасности в ИЯ (т. е. при наличии побочных эффектов). Не советую составлять впечатление о преимуществах ФЯ из прений сторон на эту тему.

Это один из плюсов. Но далеко не единственный — ФЯ характеризуются не только теми вещами, которых в них нет (состояний). Основной плюс на самом деле — в декларативном описании алгоритмов и данных. Сравните программирование на Transact SQL и разработку под dBase-подобные базы — будет похоже.

V>И еще пара замечаний.

V>1) Окружающий мир по своей природе императивен и непрерывно изменчив. Электроны вертятся вокруг ядра, молекулы находятся в броуновском движении, Земля вращается вокруг Солнца, люди рождаются и умирают и т.д. В этом смысле ФЯ не имеют ничего общего с реальным миром, они являются исключительно плодом человеческого воображения. Поэтому, ФЯ мало подходят для моделирования предметной области, связанной с окружающим миром, например для бухгалтерских систем.

При этом в бизнес-анализе и моделировании часто применяются функциональные модели — IDEF0 и DFD. Парадокс.

V>2) Человек мыслит императивно. Если у Вас спросить, как приготовить чай, что вы ответите? Вы опишете последовательность действий: налить в чайник воду, вскипятить и пр. Врядли кто-то опишет набор функций,каскадный вызов которых приведет к появлению чая. То есть ИЯ ближе к человеческому мышлению, и, следовательно,более доступны ему.

Все аналогии ущербны. Но раз уж ты начал...

Чтобы сделать чай, мне нужен кипяток и заварка.
Чтобы сделать кипяток, мне нужно электричество, и чайник с водой.
Чтобы получить чайник с водой, мне нужен пустой чайник и водопроводная вода.

Это я помню. И могу без проблем сделать себе чай. А алгоритм для себя составлять каждый раз как-то ломает. Это пусть делают те, кто мыслят только императивно

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

_O_>Конечные автоматы нет нужды писать на С/C++. Проще писать на чем-то более подходящем (например на SDL), а затем генерить C(или C++) код. Получается эффективней.
Знаю. Только известные мне SDL тулзы очень дорогие (кинь ссылки, если знаешь халяву, плз). Но в любом случае, иногда приходится делать КА и руками.

_O_>Если очень хочется писать их реализацию ручками, то тоже можно. Это хорошо описано здесь :
_O_>"Practical Statecharts in C/C++: Quantum Programming for Embedded"
_O_>http://www.amazon.com/exec/obidos/tg/detail/-/1578201101/qid=1094468408/sr=1-1/ref=sr_1_1/002-6078401-9507225?v=glance&s=books
Да вроде я и так это умею. Но за ссылку все равно спасибо, не знал, что на такие темы книги пишут.

Здравствуйте.
Есть два вопроса к гуру ФЯ.
1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).
2.Отсутствие циклических структур данных или их эмуляция — это тоже достоинство?
С деревом на ФЯ работать одно удовольствие.А вот с графом...Есть конечно fgl.Но это эмуляция графа деревом.Ну нет той чистой простоты
По-видимому если две ссылки от двух вершин указывают на третью то они должны указавать на одну и ту же вершину.Это противоречит великому принципу ФЯ?

У меня складывается впечатление что легко и быстро можно работать только с односвязными списками и деревьями всех мастей — здесь все для вас и конструкторы и pattern matching .. А вот уже массивы не вкладываютя в общую
систему и необходима специальная поддержка компилятора чтобы доступ не стал O(n) И двусвязные списки тудаже.
.string1++string2 за время O(length(string2)) — work around в виде списка функций

Фундаментальной структурой данных ИЯ является массив — ФЯ дерево?

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

_>Здравствуйте.
_>Есть два вопроса к гуру ФЯ.
_>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).

Вопрос не очень понятен. Java и C++ оба императивные, но выполняются с существенно разной скоростью. Или если уж исключить интерпретаторы, то C и C++ отличаются по скорости. Да и не столь она важна в наши дни. PHP, Perl, Pyton процветают, хотя по скоростным качествам С лучше.


_>2.Отсутствие циклических структур данных или их эмуляция — это тоже достоинство?
_>С деревом на ФЯ работать одно удовольствие.А вот с графом...Есть конечно fgl.Но это эмуляция графа деревом.Ну нет той чистой простоты
_>По-видимому если две ссылки от двух вершин указывают на третью то они должны указавать на одну и ту же вершину.Это противоречит великому принципу ФЯ?

Графы фактически являются массивами. Представление их в виде отдельных объектов -ребер со ссылками на соседей не очень удобно на мой взгляд.

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

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

_>>Здравствуйте.
_>>Есть два вопроса к гуру ФЯ.
_>>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).

Q>Вопрос не очень понятен. Java и C++ оба императивные, но выполняются с существенно разной скоростью. Или если уж исключить интерпретаторы, то C и C++ отличаются по скорости. Да и не столь она важна в наши дни. PHP, Perl, Pyton процветают, хотя по скоростным качествам С лучше.

Для каждого алгорима есть асимпотическое(по количеству входных данных) время.Некоторые алгоритмы на ФЯ не перепишешь.Ну так вот аналогичный на ФП будет такой же скорости

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

_>Здравствуйте.
_>Есть два вопроса к гуру ФЯ.
_>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).
Не знаю, возможно-ли дать такое доказательство и существует ли оно. Думаю, для подавляющего большинства задач это верно. Во всяком случае, контрпримера пока не видал. Приведете?

_>2.Отсутствие циклических структур данных или их эмуляция — это тоже достоинство?
Ну наконец кто-то начал говорить о настоящих проблемах ФЯ. Ок, побеседуем. Представляю, какие радостные крики сейчас начнутся.
_>С деревом на ФЯ работать одно удовольствие.
Сформулируем более общо. С типами, алгоритмами, и данными которые допускают рекурсивные определения работать одно удовольствие.
_>А вот с графом...Есть конечно fgl.Но это эмуляция графа деревом.Ну нет той чистой простоты
_>По-видимому если две ссылки от двух вершин указывают на третью то они должны указавать на одну и ту же вершину.Это противоречит великому принципу ФЯ?
Нет конечно. Зачем, кстати, язвить? Вершины могут и будут разделяться, так что с ациклическими графами проблем нет. Настоящие циклические ссылки тоже возможны — но подграф с циклом должен быть создан сразу, модификацией такого не достичь. Есть соответствующие примеры на Хаскеле.

Т. е. настоящая проблема (вернее, принципиальное ограничение) формулируется так. Невозможно менять состояние элементов функциональной циклической структуры по отдельности, она может быть изменена только целиком. Что не очень эффективно. И никакие трюки вроде монад и uniqueness typing здесь не помогут. Однако надо понимать, что
1) Это является принципиальной проблемой только "чистых" ФЯ, которые не допускают побочных эффектов. А это только Clean и Haskell.
2) При этом, это совершенно не смертельно. Для графа существует несколько вариантов эффективных по памяти и скорости представлений, не содержащих прямых циклических ссылок. В ФЯ мы будет переходить от одного представления к другому, в зависимости от того, какие операции доминируют в данный момент, чтения или модификации. Т. е. мы будем применять т. н. functional update. См. ниже, на примере массивов.
3) Используя ФЯ с императивными расширениями, вроде OCaml, мы всегда можем перейти к императивному стилю, если не хватит скорости. В OCaml весьма гладкая сшивка императивных и функциональных возможностей.

_>У меня складывается впечатление что легко и быстро можно работать только с односвязными списками и деревьями всех мастей — здесь все для вас и конструкторы и pattern matching .. А вот уже массивы не вкладываютя в общую
_>систему и необходима специальная поддержка компилятора чтобы доступ не стал O(n).
Неправда. Укладываются великолепно в сочетании с list и array comprehensions. Доступ к массивам всегда O(1). А на поэлементной модификации можно словить и O(N), если захотеть. А если не хочется, то:
1) Если модифицируется весь или большая часть массива, то он обычно пересоздается целиком один раз с уже измененными элементами (используя list или array comprehensions), и никакого N^2 там не будет. Без всякой поддержки компилятора — это так называемый functional array update, возможный в любом ФЯ. Записывается кратко и удобно. По вычислительной сложности не проигрывает обычному деструктивному изменению. Пример на Хаскелездесь

Автор: Gaperton
Дата: 15.06.04

.

2) Чтобы получить деструктивное O(1) изменение массива в Хаскель, достаточно воспользоваться монадой ST. В Clean — достаточно указать, что массив уникален (воспользоваться uniqueness typing). А остальные распространенные языки разрешают побочные эффекты. Так что массивы можно модифицировать по одному элементу быстро и без напрягов делая прямое деструктивное изменение. Единственный из популярных ФЯ где так делать нельзя — Erlang.

Итого, настоящая проблема: В Erlang поэлементное изменение массива имеет сложность O(N).

_> И двусвязные списки тудаже.
С этим та же ситуация, что и с графами, т. е. такой список может быть изменен только будучи целиком созданным заново. Но меньше способов выкрутится. Тем не менее, они есть.
1) Первый (для чистых ФЯ) состоит в разворачивании однонаправленного списка по мере необходимости. Скажете, это не эффективно? Да, конечно. Но и не смертельно, мы ведь говорим о вычислительной сложности, так? Рассмотрим пример — надо реализовать очередь. Делаем ее на паре двунаправленных списков. Кладем поступающие элементы в первый список. Забираем элементы из второго списка. Если он пуст (!) присваиваем ему результат разворота первого списка, первый список делаем пустым. Эта структура известна как Okasaki Queue, и имеет средневзвешенную сложность операций put и get равную O(1).

2) Второй (для чистых ФЯ) — использовать read-only двунаправленные списки, пересоздавать их используя групповые изменения, как с массивами.

3) Третий — пользуемся императивными расширениями, если не хватило производительности.

_>.string1++string2 за время O(length(string2)) — work around в виде списка функций
Проблема многих ФЯ в том, что строки там представлены списками. Вот где ужас-то, на самом деле. Строки там медленные. Ну, кроме тех ФЯ, где строки представлены массивами . Например Clean.

_>Фундаментальной структурой данных ИЯ является массив — ФЯ дерево?
Для ФЯ — скорее список.

From: little_alex

я не гуру, но отвечу, гуру поправят.

>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).

Можно смело сказать что "Нет", твои первые программы на ФЯ будут работать намного медленнее. Но учитывая, что скорость выполенения не самый важный фактор в программировании, а о скорости программы с ошибками вообще говорить не приходится, и что на ФЯ за то же время ты сможешь написать их больше, так что выигрыш в баксах/месяц и для тебя и для заказчика должен быть.
ФЯ вообще расчитаны не на современные процессоры, у меня сложилось ощущение что для ФЯ-процессора достаточно нескольких сотен транизисторов, т.е. в какой-нибудь мультипроцессорной архитектуре будущего все будет работать в памяти, а не в процессоре, а по шинам будут течь не данные, а контексты процессоров.
Оптимизацию для ФЯ делать теоретически легче, поэтому ей занимаются не программисты, а компиляторы.

>2.Отсутствие циклических структур данных или их эмуляция — это тоже достоинство?
С деревом на ФЯ работать одно удовольствие.А вот с графом...Есть конечно fgl.Но это эмуляция графа деревом.Ну нет той чистой простоты

Граф можно представить деревом и соответствующие многоуровневые шаблоны тоже можно разложить в одноуровневые, читай про суперкомбинаторы. ФЯ-программистам и в голову не придет писать процедуры на несколько страниц. Дерево, конечно, получится на уровень выше, а в листьях будут повторы, но они вычисляются только один раз, или вообще не вычисляются . У ФЯ оптимизация отчасти происходит в run-time, поэтому предсказать скорость трудно. Важнее то, что ФЯ требует больше памяти, если начнется своп, вот это будет заметно.

>По-видимому если две ссылки от двух вершин указывают на третью то они должны указавать на одну и ту же вершину.Это противоречит великому принципу ФЯ?

Какому принципу? У графа ведь нет корня, ты его описываешь со всех сторон как тебе удобнее. Пиши так, чтобы та вершина была вершиной дерева, а не листом.

>У меня складывается впечатление что легко и быстро можно работать только с односвязными списками и деревьями всех мастей — здесь все для вас и конструкторы и pattern matching .. А вот уже массивы не вкладываютя в общую
систему и необходима специальная поддержка компилятора чтобы доступ не стал O(n) И двусвязные списки тудаже.
.string1++string2 за время O(length(string2)) — work around в виде списка функций

Имхо, выражение в С++ вроде "a[5]" это декларативный стиль. Мы говорим пятый элемент. Элемент, который пятый. Так что это должно оптимизироваться и в родном для такого стиля ФЯ. Думаю с массивами сложностей не должно быть, а вот со сложными структурами ФЯ действильно удобнее. И вообще, массивы в ФЯ не обрабатываются, там вообще ничего не обрабатывается, там все описывается. Выполнение программы мне представляется таким наслоение новых слоев данных, то, что нужно остается, а лишний мусор убирается. Новое состояние массива строится поверх старого, а старый убирается когда станет ненужен. На прежнем месте присваивания происходят при выполнении если компилятор определил что можно так с-оптимизировать.

>Фундаментальной структурой данных ИЯ является массив — ФЯ дерево?

Неа, фундаментальной структурой данных является функция
Тут не надо думать что программы это алгоритмы и структуры данных. В осмысленные единицы системы там инкапсулируются не алгоритмы со структурами и потом туда бинарно заливаются данные и запускаются методы. ФЯ программа это не мясорубка в которую входят аргументы и из них делается результат. ФЯ строит результат из своего сырья, но "на тему" аргументов.

Lloyd -> "Re[16]: Сильные стороны функционального программирования" :

L> журнала и насколько я помню, это у тебя в профайле по крайней пере
L> пару лет уже записано. Судя по пикче, которая у тебя в профайле же,
L> тебе не очень много лет. Думаю вряд ли взрослый серьезный человек

Чувааааак. Это же DOOM! Возможно даже 1-й. А это как минимум 8 лет назад

Yury Kopyl aka hrg | http://id.totem.ru | Все вышесказанное является моим
личным мнением и может быть использовано против вас

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

_>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).

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

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

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

_>>1.Есть ли док-во того что на современных машинах программа на ФЯ будет выполняться с такой-же скоростью как и на императивном.Сравниваем языки а не компиляторы .Поэтому предполагаем отсутствие оптимизации и забиваем на константный множитель (сравниваем log(N) < N; 10N == N ).

S_>А это не совсем правильно сравнивать скорость языков а не компиляторов... языки не обладают ни скоростью ни производительностью, такими свойствами обладают компиляторы и оптимизаторы. Цель языка описать задачу. И потенциально компиляторы более декларативных языков более производительны, так как языки им оставляют больше свободы для оптимизации.
Вообще — правильно человек вопрос ставит . Он говорит о вычислительной сложности.

При этом, так как монада ST и uniqueness typing гарантируют то, что на объект будет единственная ссылка, то возможно деструктивное изменение с сохранением функциональной семантики. Эти вещи являются частью языка, и программист рассчитывает на деструктивное изменение применяя такие вещи. Я предполагаю, что little_alex со мной согласен.

"Оптимизацией" являются такие вещи, например, как single threadness analyzis, который программистом явно не контроллируется, частью языка не является, и способен в ряде случаев радикально улучшить производительность функциональной программы. Считаем это жульничеством, божественным вмешательством, и оптимизацией.