Вышел новый стандарт Haskell

>> Даун, просветись - у СТО нет ни одно прямого доказательства.

Ацюковского начитался что-ли? Т.е. найти 3-4 эксперимента в которых СТО типа не подтверждается ты смог, а вот найти сотни тысяч экспериментов, в которых СТО подтверждается с точность до 8-9 знака после запятой сил не хватило, так?

Это ведь все очень важно при обсуждении хаскеля?

А разве тут его обсуждают?

зачем сам язык, когда можно и хаскелистов пообсуждать ;)

>> Это ведь все очень важно при обсуждении хаскеля?

Как правильно сказал archimag, в темах про Хаскель обсуждают все что угодно, но только не subj. Во всяком случае так обычно бывает на ЛОРе )))

Господа, давайте еще поднимем тему артиллерии при Бонапарте... Ее тут очень не зватает :)

СТО - все там нормально выводится из постулатов (А какие там постулаты? Изотропия пространства и времени (пр-п относительности), постоянство скорости света, все.), и хорошо подтверждено экспериментально. Вся мало-мальски конструктивная критика ныне крутится вокруг принципа локальной эквивалентности и (не-?)равенства инертной и гравитационной масс. Но это уже ОТО.

> в темах про Хаскель обсуждают все что угодно, но только не subj

Зато в любой другой теме про программирование обычно начинают вспоминать Хаскелл. :)

> Изотропия пространства и времени (пр-п относительности), постоянство скорости света, все.),

Более того товарищ С.Н. Манида и без постулирования постоянства скорости света выводил.

> СТО - все там нормально выводится из постулатов (А какие там постулаты? Изотропия пространства и времени (пр-п относительности), постоянство скорости света, все.), и хорошо подтверждено экспериментально.

Думаешь, он тебе поверит? Он в газете «Жизнь» прочитал, что это не так.

