Re: Список максимумов
От: CodingUnit Россия  
Дата: 29.02.12 11:14
Оценка: 51 (1)
Здравствуйте, Аноним, Вы писали:

А>упрощенно, есть список чисел list[double]

А>хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
А>[1,2,3,2,1]
А>[(1,3)(2,3)(3,3)(2,2)(1,1)]

А>Циклами понятно как...


А>и еще TakeWith выдает тип list[Enumerable([double*double*double])], а Map list[double*double*double]



а еще можно так:


def lst = [1, 2, 3, 2, 1];
def (res, _) = lst.FoldRight(([], 0), (x, (res, max)) => if (x > max) ((x, x) :: res, x) else ((x, max) :: res, max));
Re[8]: Список максимумов
От: VoidEx  
Дата: 03.03.12 08:24
Оценка: 6 (1)
Здравствуйте, VladD2, Вы писали:

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


Я же даже ссылку давал. 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? У задачи есть прямое и простой решение — свертка или цикл (что одно и тоже по сути).


Я же достаточно понятно написал. Слияние списка и максимумов хвостов. Слияние — zip. У нас же не тупл списков, а список туплов. Хвосты — tails. Прочти исходный текст-то. Там только "хвосты" сформулированы "от текущего элемента до конца", что суть одно и то же.
  zip   . (id              &&&    map maximum . tails)
слияние  самого [списка]    и     максимумов   хвостов

Если убрать zip, получится тупл двух списков. Если убрать id &&&, получатся только максимумы хвостов.

VD>Я считаю, что понятный, прямо подходяций и наиболее быстрый путь — это самый правильный путь.


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

VD>Свертка — это абстракция цикла. Что там включать то? Перебор в обратную сторону с накопителем.


Ты ведь остался в душе императивщиком, раз свёртку понимаешь через цикл. В таком случае цикл тебе и правда понятнее. Непонятно только, зачем тогда свёртка.
Свёртка — это не абстракция цикла. Свёртка для Option — это что, цикл что ли? А для Tree? Два цикла? Или что-то другое?

VD>Те ерогливы что написал в первом варианте — это конечно куда лучше. Хрень поймешь через 10 минут, но зато очень круто! Мега-хаскель-вый!


Это называется "парадокс Блаба". Императивный программист пишет императивно даже на Haskell.

VD>Люди! Кто понял исходный вариант без напряжения? А вообще кто-то есть кто понял?


Любой хаскелист поймёт сходу, а Блабы разделятся на тех, кто попытается понять и поймёт, и тех, кто будет отстаивать право на невежество.

VD>А чтобы прочесть вот этот
Автор: CodingUnit
Дата: 29.02.12
10 секунд.


Опыт, сын ошибок трудный. Несколько лет назад ты бы прекрасно понял только столь же страшный код с циклами на C# (C++). Время, за которое ты понимаешь код, очень субъективный параметр. Ты им можешь пользоваться в оценке исключительно для себя, а не для кого-то другого. Я на "вот этот" даже взглянуть без слёз не могу. Цикл и то понятнее.

VE>>Не совсем. Например map f . map g . map h обратно не перевести без потерь.


VD>Да ладно! Что этому мешает?


Что это за закорючки?
Очевидно, потенциальная грязь в f, g и h мешает. Придётся анализировать чистоту.

VD>Оптимизация — это исключительно фича компилятора. Если в одном компиляторе ее сделали, то и в других можно сделать.


В прицнипе и зайчика можно научить курить. Если прикрутить анализатор чистоты, то, возможно, получится.

VD>У тебя же никакие компиляторы не помогут. Алгоритм квадратичный и это не лечится.


Тебе виднее

Вообще, спор с тобой я считаю бессмысленным (как и ты спор со мной), мы друг друга ни в чём не переубедим, да и ни к чему, так что давай прекратим? Меня лично интересует только мнение ТС. Точнее, как я понимаю, я его частично заинтересовал, а уж сочтёт он информацию полезной или нет — решать ему. Сочтёт интересным подход Хаскеля — неплохо, сочтёт "кривыми закорючками" — быть посему.
Поэтому если ты будешь отвечать, пожалуйста, постарайся отвечать на это сообщение без задавания флеймовых вопросов. Если есть конкретные вопросы, всегда пожалуйста.
Re[4]: Список максимумов
От: WolfHound  
Дата: 01.03.12 20:07
Оценка: :)
Здравствуйте, VladD2, Вы писали:

VD>Еще надо на К и J для полноты картины. А моно и jpeg-ом его... Не фиг читать что не попадя.

Это все попса. Наш выбор Jot.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 13:09
Оценка: :)
Здравствуйте, m e, Вы писали:

VE>>>
VE>>>x `zip` map maximum (tails x)
VE>>>


ME>а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)


Если это случится, то причиной может быть одно из двух:
1. Мы получили ИИ который способен взять неэффективный алгоритм и подобрать аналогичный эффективный.
2. Мы имеем место с задачей специально подобранной под оптимизацию. А это уже банальное мошенничество, так как на любой другой задаче чуда не случится.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Список максимумов
От: VoidEx  
Дата: 03.03.12 19:32
Оценка: +1
Здравствуйте, 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>Уважаемый, ты часом не забыл, что это ты влез в тему и в форум никак не относящийся к хаскелию и развел в ней офтоп?


Не забыл, поэтому уже давно хочу оффтоп прекратить.
Список максимумов
От: Аноним  
Дата: 29.02.12 10:04
Оценка:
упрощенно, есть список чисел list[double]
хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
[1,2,3,2,1]
[(1,3)(2,3)(3,3)(2,2)(1,1)]

Циклами понятно как...

и еще TakeWith выдает тип list[Enumerable([double*double*double])], а Map list[double*double*double]
Re: Список максимумов
От: CodingUnit Россия  
Дата: 29.02.12 10:46
Оценка:
Здравствуйте, Аноним, Вы писали:

