Haskell vs Lisp

>> Да не zip, а зиппер. Вот тебе для списков, для деревьев сделаешь сам:

Это ничем не отличается от вставки элемента в голову списка типа x:xs. Естественно вставка влево-вправо это O(1), а если мне надо вставить не на соседнюю поицию, а через несколько? Рекурсивно применять toRight/toLeft? И где тут O(1)? Тут скорее O(n)где n-число позиций между текущей и той куда надо вставить. Прежде чем вставить элемент, мне надо сначала добраться до нужной позиции путем последовательного прохода по спику, так?. Другого способа добраться до нужной мне позиции нет.

>> Вспоминай человеческий язык.

Это был пример той самой многозначности :))

> Прежде чем вставить элемент, мне надо сначала добраться до нужной позиции путем последовательного прохода по спику, так?

А зачем тебе вставлять элемент в позицию, которой ты в глаза не видел?

Список (вар.: дерево) - это корневой каталог и абсолютные пути; зиппер - это текущий каталог, команда cd, и относительные пути.

s/влево-вправо/в текушую позицию/

>> А зачем тебе вставлять элемент в позицию, которой ты в глаза не видел?

Ну приехали...

У меня есть список [1 2 3 4 5 6], мне надо 6 поменять на 10, текущая позиция на двойке, и как мне это сделать без 4-х кратного применения toRight?

>> это корневой каталог и абсолютные пути; зиппер - это текущий каталог, команда cd, и относительные пути

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

> У меня есть список [1 2 3 4 5 6], мне надо 6 поменять на 10, текущая позиция на двойке, и как мне это сделать без 4-х кратного применения toRight?

Ещё раз: это тебе святой дух нашептал, что надо именно 6-ю позицию поменять?

> cd может перебросить меня в любую каталог файловой системы за одну комманду, а Zipper не может передвинуть меня дальше одной позиции за раз.

Ну, блин, приехали.

multipleRight :: Integer -> Zipper a -> Zipper a

multipleRight 0 = id

multipleRight n = multipleRight (n-1) . toRight

>> Ещё раз: это тебе святой дух нашептал, что надо именно 6-ю позицию
 поменять?

Miguel хватит тупить а?  Мне надо получить доступ к  i-му элементу 
массива за O(1), что тут непонятно? Или тебе трудно представить задачу 
где это необходимо? 

>> multipleRight n = multipleRight (n-1) . toRight

Пацтулом. и ты мне хочешь сказать, что это O(1)? 
Ну давай посмотрим, что будет при n=3, раз ты сам не можешь.

multipleRight 3
multipleRight 2 . toRight
multipleRight 1 . toRight . toRight
toRight . toRight . toRight

Итого имеем три отложенных вызова toRight  и 3 рекурсивных вызова 
miltipleRight, т.е. сложность алгоритма по использованной памяти O(n),
 по времени тоже O(n).

Нельзя реализовать доступ к массиву за О(1) операцями типа x:xs и 
подобными, неужели это не понятно?

>и как мне это сделать без 4-х кратного применения toRight?

Да никак! Это же список! Если тебе критичен доступ к _произвольному_ элементу со сложностью O(1) используй массив.

> Пацтулом. и ты мне хочешь сказать, что это O(1)?

Дурень, ты хочешь сказать, что cd работает за O(1) от длины пути?

> Нельзя реализовать доступ к массиву за О(1) операцями типа x:xs и подобными, неужели это не понятно?

Да мне-то понятно, но неужели ты думаешь, что операциями типа car и cdr это возможно?

> Тогда так и говори: не "все функции", а "все функции стандартной библиотеки". А вот в хаскеле - именно ВСЕ.

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

Позиция тебе может быть известна и предварительно. Когда создавал дерево ты позицию запомнил, а потом в процессе дальнейших вычислений выяснилось, что какое-то значение в этой позиции надо поменять.

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

>> Да никак! Это же список! Если тебе критичен доступ к _произвольному_ элементу со сложностью O(1) используй массив.

Замечтально... Теперь покажи мне это в Хаскеле. И что-то мне подсказывает, что сделано это далеко не в чисто функциональном стиле, ага. Через unsafeWrite со всеми вытекающими.