Если вам действительно интересны высокоэффективные структуры данных в Haskell на практике, почитайте блог Дональда Стюарта (http://donsbot.wordpress.com) или почитайте про stream fusion.

Ну а если вам нужно просто ещё раз что-то доказать себе, то уж извините.

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

>Дело ведь не в том, что императивные структуры эффективнее, это и так понятно.

Как только вступает в дело многозадачность начинается оопс.

> Как только вступает в дело многозадачность начинается оопс.

Ну и что, та же STM тоже императивна по сути, просто возможность безопасно перезапускать транзакции обеспечивается системой типов.

Кстати, где-то видел бенчмарки, там STM была заметно эффективнее обычных блокировок на > 2 процессорах с большим кол-вом потоков.

>Кстати, где-то видел бенчмарки, там STM была заметно эффективнее обычных блокировок на > 2 процессорах с большим кол-вом потоков.

Блокировки нужны чтобы обеспечивать доступ к мутабельным структурам - чтобы исключить рейс кондишенс. В иммутабельных структурах рейскондишенс исключены семантикой. Никаких блокировок не нужно.

> Блокировки нужны чтобы обеспечивать доступ к мутабельным структурам - чтобы исключить рейс кондишенс. В иммутабельных структурах рейскондишенс исключены семантикой. Никаких блокировок не нужно.

afaiu, ничто не мешает в ходе транзакции «мутировать» структуру (т.е. писать лог мутаций), а потом при её выполнении мутировать по-настоящему.

И да, от мутабельных «штук» полностью не избавиться (пока). Например, те же std{in,out,err}. С другой стороны, ещё есть CSP, но я неё знаю плохо.

Близкий аналог классу хаскеля classus vulgaris из быдлоязыков (типа C++/C#/Pascal/Java/etc)

Ну если у вас ничего кроме быдло кода не получается писать на С++/Java может вы только может писать быдло код на них, у других людей получается нормально. И еще а можно в студию не быдло языки.

> В иммутабельных структурах рейскондишенс исключены семантикой. Никаких блокировок не нужно

бугага!

берем опять тот самый пример с обходом директорий с симлинками — на функциональных структурах данных (типа хэша) гонки *фактически* присутствуют — как уже описанная мной ситуация «одна нить заходит в директорию, другая тоже через симлинк»

чтобы убрать гонки, придется переписывать программу

вот тут то быдлокодер на быдлоимперативном ООП-быдлоязыке и будет в вигрыше — ему достаточно заменить std::set на syncronized::set (а если такого готового нет, то сделать обертку над обынчым-- не приходя в сознание добавить aquire_lock release_lock на обоих его методах)

> Ну а если вам нужно просто ещё раз что-то доказать себе, то уж извините.

«можно написать и даже работать будет не особо медленнее (но скромно умолчим, что памяти жрать будет в 10 раз больше)» — это не интересно

вот чуть выше пример минимальности изменений кода при при переходе на многопоточный вариант на быдлоязыке; а что потребуется в хаскеле? (количество копирований/вставок/добавления/удаления кода?)

З.Ы. Beautiful concurrency стоит прочесть

> Если симлинк смотрит ниже корня, то ходить по нему не надо, а если вне корня, то результат обхода непредсказуем, ведь можно так всю файловую систему обойти, включая виртуальные файловые системы, а зачем?

после того, как не получилось написать это на хаскеле, пошли отмазки, что это «не нужно»

> Сторонники хаскеля заявят что обход дерева с сисмлинками не требует меморайзеного списка обойденных узлов. Достаточно проверять находится ли таржет симлинка под уровнем входа - и если так - не входить (в него войдут черезвхот).

Над *каким* из уровней входа? Ведь по симлинку мы можем пройти в рядом лежащее дерево, из него — еще в рядом лежащее (и все они НЕ под самой первой точкой входа).

> Учитывая что императивные неленивые коллекции на всех операциях типа filter/map порождают новую коллекцию

С чего вдруг? Может в яве это и так (кстати почему?), но в плюсах можно по-другому.

> Ещё им сильно кажется, что если таковой понадобится, то при правильном подборе размеров дерева (:с лёгкой подачи оппонёнтов превратившегося в произвольный граф:), обеспечить O(1) структуру для него не удастся даже с деструктивными апдейтами.

а вот отсюда поподробней!!

замечу, что в произвольный граф оно не правратилось — как минимум этот граф частично упорядочен и имеет известный максимальный элемент; возможно у него есть еще св-ва, сходу не скажу.

> Ну и что, та же STM тоже императивна по сути, просто возможность безопасно перезапускать транзакции обеспечивается системой типов.

В хаскеле достаточно приличная система типов, но ФП это отношения мало имеет.

Я люблю С++! После чего-нить вроде

std::sort<vector<A>::iterator>(b.begin(), b.end(), (&_1->*&A::x < &_2->*&A::x && bind(pStrCmp, &_1->*&A::y, &_2->*&A::y) == 0) || (&_1->*&A::x >= &_2->*&A::x && bind(pStrCmp, &_1->*&A::y, &_2->*&A::y) != 0) ); 

Я люблю C#! После чего-нить вроде

FuncX<FuncX<int, int>, FuncX<int, bool>> f = Up<int, int, bool>(delegate(int x)
{
    return x > 0;
});

>му достаточно заменить std::set на syncronized::set

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

на функциональных структурах данных (типа хэша) гонки *фактически* присутствуют — как уже описанная мной ситуация «одна нить заходит в директорию, другая тоже через симлинк»

Это проблемы алгоритма, а не структур.

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

Если они _не_ под самой точкой входа - значит нет _никаких_ проблем с повторным обходом. Если они _над_ точкой входа - значит following link + добавляем его в точки входя для последующих шагов рекурсии. Итого - хранить надо _малое_ количество элементов - только точки входа. Остальная иерархия прошита в путях обходимых каталогов.

То есть множество обойденных каталогово заменено на множество описанное характеристической функцией «являюсь ли я чайлдом или обойденным чайлдом».

>С чего вдруг?

С того что описанный тобой быдлокодер привыкший брать std::set все элементы >5 из этого сета описывает как
....
std::set * result = new std::set()
for(...) if (elem > 5) result->insert(elem)
return result;
....

и по другому не умеет.

но в плюсах можно по-другому.

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

>> на функциональных структурах данных (типа хэша) гонки *фактически* присутствуют — как уже описанная мной ситуация «одна нить заходит в директорию, другая тоже через симлинк»

Это проблемы алгоритма, а не структур.

что, правда?

а почему тогда эти проблемы внезапно решаются заменой структуры данных std::set на syncronized::set?

> То есть множество обойденных каталогово заменено на множество описанное характеристической функцией «являюсь ли я чайлдом или обойденным чайлдом».

т.е. быдлокодер распараллелит свою функцию заменой одного слова std:: на syncronized::, а хаскелист вынужден изобретать новый алгоритм... да... явный прогресс...

кстати, ты бы не мог выписать свой алгоритм хотя бы словесным псевдокодом?

хинт: симлинк может указывать еще и ВЫШЕ первой точки входа, этот случай тоже надо обработать.

> Я люблю С++! После чего-нить вроде ... и хаскель не таким корявым кажется :)

то что хаскель че-то делает лучше — не оправдание неспособности хаскеля эффективно и удобно решать простейшие задачи

>Дело ведь не в том, что императивные структуры эффективнее,

с какой стати? в простейших случаях, возможно, но в реальной программе...

>т.е. быдлокодер распараллелит свою функцию заменой одного слова std:: на syncronized::

и получит дедлок.

> и получит дедлок.

а вот отсюда поподробнее

>а почему тогда эти проблемы внезапно решаются заменой структуры данных std::set на syncronized::set?

В какой фантастической вселенной?

и получит дедлок.

дедлок он не получит, но тот код, который я раньше нарисовал, действительно чуть переделать надо, чтобы он был пригоден для обоих случаев, вот так:

std::set<int> visited_inodes; 
 
... 
 
int i=inode(dir); 
 
if( ! visited_inodes.insert(i).second ) return;

>т.е. быдлокодер распараллелит свою функцию

Фантастика. Ты пробовал делать то что говоришь?

Код внешний по отношению к синхронной структуре вызывающий методы (даже если они синхронны по отношению к состоянию структуры) - несинхронны по отношению друг к другу. А если их засинхронизировать на тот же лок - не будет никакого параллелизма.

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

хинт: симлинк может указывать еще и ВЫШЕ первой точки входа, этот случай тоже надо обработать.

Там же выше описано.

Надо запоминать:
- первую точку входа.
- точки входа вне иерархии запомненых точех входа (переход вверх, переход в другое поддерево (есть вероятность что это не требуется если интерпретировать симлинк как каталог если он ведет вне дерева точки входа - надо подумать)).

Не надо входить:
- в запомненые точки входа
- в симлинки которые ведут в иерархию под точками входа.

> А если их засинхронизировать на тот же лок - не будет никакого параллелизма.

Будет, хотя и ограниченный.

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

> Не надо входить: - в запомненые точки входа

ну так опять имеем *коллекцию* и гонки — две нити могут одновременно добавить одну точку входа и войти в нее, и немутабельные структуры бессильны :-)