А>упрощенно, есть список чисел list[double]

А>хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
А>[1,2,3,2,1]
А>[(1,3)(2,3)(3,3)(2,2)(1,1)]

А>Циклами понятно как...


А>и еще TakeWith выдает тип list[Enumerable([double*double*double])], а Map list[double*double*double]

def loop(lst, acc)
{
 match (lst)
 {
  | []           => acc.Rev()
  | head :: tail => loop(tail, (head, tail.Max()) :: acc)
 }
}

def res = loop(lst, [])
Re[2]: Список максимумов
От: Аноним  
Дата: 29.02.12 11:12
Оценка:
Здравствуйте, CodingUnit, Вы писали:

CU>Здравствуйте, Аноним, Вы писали:


А>>упрощенно, есть список чисел list[double]

А>>хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
А>>[1,2,3,2,1]
А>>[(1,3)(2,3)(3,3)(2,2)(1,1)]

А>>Циклами понятно как...


А>>и еще TakeWith выдает тип list[Enumerable([double*double*double])], а Map list[double*double*double]



CU>def loop(lst, acc)

CU>{
CU> match (lst)
CU> {
CU> | [] => acc.Rev()
CU> | head :: tail => loop(tail, (head, tail.Max()) :: acc)
CU> }
CU>}

CU>def res = loop(lst, [])


Циклами и я могу... хочется чере map, fold и прочий матан.... (вообще так ли уж надо было его вставлять?)
Re[2]: Список максимумов
От: Аноним  
Дата: 29.02.12 11:23
Оценка:
Здравствуйте, CodingUnit, Вы писали:

CU>Здравствуйте, Аноним, Вы писали:


А>>упрощенно, есть список чисел list[double]

А>>хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
А>>[1,2,3,2,1]
А>>[(1,3)(2,3)(3,3)(2,2)(1,1)]

А>>Циклами понятно как...


А>>и еще TakeWith выдает тип list[Enumerable([double*double*double])], а Map list[double*double*double]



CU>а еще можно так:



CU>
CU>def lst = [1, 2, 3, 2, 1];
CU>def (res, _) = lst.FoldRight(([], 0), (x, (res, max)) => if (x > max) ((x, x) :: res, x) else ((x, max) :: res, max));

CU>



понял, то что и было интересно.
Re[3]: Список максимумов
От: _NN_ www.nemerleweb.com
Дата: 29.02.12 12:34
Оценка:
Здравствуйте, Аноним, Вы писали:

def loop(lst, acc)
{
  match (lst)
  {
    | [] => acc.Rev()
    | head :: tail => loop(tail, (head, tail.Max()) :: acc)
  }
}

def res = loop(lst, [])


А>Циклами и я могу... хочется чере map, fold и прочий матан.... (вообще так ли уж надо было его вставлять?)


А Fold не рекурсия ?
  public FoldLeft[T, TOut] (l : list [T], mutable acc : TOut, f : T * TOut -> TOut) : TOut {
      def loop (_) {
        | [] => acc
        | x :: xs =>
          acc = f (x, acc);
          loop (xs)
      }
      loop (l);
    }

  public FoldRight[T, TOut] (l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut {
     match (l) {
       | [] => acc
       | x :: xs => f (x, FoldRight (xs, acc, f))
    }
  }


https://github.com/rsdn/nemerle/blob/master/lib/list.n#L986

Беглым взглядом видно, что наш цикл хорошо ложится на FoldRight.
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re[4]: Список максимумов
От: Аноним  
Дата: 29.02.12 12:39
Оценка:
Здравствуйте, _NN_, Вы писали:

_NN>Здравствуйте, Аноним, Вы писали:


_NN>
_NN>def loop(lst, acc)
_NN>{
_NN>  match (lst)
_NN>  {
_NN>    | [] => acc.Rev()
_NN>    | head :: tail => loop(tail, (head, tail.Max()) :: acc)
_NN>  }
_NN>}

_NN>def res = loop(lst, [])
_NN>


А>>Циклами и я могу... хочется чере map, fold и прочий матан.... (вообще так ли уж надо было его вставлять?)


_NN>А Fold не рекурсия ?

_NN>
_NN>  public FoldLeft[T, TOut] (l : list [T], mutable acc : TOut, f : T * TOut -> TOut) : TOut {
_NN>      def loop (_) {
_NN>        | [] => acc
_NN>        | x :: xs =>
_NN>          acc = f (x, acc);
_NN>          loop (xs)
_NN>      }
_NN>      loop (l);
_NN>    }

_NN>  public FoldRight[T, TOut] (l : list [T], acc : TOut, f : T * TOut -> TOut) : TOut {
_NN>     match (l) {
_NN>       | [] => acc
_NN>       | x :: xs => f (x, FoldRight (xs, acc, f))
_NN>    }
_NN>  }
_NN>


_NN>https://github.com/rsdn/nemerle/blob/master/lib/list.n#L986


_NN>Беглым взглядом видно, что наш цикл хорошо ложится на FoldRight.


Это я знаю, но вот как написать через Fold не допер... не догадался что аккамулятором может быть и список.
Re[5]: Список максимумов
От: CodingUnit Россия  
Дата: 01.03.12 06:04
Оценка:
Здравствуйте, Аноним, Вы писали:

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


Вообще все функции начиная от Map, Iter, и другие есть частные случаи Fold, в них всех аккумулятором является список.
Re: Список максимумов
От: VoidEx  
Дата: 01.03.12 11:22
Оценка:
Здравствуйте, Аноним, Вы писали:

А>упрощенно, есть список чисел list[double]

А>хочу расширить до list[double*double] где второй элемент есть максимум от конца первого...
А>[1,2,3,2,1]
А>[(1,3)(2,3)(3,3)(2,2)(1,1)]

А>Циклами понятно как...


Вот Haskell

f = uncurry zip . (id &&& map maximum . init . tails)


По желанию перевести на любой язык.
Re[2]: Список максимумов
От: VoidEx  
Дата: 01.03.12 11:23
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, Аноним, Вы писали:


Точнее просто:

f = uncurry zip . (id &&& map maximum . tails)
Re[3]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.12 20:04
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Точнее просто:

VE>
VE>f = uncurry zip . (id &&& map maximum . tails)
VE>


Еще надо на К и J для полноты картины. А моно и jpeg-ом его... Не фиг читать что не попадя. :)
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Список максимумов
От: Аноним  
Дата: 02.03.12 06:28
Оценка:
Здравствуйте, VoidEx, Вы писали:

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