Я бы даже пример поправил. Имеется список [1 2 3 4 5 6 ... 100]. В данном списке заранее известны определенные элементы, которые попадают в группу "риска" и в дальнейшем могут поменяться. Ну например, 2,6,40,55,70,78 ... и т.д. По ходу вычислений выяснилось что необходимо поменять значения элементам 2,40,78, ... Тот зипер, который ты описал ( как я его понял) за 0(1) эту задачу решить не позволит. Первый элемент мы допустим поменяем за 0(1), а до других надо будет добираться через toLeft и toRight. Следовательно надо прудумывать какую-то другую структуру данных

>> Да мне-то понятно, но неужели ты думаешь, что операциями типа car и cdr это возможно?

Нет, для этого есть vector-set!

> А зачем тогда ФП язык использовать?

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

Лично я за идею о языке - комбайне который включает в себя и ФП и ООП и СП и т.д. При этом скорее всего потеряется столь любимая хаскелистами ленивость... ну и фиг с ней с другой стороны.

> Лично я за идею о языке - комбайне который включает в себя и ФП и ООП и СП и т.д. При этом скорее всего потеряется столь любимая хаскелистами ленивость... ну и фиг с ней с другой стороны.

Написал бы проще: "Лично я - за OCaml".

>> Дурень, ты хочешь сказать, что cd работает за O(1) от длины пути?

Если по каталогам построить индекс то таки да.

>Теперь покажи мне это в Хаскеле

Data.Array (IArray, MArray), Data.ByteString

>И что-то мне подсказывает, что сделано это далеко не в чисто функциональном стиле, ага.

Тебе шашечки или ехать? Ну да, произвольный тип в Array ты запихивать не сможешь. Только указатель. Да, там есть различные unsafe* функции, которые выполняются быстрее. Да с массивами сложно работать. Да IO вносит свой оверхед.

MArray монадический, это "чистый функциональный стиль"?

А где-ты видел массивы, сделанные в чисто функциональном стиле? Лисп, Схема, OCaml, на чистые ФП языки не тянут.

> А где-ты видел массивы, сделанные в чисто функциональном стиле? Лисп, Схема, OCaml, на чистые ФП языки не тянут.

Звучит как "Девчонки, а вам когда-нибудь яйца дверью прищемляли?" Мне пофигу, в каком оно стиле, мне надо чтобы удобно и эффективно.

>> Data.Array (IArray, MArray), Data.ByteString

Вот о них я и писал.

>> Тебе шашечки или ехать? Ну да, произвольный тип в Array ты запихивать не сможешь. Только указатель. Да, там есть различные unsafe* функции, которые выполняются быстрее. Да с массивами сложно работать. Да IO вносит свой оверхед.

Вот и нафига это надо если есть куда более простые способы?

>> А где-ты видел массивы, сделанные в чисто функциональном стиле? Лисп, Схема, OCaml, на чистые ФП языки не тянут.

Нигде. Потому что чистый ФЯ - это абсурд.

>> MArray монадический, это "чистый функциональный стиль"?

Кстати мне всегда было интересно вот что: если монада (тот же MArray) реализована исключительно на Хаскеле функциями, часть из которых не имеет функциональной чистоты (unsafeWrite, unsafeRead), то почему этот язык называется "чистым функциональным языком"?

>Мне пофигу, в каком оно стиле, мне надо чтобы удобно и эффективно.

Дык юзай списки, удобно и эффективно. А массивы в _общем_ случае это не удобно. То что называется массивами в С не есть массивы, а есть обычная арифметика с указателями. В C++ работа с массивами организована ИМХО лучше всех, правда STL тоже критерию "удобно" не соответствует.

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

???

И что он с ними будет делать?

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

Да ёклмн, не проблема это. Список точно также можно взять не за одну позицию, а за две или сколько надо. Структура станет не сильно сложнее.

>Вот и нафига это надо если есть куда более простые способы?

Дык тебя насильно заставляют? Опять же ты столкнулся с задачей когда списки работали неэффективно? Или ты просто теоретизируешь?

>Потому что чистый ФЯ - это абсурд.

Ну, ну. Изучать его сложно, а затем видны реальные выгоды такого подхода.

>часть из которых не имеет функциональной чистоты (unsafeWrite, unsafeRead), то почему этот язык называется "чистым функциональным языком"?