>Будет, хотя и ограниченный.

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

добавляет директорию, отпускает лок.

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

>а вот отсюда поподробней

Я имел в виду, что в интересующих нас диапазонах значений N,(не очень малы, но и вполне конечны), O(1) поиска вообще не бывает. Вспомним об отношениях скоростей кешей, локальной памяти, не-локальной в *NUMA. Они гораздо менее «красивы». Т.е. результат-то будет O(константа), но эта константа будет разная при разных N, что больше похоже на (например)экспоненту, нарисованую ступеньками. Соответственно, не факт, что на фоне этой константы при N достаточном для выгрузки в медленную память, будет заметно влияние недостаточно эффективных ф-ных структур. Скажем, те же 64 (где-то проскакивало) по сравнению с 300 для памяти, как-то не интересно обсуждать.

>в произвольный граф оно не правратилось

В прошлой постановке задачи она уже добралась до приведённой в учебниках по хаскелю, т.ч. писать уже ничего не нужно (разве что в IO его запихать).

«можно написать и даже работать будет не особо медленнее (но скромно умолчим, что памяти жрать будет в 10 раз больше)» — это не интересно

вот чуть выше пример минимальности изменений кода при при переходе на многопоточный вариант на быдлоязыке; а что потребуется в хаскеле? (количество копирований/вставок/добавления/удаления кода?)