VE>>Здравствуйте, Аноним, Вы писали:


VE>Точнее просто:


VE>
VE>f = uncurry zip . (id &&& map maximum . tails)
VE>


У этого алгоритма не будет случайно n^2 порядок операций?
Re[4]: Список максимумов
От: VoidEx  
Дата: 02.03.12 10:19
Оценка:
Здравствуйте, VladD2, Вы писали:

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


VE>>Точнее просто:

VE>>
VE>>f = uncurry zip . (id &&& map maximum . tails)
VE>>


VD>Еще надо на К и J для полноты картины. А моно и jpeg-ом его... Не фиг читать что не попадя.


Зачем K, на нём хоть и непонятно, зато запись короче. Лучше на Nemerle, и кода больше, и без поллитру не разобрать.
Re[4]: Список максимумов
От: VoidEx  
Дата: 02.03.12 10:22
Оценка:
Здравствуйте, Аноним, Вы писали:

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


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


VE>>>Здравствуйте, Аноним, Вы писали:


VE>>Точнее просто:


VE>>
VE>>f = uncurry zip . (id &&& map maximum . tails)
VE>>


А>У этого алгоритма не будет случайно n^2 порядок операций?


Ну если скорость не порадует, напишете правило перезаписи на свой maxMaximumTails без изменения кода самой функции.
Re[5]: Список максимумов
От: CodingUnit Россия  
Дата: 02.03.12 10:38
Оценка:
Здравствуйте, VoidEx, Вы писали:

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


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


VE>>>Точнее просто:

VE>>>
VE>>>f = uncurry zip . (id &&& map maximum . tails)
VE>>>


VD>>Еще надо на К и J для полноты картины. А моно и jpeg-ом его... Не фиг читать что не попадя.


VE>Зачем K, на нём хоть и непонятно, зато запись короче. Лучше на Nemerle, и кода больше, и без поллитру не разобрать.


если у нас использовать функцию Tails и Maximum то запись получится короче, здесь просто у вас используются встроенные библиотечные функции, а у нас их нет, и кода больше для реализации этих вещей.
Re[5]: Список максимумов
От: Аноним  
Дата: 02.03.12 10:41
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, Аноним, Вы писали:


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


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


VE>>>>Здравствуйте, Аноним, Вы писали:


VE>>>Точнее просто:


VE>>>
VE>>>f = uncurry zip . (id &&& map maximum . tails)
VE>>>


А>>У этого алгоритма не будет случайно n^2 порядок операций?


VE>Ну если скорость не порадует, напишете правило перезаписи на свой maxMaximumTails без изменения кода самой функции.



тогда это точно длиннее и сложнее чем Немерле....
Re[6]: Список максимумов
От: VoidEx  
Дата: 02.03.12 10:50
Оценка:
Здравствуйте, CodingUnit, Вы писали:

CU>если у нас использовать функцию Tails и Maximum то запись получится короче, здесь просто у вас используются встроенные библиотечные функции, а у нас их нет, и кода больше для реализации этих вещей.


Да прям уж короче. Семантически будет столько же.
Можно, конечно, и так написать.
x `zip` map maximum (tails x)


А правила перезаписи у вас есть?

Но в общем-то это всё оффтоп и ясное дело, что вопрос в библиотечных функциях. Топикстартер просил через "всякий матан", я и написал, а уж перевести это можно хоть на C++.
Своим постом я лишь хотел показать, какие нужны функции, чтобы выглядело читаемо и понятно.
"список и максимумы хвостов списка"
Re[6]: Список максимумов
От: VoidEx  
Дата: 02.03.12 11:15
Оценка:
Здравствуйте, Аноним, Вы писали:

А>тогда это точно длиннее и сложнее чем Немерле....


Любой приведённый здесь вариант на Немерле переводится на Хаскель напрямую. Более того, я вам привёл вариант, при котором код функции остаётся понятным и коротким, а работает так быстро, как вам надо. При этом вы делаете вывод, что это "длиннее и сложнее". Чувствуется религия, поэтому я умываю руки.
Re[7]: Список максимумов
От: Аноним  
Дата: 02.03.12 11:26
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, Аноним, Вы писали:


А>>тогда это точно длиннее и сложнее чем Немерле....


VE>Любой приведённый здесь вариант на Немерле переводится на Хаскель напрямую. Более того, я вам привёл вариант, при котором код функции остаётся понятным и коротким, а работает так быстро, как вам надо. При этом вы делаете вывод, что это "длиннее и сложнее". Чувствуется религия, поэтому я умываю руки.


тут не в религии дело... Если такие преобразования прописаны в библиотеке Хаскеля(переписования), то вариант его намного лучше... Иначе если необходимо писать кусок кода переписывания, то получается и больше и сложнее
Re[8]: Список максимумов
От: VoidEx  
Дата: 02.03.12 11:45
Оценка:
Здравствуйте, Аноним, Вы писали:

А>тут не в религии дело... Если такие преобразования прописаны в библиотеке Хаскеля(переписования), то вариант его намного лучше... Иначе если необходимо писать кусок кода переписывания, то получается и больше и сложнее