Еще про функцию trace забыл. А сколько "грязных хаков" в любой операционке? Или даже в более-менее сложной программе? Если ты используешь unsafe* функции, так это лично твои проблемы. Опять же никто с тебя не требует их использовать, но "срезать угол" возможно.

MArray это не монада, это Mutable Array. Для разрешения заморочек c "внешним миром" используется IO.

Да там нечего особо придумывать. Каждому элементу даём не только следующий за ним (как в обычном списке), но и следующий "рискованный". Ну и оборачиваем это дело зиппером. Проблемы нет.

Кстати: со СПИСКОМ ни один язык не будет работать за O(1). Вообще. Нужно O(1) - юзайте массив.

И он, конечно, тебе в списке сделает что надо за O(1).

А без если?

> Да там нечего особо придумывать. Каждому элементу даём не только следующий за ним (как в обычном списке), но и следующий "рискованный".

Все равно получаем, что все надо обойти "рискованные" элементы от текущего подлежащего замене, до следующего и т.д. Если в группе риска элементов много, а на деле меняются единицы, то получаем сложность O(M),где M - размер группы риска, а хотелось бы O(L), где L - количество меняющихся на самом деле элементов.

> Кстати: со СПИСКОМ ни один язык не будет работать за O(1). Вообще. Нужно O(1) - юзайте массив.

Смотря что делать. Если надо удалить L заранее выбранных элементов списка то можно за O(L), т.е. для одного элемента будет сложность O(1)

Data.Array.ST

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

Если хочется чистого ФП:

Data.Sequence

update :: Int -> a -> Seq a -> Seq a

O(log(min(i,n-i))). Replace the element at the specified position

> ??? > И что он с ними будет делать?

Всмысле "что". Будет передавать эту информацию программисту-функциональщику, который любит чтобы в функциях не было сайд-эфектов. Типа: в этих функциях возможны сайд-эфекты, будь осторожен, а в этих все чисто. При наличии Lisp-овского REPL-а такой функционал будет достаточно легко интегрировать в среду разработки. Более того скорее всего нормальные трансляторы такой анализ функций выполняют при оптимизации, для вычисления инвариантных фрагментов в циклических конструкциях

> Если надо удалить L заранее выбранных элементов списка то можно за O(L)

Если есть заранее выбранные элементы, можно и на Хаскеле сделать за O(L).

> Будет передавать эту информацию программисту-функциональщику, который любит чтобы в функциях не было сайд-эфектов.

А фигли тогда не следить за чистотой самому?

> Если есть заранее выбранные элементы, можно и на Хаскеле сделать за O(L).

Расскажи, действительно любопытно. Для общего развития

> А фигли тогда не следить за чистотой самому?

Во первых, не всё ты пишешь сам, а во вторых ингода сайд-эфекты удобны.

>> А фигли тогда не следить за чистотой самому?

> Во первых, не всё ты пишешь сам,

Я имел в виду транслятор. Почему бы ему самому не следить за чистотой и не давать ерроры вместо "информации для программиста"?

> Расскажи, действительно любопытно.

Дык уже рассказал. Дополнительно к следующему элементу указывать на следующий выбранный.

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

Чето не могу представить как это в коде будет. Покажи. Схематично хотябы

>> Еще про функцию trace забыл. А сколько "грязных хаков" в любой операционке? Или даже в более-менее сложной программе? Если ты используешь unsafe* функции, так это лично твои проблемы. Опять же никто с тебя не требует их использовать, но "срезать угол" возможно.

При чем здесь грязные хаки в операционках? При чем здесь личные проблемы? Речь идет о производительности алгоритмов, да и грязные хаки, как ты выразился - понятие относительное. С точки зрения ФП qsort выполненный на С - грязный хак, и что? Объясни мне теперь, что код на хаскеле работающий в разы медленнее сишного варианта, но зато дико красивый, лучше чем грязный хак на С.

>> Ну, ну. Изучать его сложно, а затем видны реальные выгоды такого подхода.

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

>> Дык тебя насильно заставляют? Опять же ты столкнулся с задачей когда списки работали неэффективно? Или ты просто теоретизируешь?

Меня насильно никто не заставляет, поэтому хаскелем я не пользуюсь ;)

>> Data.Array.ST ... и далее по тексту...

Я промолчу, что само это написано, как тут было сказано, "грязными хаками", на чистом как слеза функциональном языке. Ну-ну

