Здравствуйте, FR, Вы писали:
FR>По моему пример должен был продемонстрировать выразительность кода
Ну не знаю. Возможность просто использовать рекурсию — вполне конкретна и содержательна, а про какую-то "выразительность" это не скажешь.
FR>Да доказываю твой тезис что ocaml неплохой императивный язык.
Едва ли с этим будет кто-то спорить.
FR>Но с уточнением что код получается и по виду и по стилю скорее функциональным.
Мы ведь вроде программисты, а не стилисты.
Да и по функциональности окамловкий и плюсовой код не соотвествуют хаскельному — продюсер должен знать кол-во чисел.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, <Аноним>, Вы писали:
А>а не проще ли тебе признать, что ты не прав?
В чем неправ? В том, что списки нужны и map нужен?
А>объясни, какие такие алгоритмы "требуют" обращения к произвольному элементу в твоем понимании? А>умело используя придуманную тобой "минимальность", можно *вообще* обойтись без обращения к произвольному элементу А>вот так: вместо a[i] пишем get_element(a, i), где А>
int get_element(stack a, int i) {
А> if( i==0 )
А> return a.head();
А> else
А> return get_element(a.tail(), i-1);
А>}
Ну и зачем все сводить к абсурду? При таком подходе сложность доступа по индексу O(n).
А>а сейчас он не имеет смысла БЕЗ указания скорости работы
Без указания алгоритмической сложности. А у моих построений с этим все в порядке.
А>теперь на более глобальную тему А>почему ты решил, что в *практическом* программировании map всегда должна выражаться через стековые операции, назовем их head и tail, или, что наверно то же, через forward iterator для обхода?
Map для списка. На другие рекурсивные иммутабельные структуры рассуждения из первого поста тоже можно распространить.
А>я считаю рациональным у любого контейнера иметь forward iterator для его обхода,
Непонятно, кстати, почему вы тут так много рассуждение про "итераторы для обходов", потому как в треде обсуждаются совсем другие подходы для работы с коллекциями.
А>но это не значит, что функция map не нужна, или что она не должна юзать random access iterator, *если он есть*
Ну и с этим спорит разве кто-нибудь?
А>дальше, map может быть достаточно сложно устроена чтобы она работала быстро
Может и будет и уже есть. А может быть устроена просто. О чем и разговор.
А>особенно в многопоточной программе
Все обсуждаемые тут мапы последовательные, а не параллельные.
Обсудите это лучше с окамлистами, им многопоточность не нужна также как и списки с мапами.
А>твои восторги "ах, мы можем написать map в две строчки!!!1111111" -- это какой-то детсад
Ни быстротой, ни многопоточностью различия между обсуждаемыми здесь двустрочной и 12-истрочной функциями не обусловлены, так к чему эти разговоры?
А>вполне возможно
Кому интересно, параллельный мап для списка на хаскеле реализуется на основе обычного последовательного map навешиванием стратегии параллельного вычисления:
parMap strat f = (`using` parList strat) . map f
Это более высокоуровневый способ, есть более низкоуровневый с большим контролем:
parMap f xs = mapM (pval . f) xs >>= mapM get
Тут используем монаду Par и опять-таки готовую последовательную mapM, на которую распространяются все, что было сказано про map в этом треде (собственно, map — это ее частный случай).
Реальный библиотечный код из пакетов parallel и monad-par. В окамле параллельного map для списка нет, потому что "не нужен".
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[23]: Строгость и нищета списков.
От:
Аноним
Дата:
16.12.11 12:20
Оценка:
K>Ну и зачем все сводить к абсурду? При таком подходе сложность доступа по индексу O(n).
вижу прогресс -- ты наконец-то заговорил про сложность
вот давай про нее и поговорим, и не только про безликие О(...), а еще про ту константу, на которую умножается n
K>Без указания алгоритмической сложности. А у моих построений с этим все в порядке.
бугага
у тебя со сложностью хреново, и будет хреново
если ты выдаешь наружу интерфейс последовательного доступа, когда есть возможность обращатся произвольно -- то в общем случае ты тормозииииииииишь; да, ты можешь попытаться найти частные случаи, когда этих тормозов не будет -- но они развалятся, как только ты выйдешь из своего детского сада в реальный мир...
K>Все обсуждаемые тут мапы последовательные, а не параллельные.
... в реальный мир, где на ваши, с позволения сказать, язычки обратили внимание только потому, что сейчас актуальна многопоточность, а функциональщина для нее как раз интересна
мап *должен* работать максимально быстро, а не просто О(эн), и *должен* иметь многопоточную версию
в своей статье ты справедливо высмеиваешь тех, у котого однопоточный мап работает хреново (причем, кстати, в достаточно редком случае spine-strict), но как только дело доходит до реального мира с его многопоточностью -- пытаешься спрятаться в кусты
K>Обсудите это лучше с окамлистами, им многопоточность не нужна также как и списки с мапами.
я буду обсуждать содержимое твоей статьи в основном с тобой
хотя, если господа окамлисты посоветуют мне хорошую статью про систему модулей окамла (ее хвалят), обязательно прочту
Re[23]: Строгость и нищета списков.
От:
Аноним
Дата:
16.12.11 12:36
Оценка:
А>>а не проще ли тебе признать, что ты не прав?
K>В чем неправ? В том, что списки нужны и map нужен?
ну ты даешь, епрст
списки и мап конечно нужны, а неправ ты в том, что пытаешься доказать, что 640 килобайт хватит всем map-у хватит последовательного доступа, даже если имеется произвольный
Здравствуйте, <Аноним>, Вы писали:
А>вот давай про нее и поговорим, и не только про безликие О(...)
Уже смешно.
А>а еще про ту константу, на которую умножается n
Ну, говорите.
А>у тебя со сложностью хреново, и будет хреново
O(1) — для доступа к вершине стека (а никакого другого доступа там не нужно) это "хреновая" сложность? Ну, ну.
А>если ты выдаешь наружу интерфейс последовательного доступа,
Какой интерфейс, на какую "ружу"?
А> когда есть возможность обращатся произвольно -- то в общем случае ты тормозииииииииишь; да, ты можешь попытаться найти частные случаи, когда этих тормозов не будет -- но они развалятся, как только ты выйдешь из своего детского сада в реальный мир...
Т.е. в реальном мире списки таки не нужны? Или я вас неправильно понял?
А>... в реальный мир, где на ваши, с позволения сказать, язычки обратили внимание только потому, что сейчас актуальна многопоточность, а функциональщина для нее как раз интересна
В большинстве этих, как вы выразились "язычков" с многопоточностью дела обстоят не здорово. Вы там в совем "реальном мире" все так от реальности оторваны?
А>мап *должен* работать максимально быстро, а не просто О(эн),
И двухстрочная и 12-истрочная версии максимально быстро и работают (для ленивых и spine-strict соотвественно).
А>и *должен* иметь многопоточную версию
Последовательный мап не нужен? Впрочем, многопоточные версии для хаскеля я показал. В других языках дела сложнее обстоят.
А>в своей статье ты справедливо высмеиваешь тех, у котого однопоточный мап работает хреново
В моей статье все мапы кроме одного работают нормально (не все одинаково быстро). а в этой подветке обсуждается, скажем так, вообще не работающий вариант.
А>(причем, кстати, в достаточно редком случае spine-strict)
Это, по-вашему, достаточно редкий случай? Но в большинстве ФЯ списки как раз такие.
А>, но как только дело доходит до реального мира с его многопоточностью -- пытаешься спрятаться в кусты
С чего бы это? Я бы и многопоточность пообсуждал, но для начала нужно провентилировать один вопрос: как это все связано с практичностью нехвосторекурсивного map из std-lib и нужностью списков, которые обсуждались в конкретной подветке. Я вот думаю, что никак.
А>я буду обсуждать содержимое твоей статьи в основном с тобой
Но разговор, который вы начали не имеет никакого отношения к содержанию моей статьи.
А>хотя, если господа окамлисты посоветуют мне хорошую статью про систему модулей окамла (ее хвалят), обязательно прочту
Советую "Understanding and Evolving the ML Module System by Derek Dreyer".
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, <Аноним>, Вы тред-то вообще читали?
А>списки и мап конечно нужны
Т.е. прав я.
А>а неправ ты в том, что пытаешься доказать, что 640 килобайт хватит всем map-у хватит последовательного доступа, даже если имеется произвольный
То, что 2048 килобайт всем достаточно тут пытался доказать D.Mon, пока не решил, что map не нужен вообще. А про "если имеется произвольный" — я вовсе ничего не говорил. Я говорил о том, что при отсутствии произвольного доступа map может быть нужен, и приводил минимальный пример такого алгоритма.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, D. Mon, Вы писали:
DM>Всевозможные деревья — тоже обычно рекурсивные типы, но сложность операций с ними другая. Их я не считаю непрактичными, но про них Klapaucius не писал, просто так на них его пост не обобщается, вроде.
Обобщается на все линейно-рекурсивные, как минимум (может и больше, но мне лень думать). Из практически полезных — потоки, например. Вообще, в энергичных вариантах потоки немного совсем не работают, а в ленивых — норм. Не всё, что дозволено Хаскелисту, дозволено окамлисту
А вообще, хватит пинать труп Окамла, давайте лучше вместе е@@нём по Джаве!
Здравствуйте, Паблик Морозов, Вы писали:
DM>>Всевозможные деревья — тоже обычно рекурсивные типы, но сложность операций с ними другая. Их я не считаю непрактичными, но про них Klapaucius не писал, просто так на них его пост не обобщается, вроде.
ПМ>Обобщается на все линейно-рекурсивные, как минимум (может и больше, но мне лень думать). Из практически полезных — потоки, например. Вообще, в энергичных вариантах потоки немного совсем не работают, а в ленивых — норм. Не всё, что дозволено Хаскелисту, дозволено окамлисту
Ну если к энергичным добавить call/cc потоки и многое другое внезапно начинают работать, но цена конечно такая же как у ленивости если не больше.
ПМ>А вообще, хватит пинать труп Окамла, давайте лучше вместе е@@нём по Джаве!
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Обобщается на все линейно-рекурсивные, как минимум (может и больше, но мне лень думать).
Обобщается на все рекурсивные. (Но если окамлисту не нужны списки, ему и несбалансированные деревья, например, тоже не нужны).
ПМ>А вообще, хватит пинать труп Окамла, давайте лучше вместе е@@нём по Джаве!
"Статья", вообще-то, пинает в одинаковой степени все энергичные языки (ну, исключая всякие экзотические реализации с CPS-трансформацией) включая и Джаву. Но возбудила статья одних только окамлистов.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>"Статья", вообще-то, пинает в одинаковой степени все энергичные языки (ну, исключая всякие экзотические реализации с CPS-трансформацией) включая и Джаву. Но возбудила статья одних только окамлистов.
У явистов что-то функции map в стандартной библиотеке не наблюдается
Здравствуйте, Klapaucius, Вы писали:
FR>>У явистов что-то функции map в стандартной библиотеке не наблюдается
K>Нет map — нет и проблемы? Ну, в нестандартной-то functionaljava map есть:
Конечно нет, так как 99% явистов вряд ли даже слышали о functionaljava.
И вообще какая функциональнальщина на яве не смешно даже, вот C++ совсем другое дело, настоящая кошерная
ленивая функциональщина http://www.boost.org/doc/libs/1_48_0/libs/phoenix/doc/html/index.html притом в
библиотеке являющейся практически неформально стандартной.
Кстати надо будет поковырять насчет быстродействия этот кошмар.
Здравствуйте, FR, Вы писали:
FR>Конечно нет, так как 99% явистов вряд ли даже слышали о functionaljava.
Я думаю, что это сильно завышенная оценка. 1% ява-программистов — это очень много. Думаю раз в 100 больше, чем программистов, слышавших про окамл.
Но причина, по которой тема не взволновала джавистов, в общем, понятна. Им односвязные списки действительно не нужны — они без них как-то обходятся, в отличие от окамлистов, которым списки не нужны только в этом треде, а в реальности они их используют.
FR>И вообще какая функциональнальщина на яве не смешно даже, вот C++ совсем другое дело, настоящая кошерная FR>ленивая функциональщина http://www.boost.org/doc/libs/1_48_0/libs/phoenix/doc/html/index.html притом в
Вообще, в языках без GC upward funarg problem как следует не решается. А вот в яве вся "функциональщина" отличается от окамловской "функциональщины" только синтаксисом. Не подумайте только, что я считаю это несущественным различием. Синтасксис — это очень важно. Благодаря этому на окамле можно писать красивый неработающий функциональный код, а на яве — только уродливый.
FR>библиотеке являющейся практически неформально стандартной.
Согласен насчет неформально (де факто) стандартной. Иначе бы она в мой обзор не попала.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
FR>>Конечно нет, так как 99% явистов вряд ли даже слышали о functionaljava.
K>Я думаю, что это сильно завышенная оценка. 1% ява-программистов — это очень много. Думаю раз в 100 больше, чем программистов, слышавших про окамл.
Мой палец говорит что их в 100 раз меньше чем камлистов, так как любой вменяемый явщик скорее воспользуется Scala или другим
поддерживающим ФП языком под платформу, а не будет так жестко извращаться.
K>Но причина, по которой тема не взволновала джавистов, в общем, понятна. Им односвязные списки действительно не нужны — они без них как-то обходятся, в отличие от окамлистов, которым списки не нужны только в этом треде, а в реальности они их используют.
Не надо обобщать на всех окамлистов в этом треде.
FR>>И вообще какая функциональнальщина на яве не смешно даже, вот C++ совсем другое дело, настоящая кошерная FR>>ленивая функциональщина http://www.boost.org/doc/libs/1_48_0/libs/phoenix/doc/html/index.html притом в
K>Вообще, в языках без GC upward funarg problem как следует не решается.
Ты недооцениваешь Phoenix там не только функции а даже их аргументы и значения эмулируются. В результате вместо нативного кода получаем один большой функтор.
K>А вот в яве вся "функциональщина" отличается от окамловской "функциональщины" только синтаксисом.
Нет, ты как минимум забываешь замыкания, это уже семантика.
K>Не подумайте только, что я считаю это несущественным различием. Синтасксис — это очень важно. Благодаря этому на окамле можно писать красивый неработающий функциональный код, а на яве — только уродливый.
Сам дурак
FR>>библиотеке являющейся практически неформально стандартной.
K>Согласен насчет неформально (де факто) стандартной. Иначе бы она в мой обзор не попала.
Тут не понял кто попал в твой обзор и где этот обзор.
Здравствуйте, Klapaucius, Вы писали:
K>Но причина, по которой тема не взволновала джавистов, в общем, понятна. Им односвязные списки действительно не нужны — они без них как-то обходятся, в отличие от окамлистов, которым списки не нужны только в этом треде, а в реальности они их используют.
Окамлистам списки разумного размера нужны, они их используют (и я среди них). И все работает.
А неразумное применение списков и хаскеллистам не нужно:
иначе я бы и для 10к элементов не стал бы его использовать
Здравствуйте, FR, Вы писали:
FR>Мой палец говорит что их в 100 раз меньше чем камлистов
Вот это уже более реальная оценка.
FR>так как любой вменяемый явщик скорее воспользуется Scala или другим поддерживающим ФП языком под платформу, а не будет так жестко извращаться.
В мейнстриме, вообще-то, не программист выбирает язык и протащить в продакшн извращения может и не просто, но примерно в 1024 раза легче, чем более нормальный язык. Не знаю, как дела с явой обстоят, но в коде на С# и C++ такие извращения встречаются.
FR>получаем один большой функтор.
Upwards funarg problem в общем случае так не решить.
FR>Нет, ты как минимум забываешь замыкания, это уже семантика.
Замыкания в яве есть, семантика, в принципе, на окамл похожа.
FR>Тут не понял кто попал в твой обзор и где этот обзор.
В первом посте треда. Код только из (почти) стандартных библиотек. В нестандартных библиотеках бывают способы решения проблем с функциями для односвязных списков в обзор не вошедшие. К примеру, ручная CPS-трансформация в Fsharpx.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, D. Mon, Вы писали:
DM>Окамлистам списки разумного размера нужны, они их используют (и я среди них). И все работает.
Как я и сказал. Не нужны — только в этом треде, в котором "разумный размер списка стремится к нулю".
DM>А неразумное применение списков и хаскеллистам не нужно: DM>
иначе я бы и для 10к элементов не стал бы его использовать
Мировой аттракцион — фантастическое редактирование.
Реальное мнение Булата о "разумном размере" противоположно вашему и совпадает с моим:
я ведь ясно написал, что список, хоть и может содержать миллионы элементов, не использует операции, которые медленней чем на массивах — иначе я бы и для 10к элементов не стал бы его использовать. ограничение в 100к элементов, после которого ты считаешь неверным использовать списки — связано именно с проблемами окамловского рантайма, а не тем, что именно до этой границы можно терпеть O(n^2) алгоритмы
DM>сколько можно.
Можно сколько угодно, а имеет смысл до тех пор, пока реакция есть.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>В мейнстриме, вообще-то, не программист выбирает язык и протащить в продакшн извращения может и не просто, но примерно в 1024 раза легче, чем более нормальный язык. Не знаю, как дела с явой обстоят, но в коде на С# и C++ такие извращения встречаются.
В С++ и не такие извращения встречаются http://www.intelib.org/intro.html
FR>>получаем один большой функтор.
K>Upwards funarg problem в общем случае так не решить.
В данном случае решают.
FR>>Нет, ты как минимум забываешь замыкания, это уже семантика.
K>Замыкания в яве есть, семантика, в принципе, на окамл похожа.
Угу в чистом си тоже есть и объекты и замыкания в принципе, семантика тоже очень похожа.
Здравствуйте, Klapaucius, Вы писали:
K>Мировой аттракцион — фантастическое редактирование. K>Реальное мнение Булата о "разумном размере" противоположно вашему и совпадает с моим:
Нет там противоположности. Он говорит, что не стал бы использовать длинные списки для операций, "которые медленнее чем на массивах". О том же и я говорю.