Многие написаны. Конкретно эти — не знаю. В других языках и того нет.
Смысл в том, что правило перезаписи позволяет вам не менять во всех функциях вхождения map f . tails на оптимизированную версию, а написать одну эффективную реализацию для всех случаев и правило для оптимизатора.
Если по каким-то причинам этот путь вам не нравится, старый путь в виде переписывания кода функции всегда к вашим услугам.

Не понимаю, как это может быть "сложнее"? В худшем случае так же.
Re[9]: Список максимумов
От: Аноним  
Дата: 02.03.12 12:29
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, Аноним, Вы писали:


А>>тут не в религии дело... Если такие преобразования прописаны в библиотеке Хаскеля(переписования), то вариант его намного лучше... Иначе если необходимо писать кусок кода переписывания, то получается и больше и сложнее


VE>Многие написаны. Конкретно эти — не знаю. В других языках и того нет.

VE>Смысл в том, что правило перезаписи позволяет вам не менять во всех функциях вхождения map f . tails на оптимизированную версию, а написать одну эффективную реализацию для всех случаев и правило для оптимизатора.
VE>Если по каким-то причинам этот путь вам не нравится, старый путь в виде переписывания кода функции всегда к вашим услугам.

VE>Не понимаю, как это может быть "сложнее"? В худшем случае так же.


Если таких правил в стандартной библиотеке прописаны наиболее встречающиеся, то супер!!! если написания правил отдано на участь конечного разработчика, то не уверен, что это хорошо...

Еще я не понял такой момент, эти правила могут быть написаны непосредственно рядом с кодом или обязаны быть вынесены в библиотеку?

кстати такое есть в gcc 4.7, но там это захаркоджино(правила)...
Re[10]: Список максимумов
От: VoidEx  
Дата: 02.03.12 12:45
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Если таких правил в стандартной библиотеке прописаны наиболее встречающиеся, то супер!!! если написания правил отдано на участь конечного разработчика, то не уверен, что это хорошо...


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

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


Вроде и так, и сяк.
Re[5]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 15:04
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Зачем K, на нём хоть и непонятно, зато запись короче. Лучше на Nemerle, и кода больше, и без поллитру не разобрать.


Пофлэймить захотелось? Иди в КСВ и там флэйми сколько хочешь.

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

Код который приводят орлы не дельный, но по крайней мере понятен всем кто знаком с языком. Стремление к краткости в ущерб понятности — это ФГМ, на мой взгляд. Делая код кратким нужно нужно добиваться большей выразительности, а не технически сокращать прощать записи.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 15:18
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Можно, конечно, и так написать.

VE>
VE>x `zip` map maximum (tails x)
VE>


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

VE>А правила перезаписи у вас есть?


Что ты имеешь в виду под перезаписью?

VE>Но в общем-то это всё оффтоп


+1

VE>и ясное дело, что вопрос в библиотечных функциях.


Вопрос еще в умении написать не тривиальный код. И у умении прочитать. Твой исходный вариант поймут только заядлые Хаскелисты. Этот вот уже более человекоподобен, но боюсь, что те для кого ты его привел один фиг ничего в нем не понял. По сему и переписать на Н они этот код не смогут.

VE> Топикстартер просил через "всякий матан", я и написал, а уж перевести это можно хоть на C++.


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

Если ты хочешь помочь, то нужно было не только привести набор закорючек, но еще и подробно расписать ход своих мыслей и действий.

VE>Своим постом я лишь хотел показать, какие нужны функции, чтобы выглядело читаемо и понятно.

VE>"список и максимумы хвостов списка"

Для челоека незнакомого с хаскелем в твоем кода:
 = uncurry zip . (id &&& map maximum . init . tails)

являются неопределенными всего лишь:
"uncurry", "." "id", "&&&", "maximum", "init", "tails"

Можешь себе представить полезность своей помощи? :)

Это я уже не говорю о том, что uncurry и id для немерла вообще смысла не имеют.

Ну, а короткое и понятное решение будет выглядить как-то так:
xs.Maximum()

при наличии соответствующей библиотечной функции. :)
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 15:21
Оценка:
Здравствуйте, CodingUnit, Вы писали:

CU>если у нас использовать функцию Tails и Maximum то запись получится короче, здесь просто у вас используются встроенные библиотечные функции, а у нас их нет, и кода больше для реализации этих вещей.


Дык делай выводы из своих же мыслей.

Раз нет, то при написании алгоритма имеет смысл выделить нужные функции. Хотя бы в виде локальных функций.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 15:59
Оценка:
Здравствуйте, CodingUnit, Вы писали:

CU>
CU>def loop(lst, acc)
CU>{
CU> match (lst)
CU> {
CU>  | []           => acc.Rev()
CU>  | head :: tail => loop(tail, (head, tail.Max()) :: acc)
CU> }
CU>}

CU>def res = loop(lst, [])
CU>


Это квадратичный алгоритм. На больших списках будет подтормаживать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 16:04
Оценка:
Здравствуйте, Аноним, Вы писали:

VE>>
VE>>f = uncurry zip . (id &&& map maximum . tails)
VE>>


А>У этого алгоритма не будет случайно n^2 порядок операций?


tails порождает по подписку для каждого элемента списка — это квадрат.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 16:11
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, Аноним, Вы писали:


А>>тогда это точно длиннее и сложнее чем Немерле....


VE>Более того, я вам привёл вариант, при котором код функции остаётся понятным и коротким, а работает так быстро, как вам надо.


Не правда. Это квадратичный алгоритм.
http://zvon.org/other/haskell/Outputlist/tails_f.html

VE>При этом вы делаете вывод, что это "длиннее и сложнее". Чувствуется религия, поэтому я умываю руки.


И правильно делает. На фиг нужен практически зашифрованный алгоритм который в итоге дает "квадрат"?

