Здравствуйте, m e, Вы писали:
ME>тогда можно было бы сказать "этот код работает в О(N)", а иначе нет, нельзя
Я и не утверждал, что он работает за O(n). Я написал, что если скорость не порадует, можно написать правило перезаписи, причём дал ссылку на описание техники, откуда ясно видно, что речь идёт о GHC.
ME>а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)
Если это случится, то причиной может быть одно из двух:
1. Мы получили ИИ который способен взять неэффективный алгоритм и подобрать аналогичный эффективный.
2. Мы имеем место с задачей специально подобранной под оптимизацию. А это уже банальное мошенничество, так как на любой другой задаче чуда не случится.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VoidEx, Вы писали:
VE>Я же даже ссылку давал. Rewrite rules. Вкратце, компилятор умеет заменять map f . map g на map (f . g), ему можно написать хинты разного рода. В том числе, если приспичило, map maximum . tails на mysuperpuperfastfunction. В частности, есть библиотека stream-fusion, где map f . map g . filter p . map h сворачивается до одного цикла.
В один компилятор встроили средства добавления оптимизаций, так что теперь пользователи этого компилятора могут добавлять свои оптимизации. Все это очень здорово.
Но причем тут задача? Как она от этого свернется до одного цикла? Давай ты приведешь код который получится в конечном итоге (будет исполняться). Далее объясни как "подзапрос" был заменен на накопительный параметр или переменную (потому как без них задача эффективно не решается). Короче, куда девается вычисление суммирования подсписков?
VD>>А зачем тут этот zip? И зачем тут tails? У задачи есть прямое и простой решение — свертка или цикл (что одно и тоже по сути).
VE>Я же достаточно понятно написал.
Давай спорить с очевидны. Если бы написал понятно и был бы прав, то вопрос не обсуждался бы.
VE>Слияние списка и максимумов хвостов. Слияние — zip. У нас же не тупл списков, а список туплов. Хвосты — tails. Прочти исходный текст-то. Там только "хвосты" сформулированы "от текущего элемента до конца", что суть одно и то же. VE>
VE> zip . (id &&& map maximum . tails)
VE>слияние самого [списка] и максимумов хвостов
VE>
VE>Если убрать zip, получится тупл двух списков. Если убрать id &&&, получатся только максимумы хвостов.
Да зачем ты мне переводишь значения функций? Ты бы лучше это в самом начале сделал, чтобы не лазить по справочникам.
Я тебе говорю, что и zip, и tails, и maximum тут лишние. Ты зачем-то подсчитываешь количество элементов в подписках. Это приводит к тому, что нужно выделить подсписков столько сколько есть элементов, а потом их все просуммировать (а значит материализовать).
Эффектвный же алгоритм требует одного прохода по списку (но в обратном направлении) и накопления значения в переменной или параметре.
И я решительно не понимаю, как неэффективный алгоритм может в одночасье превратиться в эффективный.
VD>>Я считаю, что понятный, прямо подходяций и наиболее быстрый путь — это самый правильный путь.
VE>Это определение неформализуемо и прямо зависит от понимающего.
Это демагогия. Что не формализованного в понятии самый быстрый? А если есть самый быстрый алгоритм, то его прямая запись тоже становится вполне однозначным понятием.
VE>Кому-то и цикл с мутабельными переменными понятнее.
И цикл понятнее чем набор упражнений по трансфорации функций:
def data = [1,2,3,2,1];
mutable max = 0;
mutable res = [];
foreach (x in data.Reverse())
{
max = Math.Max(x, max);
res ::= (x, max);
}
Ну, а проблема длинны стоит только для маньяков. Все остальные просто вынесут код в отдельную функцию и получат в основном коде максимальную краткость и понятность.
На изучение этого "ужасного императивного кода" уйдет значительно меньше времени чем на разбор хардкорных упражнений по склеиванию функций.
VE>Автор просил не "простой и понятный" в понимании кого-то из участников, а "матан"
автор имел в виду реализацию того же самого без цикла.
VE>что я воспринял как "более высокоуровневые комбинаторы".
Каждый воспринимает все в меру своей испорченности (с)
VE>О результате судить ему, а не тебе.
Дык он уже вроде как высказался. Ты просто его проигнорировал или не заметил. В прочем, можно послушать и прямой ответ.
VE> Свёртка менее высокоуровнева, чем tails, ибо это вообще базовый комбинатор, который использовать напрямую не рекомендуется. Именно по причине непонятности.
Глупость какая-то. Более выскоуровневый, менеевысокоуровневый. Это чушь. У нас на лицо разные алгоримы и разные методы их реализации.
И ты вместо простого и быстрого решения придумал медленное и сложное. Чем в очередной раз доказал, что хаскель портит восприятие мира .
VE>Свёртка понятна тебе так же, как цикл императивщикам. Им он и правда понятен. Вон все стены они обдолбили, пытаясь понять, чем всякие фолды лучше циклов, им лично циклы понятнее. Но ты же понимаешь, почему так.
Ты сильно отстал от жизни. Они давно использую Линк. А то что им цикл понятнее — это ни разу не их проблема. Лично я тоже переодически предпочитаю цикл и императив, когда он бывает понятнее.
У тебя проблема. Ты ставишь знак равенства между "понятнее" и "короче". Но это не так. Понятнее — проще для восприятия. Чем быстрее можно вникнуть в суть кода, тем он понятнее.
Зачастую ФП понятнее, так как сворачивает кучу действий в одно. Но разницы между фолдом и циклом по сути нет. Фолд и есть абстракция цикла с накоплением результата.
Преимущество ФП-подхода тут только в том, что он предотвращает сваливания в одну кучу разных частей алгоритма, и тем самым способствует структуризации кода. Но, если программист сам способен структурировать код, то разница между фолдом и циклом минимальна.
Комбинаторы же, на мой взгляд, это вообще ФП-шная ересь. Иногда они бывают очень удобны. Но в большинстве случаев они спользуются просто не по делу и затрудняют чтение кода.
VD>>Свертка — это абстракция цикла. Что там включать то? Перебор в обратную сторону с накопителем.
VE>Ты ведь остался в душе императивщиком, раз свёртку понимаешь через цикл.
У меня не было задачи переродиться и признать прошлое ошибочным. Я просто не менялся. Я приобрел новый опыт и использую его там где он удобен.
ФП ни разу не серебряная пуля. И ты прекрасно демонстрируешь оверкил в его использовании, выбирая переусложненные и неэффективные решения (да еще и гордясь этим).
VE> В таком случае цикл тебе и правда понятнее. Непонятно только, зачем тогда свёртка.
Я уже говорил, что свертка особых преимуществ не дает. Некоторое сокращение кода и отсутствие изменяемых переменных. Так что я выбираю то, что кажется удобным по месту. А если нужна эффективность, то выбираю циклы.
В высокоуровневом языке и циклы могут выглядеть вполне прилично.
VE>Свёртка — это не абстракция цикла. Свёртка для Option — это что, цикл что ли? А для Tree? Два цикла? Или что-то другое?
Цикл, цикл. Точнее абстрагирование частного случая. В императивном мире ее заменой являются итераторы. Их тоже по фигу для какой структуры создавать.
VD>>Те ерогливы что написал в первом варианте — это конечно куда лучше. Хрень поймешь через 10 минут, но зато очень круто! Мега-хаскель-вый!
VE>Это называется "парадокс Блаба". Императивный программист пишет императивно даже на Haskell.
Это называется неумение понимать окружающих. Ты возомнил, то только твой взгляд правильный и начинаешь на окружающих ярлыки приклеивать.
В используемом мной языке все необходимые конструкции есть. Как ими пользоваться я прекрасно понимаю и иногда пользуюсь. Разница между нами только в том, что я не испытываю оргазма от этого.
Вместо комбинации функций я предпочитаю объявление локальных функций с внятными именами. Все равно, как бы ты не упражнялся с комбинаторами в реальной жизни постоянно возникают ситуации когда кода слишком много. Держать его по месту — запутывать код.
VD>>Люди! Кто понял исходный вариант без напряжения? А вообще кто-то есть кто понял?
VE>Любой хаскелист поймёт сходу
Я не к тебе обращаюсь. Вот кода тут будет хотя бы несколько ответов, что код поняли без проблем, то поговорим дальше.
VD>>А чтобы прочесть вот этот
На фиг не нужен такой опыт. Это опыт дешифрации.
VE>Несколько лет назад ты бы прекрасно понял только столь же страшный код с циклами на C# (C++).
Я прекрасно понимаю твоей код. Вот только оценка моя другая — это говнокод. Ни чем не лучше чем упржения С++-ников на шаблонах. Из серии есть возможность — надо использовать.
VE>Время, за которое ты понимаешь код, очень субъективный параметр.
Ну, да. Я понимаю долго. Вася Пупкин долго, еще 10 программистов долго. Но у нас тут есть один не признанный гений выдресировавший себя до такой степени, что имеет в уме интепретатор хаскеля. И он нам объясняет как надо писать код.
Запомни простую истину. Код надо писать так, чтобы он был понятен большинству окружающих. Всегда можно найти несколько разных способов написать код. И выбирая более сложный вариант надо четко понимать зачем это делает. Что это дает. Если это дает пол строки кода, но увеличивает сложность восприятия, то нужно отказаться от такого выбора.
VE>>>Не совсем. Например map f . map g . map h обратно не перевести без потерь.
VD>>Да ладно! Что этому мешает?
VE>Что это за закорючки?
Блаб?
VE>Очевидно, потенциальная грязь в f, g и h мешает. Придётся анализировать чистоту.
Очевидно, что это надуманный предлог.
VD>>Оптимизация — это исключительно фича компилятора. Если в одном компиляторе ее сделали, то и в других можно сделать.
VE>В прицнипе и зайчика можно научить курить. Если прикрутить анализатор чистоты, то, возможно, получится.
Когда сказать нечего не стоит нести чушь.
VE>Вообще, спор с тобой я считаю бессмысленным (как и ты спор со мной), мы друг друга ни в чём не переубедим, да и ни к чему, так что давай прекратим?
Уважаемый, ты часом не забыл, что это ты влез в тему и в форум никак не относящийся к хаскелию и развел в ней офтоп?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Аноним, Вы писали:
А>Я прочел хотя никогда и не писад на хаскеле... А>В хаскеле можно сделать ...
А чудесное превращение алгоритмов — это вообще нонсенс. Перестановка функций местами алогоритма не изменим. Если было суммирование подсписков, то оно и останется. Или речь идет об подтасовке которая тупо меняет один конерктный алгоритм на другой. Но это обман, а не оптимизация.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
ME>>а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)
VD>Если это случится, то причиной может быть одно из двух: VD>1. Мы получили ИИ который способен взять неэффективный алгоритм и подобрать аналогичный эффективный. VD>2. Мы имеем место с задачей специально подобранной под оптимизацию. А это уже банальное мошенничество, так как на любой другой задаче чуда не случится.
maximum (tails x) очевидным образом вычисляется в О(N), и вопрос только в том, есть ли г.хаскеле такой rewrite:
maximum (tails x) = scanr1 max x
я предпочитаю на такие вещи не надеяться, и записывать прямо:
Здравствуйте, m e, Вы писали:
ME>maximum (tails x) очевидным образом вычисляется в О(N),
Логично. Вот только он вычисляется для каждого элемента списка.
ME>и вопрос только в том, есть ли г.хаскеле такой rewrite: ME>
maximum (tails x) = scanr1 max x
Что за scanr1? И что все это даст? Чтобы код выполнялся быстро его в цикл нужно переписывать. В один. А это изменение алгоритма.
ME>я предпочитаю на такие вещи не надеяться, и записывать прямо: ME>
solution x = x `zip` map scanr1 max x
И что мы получаем вместо одного цикла?
Короче, возьми свои варианты и прогони на большом объеме данных или много раз. Только так чтобы компилятор не выбросил бессмысленные повторения.
ME>кстати, никто не мешает сделать scanr1 в немерле
В Н вообще любую реализацию с Хаскеля можно переписать, так как это такой же в точности ФЯ. Так что вся эта пенесометрия от глупости.
Вопрос только в том, что у Н свои подходы. ФП в нем не серебрянная пуля, а равноправная парадигма. Когда-то ФП рулит. Когда-то рулит ООП. А когда-то рулит МП.
Причем МП обладает смой большой мощью. С помощью МП можно сделать декларативным все что угодно. Но опять же это не серебряная пуля, так как на решение задач с помощью МП нужно больше сил и большая квалификация.
Вот в Н2 мы в основном будем работать над упрощением применения МП (точнее языкового подхода).
Мы думали и об наворачивании основного языка, но пока что лично я не вижу в этом реальной необходимости. Хаскел и (даже) Скала стремительно уходят в разряд элитных наворотов для тренировки мозга. Мы же ставим другие задачи. Мы хотим создать средсво разработки значительно повышающее производительность труда массового программиста.
Мы не ориентируемся на даунов и быдлокодеров. Но при этом мы хотим сделать технологию доступной для масс.
По сему лично мне смешно когда хаскилисты приходятся мериться пенесами на отдельных строчках кода. Мол у кого короче, тот и прав.
Давайте померим объем кода необходимый, например, для создания парсера современного ЯП. Вот тут Хасель сольет по полной. Его решение будет и длиннее, и не понятнее, и значительно медленнее. При этом производительность труада программиста так же будет сильно не в пользу Хаскеля.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Давай спорить с очевидны.
С тобой спорить, только время терять.
VD>Эффектвный же алгоритм требует одного прохода по списку (но в обратном направлении) и накопления значения в переменной или параметре.
Пущай требует, зачем же его явно писать.
Декларативность подразумевает запись того, что нужно сделать, а не как.
VD>И я решительно не понимаю, как неэффективный алгоритм может в одночасье превратиться в эффективный.
Ну не всем же всё понимать.
VD>>>Я считаю, что понятный, прямо подходяций и наиболее быстрый путь — это самый правильный путь.
VE>>Это определение неформализуемо и прямо зависит от понимающего.
VD>Это демагогия. Что не формализованного в понятии самый быстрый?
Демагогия, это отвечать в ответе на "неформализуемо" вспоминать только "самый быстрый", а не "понятный" и "прямо подходящий".
VD>И цикл понятнее чем набор упражнений по трансфорации функций:
ТС написал, что мой второй вариант понятнее.
VD>На изучение этого "ужасного императивного кода" уйдет значительно меньше времени чем на разбор хардкорных упражнений по склеиванию функций.
У тебя.
VD>Каждый воспринимает все в меру своей испорченности (с)
Именно.
VD>Дык он уже вроде как высказался. Ты просто его проигнорировал или не заметил.
Или ты.
VD>У нас на лицо разные алгоримы и разные методы их реализации.
У нас на лицо одинаковый выход на одинаковый вход.
VD>Чем в очередной раз доказал, что хаскель портит восприятие мира .
Если в твоём восприятии мира моё решение является для тебя каким-то там доказательством, то проблемы с твоим восприятием мира, а не моим.
VD>Чем быстрее можно вникнуть в суть кода, тем он понятнее.
Только "быстрее вникнуть" — это субъективное понятие. Не ты ли лбы в баталиях разбивал, называя всех блабами? Не от того ли, что твои идеи банально сложны, непонятны, и нафиг не нужны поэтому?
VD>Цикл, цикл.
Ещё раз: где цикл в свёртке Option?
VD>Это называется неумение понимать окружающих. Ты возомнил, то только твой взгляд правильный и начинаешь на окружающих ярлыки приклеивать.
И от кого я это слышу?
Я с тобой специально общаюсь на твоём же языке. Ты видишь, каким идиотом я выгляжу, но иронии не понимаешь. Ну, ладно.
VD>В используемом мной языке все необходимые конструкции есть. Как ими пользоваться я прекрасно понимаю и иногда пользуюсь. Разница между нами только в том, что я не испытываю оргазма от этого. VD>Вместо комбинации функций я предпочитаю объявление локальных функций с внятными именами. Все равно, как бы ты не упражнялся с комбинаторами в реальной жизни постоянно возникают ситуации когда кода слишком много. Держать его по месту — запутывать код.
Круто!
VD>На фиг не нужен такой опыт. Это опыт дешифрации.
Дык у тебя опыт-то. Потому фолд тебе и понятен.
VD>Я прекрасно понимаю твоей код. Вот только оценка моя другая — это говнокод. Ни чем не лучше чем упржения С++-ников на шаблонах. Из серии есть возможность — надо использовать.
Спасибо за оценку.
VD>Ну, да. Я понимаю долго. Вася Пупкин долго, еще 10 программистов долго. Но у нас тут есть один не признанный гений выдресировавший себя до такой степени, что имеет в уме интепретатор хаскеля. И он нам объясняет как надо писать код.
Я никому ничего не объясняю. Это ты тут меня пытаешься учить. Заметь, с ТС мы обсудили и он сделал свои выводы. В пользу ли Хаскеля или нет — неважно. А вот ты чего-то пытаешься мне доказать.
За гения спасибо. Я не имею интерпретатора хаскеля в голове, но отзыв мне льстит. Разве что "непризнанный" намекает на что-то уничижительное, но так твоё признание мне и не нужно.
VD>Запомни простую истину. Код надо писать так, чтобы он был понятен большинству окружающих. Всегда можно найти несколько разных способов написать код. И выбирая более сложный вариант надо четко понимать зачем это делает. Что это дает. Если это дает пол строки кода, но увеличивает сложность восприятия, то нужно отказаться от такого выбора.
И кто тут объясняет, как надо писать код?
VE>>Что это за закорючки?
VD>Блаб?
Нет. Это ж твоя фраза.
VD>Уважаемый, ты часом не забыл, что это ты влез в тему и в форум никак не относящийся к хаскелию и развел в ней офтоп?
Не забыл, поэтому уже давно хочу оффтоп прекратить.
Здравствуйте, VladD2, Вы писали:
VD>Что за scanr1? И что все это даст? Чтобы код выполнялся быстро его в цикл нужно переписывать. В один. А это изменение алгоритма.
Пакет stream-fusion прямо так компилирует map f . filter p . map g в один цикл.
ME>>я предпочитаю на такие вещи не надеяться, и записывать прямо: ME>>
solution x = x `zip` map scanr1 max x
VD>И что мы получаем вместо одного цикла?
Один цикл.
VD>Мы не ориентируемся на даунов и быдлокодеров. Но при этом мы хотим сделать технологию доступной для масс.
Ладно, спорить больше не хочу, вкладку закрываю. Если конечно хочешь, можешь ответить, но пиши сразу не мне, а потенциальным читателям, мне ответы на почту не идут.
, разве что там scanr руками написан. Там рекурсией с конца строится список, потом ещё один "цикл" при проходе по списку вперёд. Здесь то же самое. Один цикл при построении в scanr, "второй" при чтении результата. list1 `zip` list2 за два цикла нельзя считать, так как цикл реально один, zip на бесконечных списках работает.
Что этому мешает?