>> Если хочется чистого ФП: Data.Sequence update :: Int -> a -> Seq a -> Seq a O(log(min(i,n-i))). Replace the element at the specified position

Мне надо O(1), нафиг мне Data.Sequence который это не умеет?

>> Дык юзай списки, удобно и эффективно.

Дык уже ж показали ни эффективно

>Речь идет о производительности алгоритмов

Еще раз спрашиваю, ты реально уперся в ограничения хаскеля или просто теоретизируешь?

>Выгода там одна - уровень абстракции, которая убивается напрочь эффективностью полученных программ.

>Объясни мне теперь, что код на хаскеле работающий в разы медленнее сишного варианта, но зато дико красивый, лучше чем грязный хак на С.

>Выгода там одна - уровень абстракции, которая убивается напрочь эффективностью полученных программ.

Вот ты и сам ответил чем лучше.

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

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

>Дык уже ж показали ни эффективно

Код на С зато небезопасен. Если ты сможешь программу на 100000 строк на С вылизать да такого уровня до какого вылизан sort в С, то такой код тебе на вес золота обойдется учитывая трудозатраты. А так все время будешь за пределы массивов выходить и по невалидным указателям обращатся. Так что нафиг такую эффективность.

>> Еще раз спрашиваю, ты реально уперся в ограничения хаскеля или просто теоретизируешь?

Ну если это можно назвать "реально", то да - сравнивал qsort на Хаскеле, которым весь инет забит с сишным вариантом. Чтобы засечь разницу в скорости не понадобилась даже секундная стрелка на часах :))

>> А что ты хотел? На ежа сесть и не уколоться?

Нет, просто меня нервирует тот факт, что haskell fanboys пытаются им все дыры заткнуть.

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

Прям шаолинь какой-то :)) Это не экзамен - это психологическая потребность спросить у других "зря ли я потратил год?". Ну и вопрос про цену, на самом деле больше тебя волнует чем меня :)

>Ну если это можно назвать "реально", то да - сравнивал qsort на Хаскеле, которым весь инет забит с сишным вариантом. Чтобы засечь разницу в скорости не понадобилась даже секундная стрелка на часах :))

Ага я тоже сравнивал random 1000000 Int из файла - mergesort из Data.List.sort 5.5 s, qsort на MArray 1.0 s, C - 0.38 s

Зато если тебе не нужны все данные, а например только некоторые вначале то картина будет совсем другая, а если тебе нужны все, то зачем тогда ленивость? Ты жертвуешь тут зато можешь получить глобальное преимущество за счет ленивости, опять же это будет заметно только в большой нетривиальной задаче.

>Нет, просто меня нервирует тот факт, что haskell fanboys пытаются им все дыры заткнуть.

Фанатегов нужно игнорировать, нервные клетки не восстанавливаются.

>то да - сравнивал qsort на Хаскеле, которым весь инет забит с сишным вариантом.

И больше ничего? Значит теоретизируешь. Попробуй на хаскеле сделать парсер какого-нибудь текстового файла, а еще лучше XML'а с помощью HXT. Сразу возникнет ощущение, что чего-то важное в жизни ты пропустил.

>Прям шаолинь какой-то

А ты как думал. Потребности спросить, потратил ли я год зря не возникает: ФП позволяет взглянуть на обычные проблемы под другим углом. А самая главная проблема в изучении хаскеля - недостаток математических знаний. А другая проблема в том, что годами наработанные "императивные" идиомы, либо вообще не работают, либо очень вредят.

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

...а память нынче дешёвая.

> Попробуй на хаскеле сделать парсер какого-нибудь текстового файла, а еще лучше XML'а с помощью HXT. Сразу возникнет ощущение, что чего-то важное в жизни ты пропустил.

Уж лучше на OCaml сделаю, лол.

Да и вот еще - попробуй так, у меня вышло заметно быстрее

part [] = ([],[],[])
part (x:xs) = partition' xs [] [x] []

partition' [] less eq more = (less, eq, more)
partition' (x:xs) less eq@(p:_) more = case compare x p of
                                            LT -> partition' xs (x:less) eq more
                                            EQ -> partition' xs less (eq++[x]) more
                                            GT -> partition' xs less eq (x:more)

qsort [] = []
qsort x = qsort less ++ eq ++ qsort more 
  where
  (less, eq, more) = part x