Тут за глаза хватит банальной правой свертки
Автор: CodingUnit
Дата: 29.02.12
. Скорость будет линейной. Кода будет не намного больше чем твоем варианта.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 16:11
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Любой приведённый здесь вариант на Немерле переводится на Хаскель напрямую.


Я тебе скажу больше. В обратную сторону все точно так же переводится. Вопрос только в наличии библиотечных функций.

VE>Более того, я вам привёл вариант, при котором код функции остаётся понятным


:)))

VE>и коротким, а работает так быстро, как вам надо. При этом вы делаете вывод, что это "длиннее и сложнее". Чувствуется религия, поэтому я умываю руки.


Чувствуется что человек твой код не понимает. И оно не мудрено. Довольно безрассудно ожидать понимания приводя код напичканный выкрутасами с параметрами на незнакомом человеку языке и ожидать от него понимания.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Список максимумов
От: VoidEx  
Дата: 02.03.12 19:28
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Пофлэймить захотелось? Иди в КСВ и там флэйми сколько хочешь.


Я не начинал, а лишь поддержал флейм.

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


Печально наверное быть здоровым на голову. Такой низкий потолок познания.

VD>Не правда. Это квадратичный алгоритм.


Я про rewrite rules написал неспроста.

VD>практически зашифрованный алгоритм


Если вот это зашифрованный алгоритм
-- список и максимумы хвостов
x `zip` map maximum (tails x)

То как же тогда выглядит нормальный? Мне правда интересно. Тут почти слово в слово.

Лично я считаю, что более прямой перевод всё же zip . (id &&& max maximum . tails), так как напрямую выражает: слияние (zip) самого списка (id) и (&&&) максимумов (map maximum) хвостов (tails). Но необходимость uncurry всё портит.

VD>Тут за глаза хватит банальной правой свертки


Ты всерьёз считаешь использование самого базового комбинатора вместо высокоуровневых более понятным?
И как понять, что эта свёртка делает? Крутить в голове рекурсию? Зачем тогда вообще декларативное программирование-то? Как понять мою, я показал — прочесть. Конечно, надо знать, что такое id и &&& например, но никто же не удивляется, что в записи на некоем языке X 1 + 3 * 4 надо знать указанные операторы и уж тем более никому в здравом уме не приходит обвинять сам язык X за то, что вы не знаете, что такое + и *.

VD>В обратную сторону все точно так же переводится.

Не совсем. Например map f . map g . map h обратно не перевести без потерь.
Точнее перевести-то можно, но соптимизировать до map (f . g . h) автоматом уже нельзя.
Re[7]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.12 20:49
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Печально наверное быть здоровым на голову. Такой низкий потолок познания.


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

VD>>Не правда. Это квадратичный алгоритм.


VE>Я про rewrite rules написал неспроста.


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

VD>>практически зашифрованный алгоритм


VE>Если вот это зашифрованный алгоритм

VE>
VE>-- список и максимумы хвостов
VE>x `zip` map maximum (tails x)
VE>

VE>То как же тогда выглядит нормальный? Мне правда интересно. Тут почти слово в слово.

Я о исходном говорил. Этот немного более расшифрованный. Но для тех кто с названиями функций незнаком он не сильно отличается.

VE>Лично я считаю, что более прямой перевод всё же zip . (id &&& max maximum . tails), так как напрямую выражает: слияние (zip) самого списка (id) и (&&&) максимумов (map maximum) хвостов (tails). Но необходимость uncurry всё портит.


А зачем тут этот zip? И зачем тут tails? У задачи есть прямое и простой решение — свертка или цикл (что одно и тоже по сути).

VD>>Тут за глаза хватит банальной правой свертки


VE>Ты всерьёз считаешь использование самого базового комбинатора вместо высокоуровневых более понятным?


Я считаю, что понятный, прямо подходяций и наиболее быстрый путь — это самый правильный путь. Даже если он приведет к написанию нескольких лишних символов. Эти несколько символов легко абстрагируются за функцией. Зато когда кто-то потом будет изучать код у него не возникнет проблем с его понимаением. Ведь и имя у функции будет, так что не придется читать ее код, чтобы понять происходящее, и код этой функции будет проще для понимания. Ну, а уж выбор "экономия нескольких символов vs. квадратичность алгоритма" — это уже просто смешной выбор.

VE>И как понять, что эта свёртка делает?


См. выше.

VE>Крутить в голове рекурсию?


Свертка — это абстракция цикла. Что там включать то? Перебор в обратную сторону с накопителем.

Те ерогливы что написал в первом варианте — это конечно куда лучше. Хрень поймешь через 10 минут, но зато очень круто! Мега-хаскель-вый!

Это мега-вэй переписывается на Н 1 в 1. Только я бы за уши оттаскал тех кто в моем проекте такое оставил.

VE>Зачем тогда вообще декларативное программирование-то?


Чтобы потноваться, судя по твоим словам. Да и декларативного в нем нет нихрена. Банальная декомпозиция в обоих случаях. Только разные алгоритмы и разное количество шаманства.

VE>Как понять мою, я показал — прочесть.




Люди! Кто понял исходный вариант без напряжения? А вообще кто-то есть кто понял?

VE>Конечно, надо знать, что такое id и &&&


Этого мало. Надо еще вникнуть во все пертурбации которые просходят с фнукциями. Правильно понять какая функция с какой склеиваются и в какую передаются. В результате чтобы прочсть твой вариант у меня ушло 20 минут с залезанием в интернет за описанием функций. А чтобы прочесть вот этот
Автор: CodingUnit
Дата: 29.02.12
10 секунд. Ну, можно еще списать это на мое плохое знание хаскеля и полное незнание его библиотек. Но вот я представил как это будет выглядеть на Н и понял, что минут 5 я все равно потратил бы на дешифрацию.

В общем, харкорное ФП-шество очень похоже на те перегибы, что я видел в начале 90-ых когда народ ООП осваивал. Тоже пытались все на ООП залудить. Надо, не надо — не важно.

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