З.Ы. Beautiful concurrency стоит прочесть

Ну а что сложного? Во-первых, нужно с самого начала прикрутить монаду Reader (чтобы параметризировать обход директории по регуляркам, или что сами придумаете). То есть у нас будет тип данных Environment для хранения всего этого добра, и

newtype DirTraverserT m a = DT (ReaderT Environment m a)

type DirTraverser = DirTraverserT IO

Для хранения найденных файлов можно прикрутить монаду Writer, но у нас всё равно будут «грязные» вычисления, так что можно в Environment засунуть IORef. В качестве структуры для хранения найденных файлов лучше использовать Data.Sequence.Seq или Data.DList.DList.

Затем, если вам надо многопоточность (вот только зачем? :-), то просто заменяем IORef на TVar, и в функции, проходящей по директории, меняем «asks files >>= liftIO . readIORef» на какую-то транзакцию, ну и думаем, сколько будет потоков и куда их запускать. Мне представляется, что каждый поток получает порцию директорий, проходит по ним и пишет в TVar результаты. Никаких блокировок. Правда, с симвользым ссылками сложнее, но опять же, всё можно запихнуть в Environment (настройки — чистые, результаты — транзакционные переменные).

> ну так опять имеем *коллекцию* и гонки — две нити могут одновременно добавить одну точку входа и войти в нее

Если по-хорошему, то не могут. В Concurrent Haskell в STM есть две отличительные особенности: retry и orElse (которые, кстати, формируют моноид под монадой). Если вы ещё не прочитали об этом, то очень советую. Бумажка называется «composable memory transactions», afair.

Так что здесь при попытке добавления новой точки входа поток должен сначала попытаться найти эту точку. Если не нашёл, но добавить и идти собирать урожай. Если нашёл, то ждать, пока кто-то её не уберёт.

Хотя здесь ещё надо как следует подумать, что и как надо хранить. Но в любом случае, гонок и дедлоков уже можно не бояться.

Это все очень интересно. Да вот одна неувязкочка: без СТО и ОТО не было бы GPS, т.к. там нужна очень высокая точность времени, и надо вводить поправки на СТО (скорость спутника) и ОТО (гравитация на Земле больше чем на уровне спутника, и время идет быстрее). Т.е. доказательство прямейшее.

Любителям мысленных экспериментов: Угадайте что обнаружит брат близнец прилетевший обратно на землю? Он обнаружит что его близнец оставшийся на земле состарился, а что обнаружит оставшийся брат близнец (он тоже наблюдатель и относительно себя он неподвижен а относительно брата близнеца - улетал от него) он обнаружит что состарился прилетевший брат близнец - что напрямую противоречит не релятивисткой (хорошо проверенной в отличие от СТО экспериментально) физике. Привет пиар евреям.

Дядь, а ты хоть отличаешь инерциальные СО от неинерциальных? Есть некоторые сомнения в том, что ты вообще СТО знаешь.

По теме: можно качать@сидить.

Или тут.