VD>>В обратную сторону все точно так же переводится.

VE>Не совсем. Например map f . map g . map h обратно не перевести без потерь.

Да ладно! Что этому мешает?

VE>Точнее перевести-то можно, но соптимизировать до map (f . g . h) автоматом уже нельзя.


Ах можно? Тогда зачем гнать?

Оптимизация — это исключительно фича компилятора. Если в одном компиляторе ее сделали, то и в других можно сделать.

У тебя же никакие компиляторы не помогут. Алгоритм квадратичный и это не лечится.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Список максимумов
От: Аноним  
Дата: 03.03.12 04:11
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Печально, но ты учти, что такая печаль у всех кто не имеет пятого дана по хаскелю.

VD>И странно было бы предполагать, что на этом форуме такие есть.
Я прочел хотя никогда и не писад на хаскеле.. пеРвый с трудо второй проще чем вариант на немерле хотя на последнем писал.
VD>>>Не правда. Это квадратичный алгоритм.

В хаскеле можно сделать правило переписования map g . map f=map g.f автоматом производящим замену. таким образом там есть способы приводить квадратичный к линейному

VD>Оптимизация — это исключительно фича компилятора. Если в одном компиляторе ее сделали, то и в других можно сделать.

Не факт тут это фича библиотеки и языка. Реализовать это на С не реально так как язык не чистый. А в переписовании все функции должны быть чистыми. В немерле по этой же причине сделать не возможно
Re[8]: Список максимумов
От: m e  
Дата: 03.03.12 09:58
Оценка:
VE>>Я про rewrite rules написал неспроста.

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


rewrite rules, насколько я понимаю, это не хаскель, а GHC хаскель

я уже налетал на их неаккуратность в терминологии; плюсисты например себе такого безобразия не позволяют

поэтому предлагаю подумать над тем, чтобы ввести тут на рсдн порядок -- называть хаскелем стандарт хаскеля (лучше 2010, ну можно еще и 98), а расширения как полагается -- GHC хаскель

чтобы было не слишком длинно это писать, можно хаскель сокращать до х-ь (так многие делают) и GHC хаскель скажем до гх-ь

з.ы. что касается самой задачки, то она явно проектировалась под хаскель
Re[8]: Список максимумов
От: m e  
Дата: 03.03.12 10:05
Оценка:
VD>Люди! Кто понял исходный вариант без напряжения? А вообще кто-то есть кто понял?

тот который c &&& я лично считают неочевидным (и еще вдобавок -- я не одоборяю pointfree style, но это отступление)

VE>>Если вот это зашифрованный алгоритм

VE>>
VE>>-- список и максимумы хвостов
VE>>x `zip` map maximum (tails x)
VE>>


а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)
Re[9]: Список максимумов
От: VoidEx  
Дата: 03.03.12 10:30
Оценка:
Здравствуйте, m e, Вы писали:

ME>я уже налетал на их неаккуратность в терминологии; плюсисты например себе такого безобразия не позволяют


Кто такие плюсисты? Я вот и плюсист, и хаскелист. Под C++ понимаю стандарт, под хаскелем — GHC Haskell. И почти все т.н. хаскелисты являются и плюсистами и в речи о C++ говорят именно о стандартном. Так что дело не в людях, а в том, что у C++ несколько флагманских компиляторов с разными расширениями. У Haskell'я флагманский один, и когда говорят о GADT, совершенно очевидно, что имеют в виду.

ME>поэтому предлагаю подумать над тем, чтобы ввести тут на рсдн порядок -- называть хаскелем стандарт хаскеля (лучше 2010, ну можно еще и 98), а расширения как полагается -- GHC хаскель


Предлагаю установление порядка в разговорах о хаскеле оставить хаскелистам. Они о нём говорят много чаще и слушать вас всё равно не будут. Порядки определяются не исходя из чьего-то эстетического чувства, а из удобства. И если почти всегда говорят о GHC Haskell, то его будут называть просто "хаскель", хотите вы того или нет, потому что понятно из контекста, о чём идет речь. Вот когда непонятно, тогда и упоминают.
Вы один раз случайно наткнулись на непонимание, так как вы имели в виду стандартный хаскель. Что ж, теперь вы, кажется, знаете, что обычно говорят о GHC Haskell, зачем же пытаться остальных подстраивать под себя?
Re[9]: Список максимумов
От: VoidEx  
Дата: 03.03.12 10:46
Оценка:
Здравствуйте, m e, Вы писали:

ME>а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)


Теоретически:
map (foldr f v) . tails === scanr f v
map (foldr1 f) . tails === scanr1 f
maximum === foldr1 max
map (foldr1 max) . tails === scanr1 max
-- scanr1 - O(n)


Исходный пример переписывается в O(n)
x `zip` scanr1 max x
Re[10]: Список максимумов
От: m e  
Дата: 03.03.12 11:03
Оценка:
VE> Так что дело не в людях, а в том, что у C++ несколько флагманских компиляторов с разными расширениями. У Haskell'я флагманский один, и когда говорят о GADT, совершенно очевидно, что имеют в виду.

на GADT я не покушаюсь — с ними действительно все понятно

а вот высказывания типа "на хаскеле это займет О(эн)" искажает реальность — О(эн) будет на ghc хаскеле, а не на хаскеле

VE>Предлагаю установление порядка в разговорах о хаскеле оставить хаскелистам. Они о нём говорят много чаще и слушать вас всё равно не будут. Порядки определяются не исходя из чьего-то эстетического чувства, а из удобства.


такое разгильдяйство как раз создает неудобство большинству — т.е. тем, кто хаскель только начинает изучать

кстати, еще один вполне нормальный вариант — это когда пишут "вот код на хаскеле", а в самом коде указывают прагмы, из которых видно, что юзаются расширения (емнип MigMit так поступает)

т.е. если бы

1. была специальная прагма, задействующая rewrite rules
2. она бы в твоем коде была указана (я предлагаю общаться на ты в обе стороны)
3. и она еще бы гарантировала наличие в rewrite rules необходимого правила переписывания

тогда можно было бы сказать "этот код работает в О(N)", а иначе нет, нельзя
Re[10]: Список максимумов
От: m e  
Дата: 03.03.12 11:05
Оценка:
VE>Исходный пример переписывается в O(n)
VE>
VE>x `zip` scanr1 max x
VE>


да, вот так я и хотел его переписать, только не знал название в хаскеле функции сканирования (я ее еще по АПЛ помню)
Re[11]: Список максимумов
От: VoidEx  
Дата: 03.03.12 11:13
Оценка:
Здравствуйте, m e, Вы писали:

ME>тогда можно было бы сказать "этот код работает в О(N)", а иначе нет, нельзя


Я и не утверждал, что он работает за O(n). Я написал, что если скорость не порадует, можно написать правило перезаписи, причём дал ссылку на описание техники, откуда ясно видно, что речь идёт о GHC.
Re[9]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 14:40
Оценка:
Здравствуйте, 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>Автор просил не "простой и понятный" в понимании кого-то из участников, а "матан"


Ну, давай спросим что хотел автор.

Судя по этому
Автор:
Дата: 29.02.12
автор имел в виду реализацию того же самого без цикла.

VE>что я воспринял как "более высокоуровневые комбинаторы".


Каждый воспринимает все в меру своей испорченности (с)

VE>О результате судить ему, а не тебе.


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

VE> Свёртка менее высокоуровнева, чем tails, ибо это вообще базовый комбинатор, который использовать напрямую не рекомендуется. Именно по причине непонятности.


Глупость какая-то. Более выскоуровневый, менеевысокоуровневый. Это чушь. У нас на лицо разные алгоримы и разные методы их реализации.

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

VE>Свёртка понятна тебе так же, как цикл императивщикам. Им он и правда понятен. Вон все стены они обдолбили, пытаясь понять, чем всякие фолды лучше циклов, им лично циклы понятнее. Но ты же понимаешь, почему так.


Ты сильно отстал от жизни. Они давно использую Линк. А то что им цикл понятнее — это ни разу не их проблема. Лично я тоже переодически предпочитаю цикл и императив, когда он бывает понятнее.

У тебя проблема. Ты ставишь знак равенства между "понятнее" и "короче". Но это не так. Понятнее — проще для восприятия. Чем быстрее можно вникнуть в суть кода, тем он понятнее.

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

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

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

VD>>Свертка — это абстракция цикла. Что там включать то? Перебор в обратную сторону с накопителем.


VE>Ты ведь остался в душе императивщиком, раз свёртку понимаешь через цикл.


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

ФП ни разу не серебряная пуля. И ты прекрасно демонстрируешь оверкил в его использовании, выбирая переусложненные и неэффективные решения (да еще и гордясь этим).

VE> В таком случае цикл тебе и правда понятнее. Непонятно только, зачем тогда свёртка.


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

В высокоуровневом языке и циклы могут выглядеть вполне прилично.

VE>Свёртка — это не абстракция цикла. Свёртка для Option — это что, цикл что ли? А для Tree? Два цикла? Или что-то другое?


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

VD>>Те ерогливы что написал в первом варианте — это конечно куда лучше. Хрень поймешь через 10 минут, но зато очень круто! Мега-хаскель-вый!


VE>Это называется "парадокс Блаба". Императивный программист пишет императивно даже на Haskell.


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

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

Вместо комбинации функций я предпочитаю объявление локальных функций с внятными именами. Все равно, как бы ты не упражнялся с комбинаторами в реальной жизни постоянно возникают ситуации когда кода слишком много. Держать его по месту — запутывать код.

VD>>Люди! Кто понял исходный вариант без напряжения? А вообще кто-то есть кто понял?


VE>Любой хаскелист поймёт сходу


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

VD>>А чтобы прочесть вот этот
Автор: CodingUnit
Дата: 29.02.12
10 секунд.


VE>Опыт, сын ошибок трудный.


На фиг не нужен такой опыт. Это опыт дешифрации.

VE>Несколько лет назад ты бы прекрасно понял только столь же страшный код с циклами на C# (C++).


Я прекрасно понимаю твоей код. Вот только оценка моя другая — это говнокод. Ни чем не лучше чем упржения С++-ников на шаблонах. Из серии есть возможность — надо использовать.

VE>Время, за которое ты понимаешь код, очень субъективный параметр.


Ну, да. Я понимаю долго. Вася Пупкин долго, еще 10 программистов долго. Но у нас тут есть один не признанный гений выдресировавший себя до такой степени, что имеет в уме интепретатор хаскеля. И он нам объясняет как надо писать код.

Запомни простую истину. Код надо писать так, чтобы он был понятен большинству окружающих. Всегда можно найти несколько разных способов написать код. И выбирая более сложный вариант надо четко понимать зачем это делает. Что это дает. Если это дает пол строки кода, но увеличивает сложность восприятия, то нужно отказаться от такого выбора.

VE>>>Не совсем. Например map f . map g . map h обратно не перевести без потерь.


VD>>Да ладно! Что этому мешает?


VE>Что это за закорючки?


Блаб?

VE>Очевидно, потенциальная грязь в f, g и h мешает. Придётся анализировать чистоту.


Очевидно, что это надуманный предлог.

VD>>Оптимизация — это исключительно фича компилятора. Если в одном компиляторе ее сделали, то и в других можно сделать.


VE>В прицнипе и зайчика можно научить курить. Если прикрутить анализатор чистоты, то, возможно, получится.


Когда сказать нечего не стоит нести чушь.

VE>Вообще, спор с тобой я считаю бессмысленным (как и ты спор со мной), мы друг друга ни в чём не переубедим, да и ни к чему, так что давай прекратим?


Уважаемый, ты часом не забыл, что это ты влез в тему и в форум никак не относящийся к хаскелию и развел в ней офтоп?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 14:50
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Я прочел хотя никогда и не писад на хаскеле...

А>В хаскеле можно сделать ...

А чудесное превращение алгоритмов — это вообще нонсенс. Перестановка функций местами алогоритма не изменим. Если было суммирование подсписков, то оно и останется. Или речь идет об подтасовке которая тупо меняет один конерктный алгоритм на другой. Но это обман, а не оптимизация.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Список максимумов
От: m e  
Дата: 03.03.12 15:48
Оценка:
VE>>>>
VE>>>>x `zip` map maximum (tails x)
VE>>>>


ME>>а вот этот считаю понятным, но надо смотреть, вытянут ли его переписывания на О(эн)


VD>Если это случится, то причиной может быть одно из двух:

VD>1. Мы получили ИИ который способен взять неэффективный алгоритм и подобрать аналогичный эффективный.
VD>2. Мы имеем место с задачей специально подобранной под оптимизацию. А это уже банальное мошенничество, так как на любой другой задаче чуда не случится.

maximum (tails x) очевидным образом вычисляется в О(N), и вопрос только в том, есть ли г.хаскеле такой rewrite:
maximum (tails x) = scanr1 max x


я предпочитаю на такие вещи не надеяться, и записывать прямо:
solution x = x `zip` map scanr1 max x


кстати, никто не мешает сделать scanr1 в немерле
Re[11]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 16:50
Оценка:
Здравствуйте, 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 мы в основном будем работать над упрощением применения МП (точнее языкового подхода).

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

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

По сему лично мне смешно когда хаскилисты приходятся мериться пенесами на отдельных строчках кода. Мол у кого короче, тот и прав.

Давайте померим объем кода необходимый, например, для создания парсера современного ЯП. Вот тут Хасель сольет по полной. Его решение будет и длиннее, и не понятнее, и значительно медленнее. При этом производительность труада программиста так же будет сильно не в пользу Хаскеля.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 17:20
Оценка:
Здравствуйте, VoidEx, Вы писали:

VE>Теоретически:...


Предлагаю проверить на практике. Создай тест, плиж, и опубликуй тут результаты. Сравним с другими.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 17:25
Оценка:
Здравствуйте, m e, Вы писали:

ME>такое разгильдяйство как раз создает неудобство большинству — т.е. тем, кто хаскель только начинает изучать


Не могу не согласиться. Это реальные проблемы Хаскеля. У С++ тоже не мало проблем. Но причем тут этот форум и эта тема?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Список максимумов
От: m e  
Дата: 03.03.12 17:48
Оценка:
ME>>я предпочитаю на такие вещи не надеяться, и записывать прямо:
ME>>
solution x = x `zip` map scanr1 max x


VD>И что мы получаем вместо одного цикла?


я при копипасте забыл удалить map

так что правильно
solution x = x `zip` scanr1 max x


тут 2 параллельных (не вложенных) цикла
Re[13]: Список максимумов
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.12 19:00
Оценка:
Здравствуйте, m e, Вы писали:

ME>тут 2 параллельных (не вложенных) цикла


А должен быть один. Короче, предлагаю не телепатировать, а тупо измерить производительность.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Список максимумов
От: VoidEx  
Дата: 03.03.12 19:34
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Что за scanr1? И что все это даст? Чтобы код выполнялся быстро его в цикл нужно переписывать. В один. А это изменение алгоритма.


Пакет stream-fusion прямо так компилирует map f . filter p . map g в один цикл.

ME>>я предпочитаю на такие вещи не надеяться, и записывать прямо:

ME>>
solution x = x `zip` map scanr1 max x


VD>И что мы получаем вместо одного цикла?


Один цикл.

VD>Мы не ориентируемся на даунов и быдлокодеров. Но при этом мы хотим сделать технологию доступной для масс.


Какие-то взаимоисключающие параграфы.
Re[11]: Список максимумов
От: VoidEx  
Дата: 03.03.12 20:08
Оценка:
Здравствуйте, VoidEx, Вы писали:

Ладно, спорить больше не хочу, вкладку закрываю. Если конечно хочешь, можешь ответить, но пиши сразу не мне, а потенциальным читателям, мне ответы на почту не идут.
Re[13]: Список максимумов
От: VoidEx  
Дата: 04.03.12 00:56
Оценка:
Здравствуйте, m e, Вы писали:

ME>так что правильно
solution x = x `zip` scanr1 max x


ME>тут 2 параллельных (не вложенных) цикла


Это смотря как считать. Этот алгоритм ничем не отличается от приведённого тут
Автор: CodingUnit
Дата: 29.02.12
, разве что там scanr руками написан. Там рекурсией с конца строится список, потом ещё один "цикл" при проходе по списку вперёд. Здесь то же самое. Один цикл при построении в scanr, "второй" при чтении результата. list1 `zip` list2 за два цикла нельзя считать, так как цикл реально один, zip на бесконечных списках работает.
Re[14]: Список максимумов
От: m e  
Дата: 04.03.12 08:55
Оценка:
ME>>тут 2 параллельных (не вложенных) цикла
VD>А должен быть один. Короче, предлагаю не телепатировать, а тупо измерить производительность.

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

в ghc 7.4.1 время растет линейно, в ghc 6.8.2 квадратично!

щас напишу подробнее в раздел декл. прогр.
Re[14]: Список максимумов
От: m e  
Дата: 04.03.12 12:13
Оценка:
VD>А должен быть один. Короче, предлагаю не телепатировать, а тупо измерить производительность.

телепатия и вправду не всегда помогает: http://www.rsdn.ru/forum/decl/4646356.aspx
Автор: D. Mon
Дата: 04.03.12
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.