[Linq] проверить последовательность - .NET

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

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

JR>>>Рекурсия — гадость сама по себе, тем более, что без неё практически всегда можно обойтись.

G>>Расскажи это программистам на haskell\ocaml\lisp\f#

А>Явная рекурсия — гадость. Она — как 'goto' функционального программирования.
Громкие слова, а толку ноль.

А>Практичеси всегда ее можно заменить на комбинацию более высокоуровневых конструкций (map/fold/unfold и т.д.).
Сделай-ка dropWhile без рекурсии. Или хотя бы эту самую проверку на упорядоченность.

А>За более детальным объяснением с доказательствами и примерами можно обратиться к классическому труду почитаемого тут Эрика Мейера Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire
Я много умного прочитал, в том числе и эту статью. Но у меня хватает мозга не кидаться громкими заявлениями.

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

A>лучше богопротивное изменямое состояние, чем сортировка или агрегация.
A>да и ничего богопротивного тут нет, бог создал Linq таким , что он позволяет использовать внешнюю переменную, потому что бог не фанат и идеолог, а практик.

Согласен.

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

            int p = int.MinValue;
            if (arr.Any(x => p > (p = x) ))
                Console.WriteLine("Не упорядочена");

Здесь это вроде прокатывает, но на более сложных задач это чревато ошибками, соответственно превосходство над старым-добрым foreach'ем теряется.

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

G>2) Если объекты неизменяемые, то в большинстве случаев не надо создавать новые экземпляры, только ссылки на них

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

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

FR>Этот не работает

FR>Так как удаляет последний элемент.

Я так и понял. Вот этим и чревата работа с индексами, что легко ошибиться по невнимательности.

FR>Новый массив не создается, в D массивы ссылочные, создается срез который дает доступ только к нужным элементам.

С точки зрения понятности алгоритма это не важно, это важно только с точки зрения скорости и потребляемой памяти.

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

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

При этом все эти оценки субъективны.

U>В императивном алгоритме дополнительных сущностей вводится две: это предыдущий и текущий элементы (или их индексы). В рекурсивном алгоритме дополнительных сущностей три: во-первых, усеченная коллекция, во-вторых, индексы предыдущего и текущего элемента. Т.е. избавиться от предыдущего и текущего элемента все равно не получилось, но зато пришлось ввести еще лишнюю сущность — усеченную коллекцию, соответственно алгоритм стал сложнее.

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

let rec f = function 
  | a::b::_  when a > b   -> false
  | h::t                  -> f t
  | _                     -> true

Тут все сущности уровня for или if в сиобразных.
А если на том же OCaml взять комбинаторный вариант:

let f l = pairwise l |> for_all (fun (a, b) -> a <= b)

Вообще деларативное описание чего хотим.

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

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

Тут не модифицируется и не копируется колекция, как уже писал используется срез который в машинном коде сводится к манипуляции указателями, и так как рекурсия хвостовая то она в том же машинном коде приводится к циклу:

pure auto f(int Arr[])
{
    if(Arr.length < 2)
        return true;
    
    if(Arr[0] > Arr[1])
        return false;
    
    return f(Arr[1 .. $]);
}

pure auto f(int Arr[])
{
00402010  sub         esp,20h 
00402013  mov         ecx,dword ptr [esp+28h] 
    if(Arr.length < 2)
00402017  push        ebx  
00402018  push        esi  
00402019  mov         esi,dword ptr [esp+2Ch] 
0040201D  cmp         esi,2 
00402020  push        edi  
00402021  jae         main@f+21h (402031h) 
        return true;
00402023  pop         edi  
00402024  mov         eax,1 
00402029  pop         esi  
0040202A  pop         ebx  
0040202B  add         esp,20h 
0040202E  ret         8    
    
    if(Arr[0] > Arr[1])
00402031  mov         edx,ecx 
00402033  mov         ebx,dword ptr [edx] 
00402035  mov         eax,esi 
00402037  cmp         ebx,dword ptr [edx+4] 
0040203A  jle         main@f+37h (402047h) 
        return false;
0040203C  pop         edi  
0040203D  xor         eax,eax 
0040203F  pop         esi  
00402040  pop         ebx  
00402041  add         esp,20h 
00402044  ret         8    
    
    return f(Arr[1 .. $]);
00402047  lea         edi,[esi-1] 
0040204A  add         edx,4 
0040204D  mov         ecx,edx 
0040204F  mov         dword ptr [esp+0Ch],edi 
00402053  mov         esi,edi 
00402055  mov         dword ptr [esp+10h],edx 
00402059  cmp         dword ptr [esp+0Ch],2 
0040205E  jb          main@f+13h (402023h) 
00402060  jmp         main@f+21h (402031h)

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

FR>На OCaml рекурсивный вариант будет такой:

FR>

FR>let rec f = function 
FR>  | a::b::_  when a > b   -> false
FR>  | h::t                  -> f t
FR>  | _                     -> true
FR>

Если честно, то глядел-глядел, но логику уловить вообще не сумел, т.е. отдельные элементы вроде понятны, но почему они работают как единое целое непонятно совершенно. Как, например, компилятор догадался, что такое a и b?

FR>

FR>let f l = pairwise l |> for_all (fun (a, b) -> a <= b) 
FR>

FR>Вообще деларативное описание чего хотим.

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

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

FR>Тут не модифицируется и не копируется колекция, как уже писал используется срез который в машинном коде сводится к манипуляции указателями, и так как рекурсия хвостовая то она в том же машинном коде приводится к циклу:

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

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

А>>Явная рекурсия — гадость. Она — как 'goto' функционального программирования.
G>Громкие слова, а толку ноль.

В общем-то по сути правильно, если возможно лучше использовать комбинаторы.
Но даже при том что рекурсия это goto функциональщины, она все-равно проще и лучше чем императивщина

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

U>Если честно, то глядел-глядел, но логику уловить вообще не сумел, т.е. отдельные элементы вроде понятны, но почему они работают как единое целое непонятно совершенно. Как, например, компилятор догадался, что такое a и b?

Боюсь я не сумею в двух словах объяснить что такое паттерн матчинг, это надо самому грокать

Компилятор не догадывается он сверху вниз пытается сопоставить образцы которые ему дали и если получилось присвоить переменным
образца (тем самым a и b то есть это и одновременно объявление переменных) реальные значения.
Конкретно строку a::b::_ when a > b можно прочитать примерно так "список должен содержать два идущих друг за другом элемента a и b
(и неважный нам хвост _) таких что a > b" если это условие выполняется то элементам a и b сопоставятся реальные значения из списка
и выполнится то что идет после "->" то есть вернется false.

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

А>>Явная рекурсия — гадость. Она — как 'goto' функционального программирования.
G>Громкие слова, а толку ноль.

Слова-то не мои. Все притенции — к Эрику.

G>Сделай-ка dropWhile без рекурсии. Или хотя бы эту самую проверку на упорядоченность.
Ну многие вещи через goto тоже проще и короче сделать

Стоило ли городить весь этот огород из Foldable да Traversable если те же деревья можно рекурсивно обойти?
Ну впрочем

myDropWhile p = foldr (++) [] . unfoldr st
    where
      st []     = Nothing
      st (x:xs) = if p x then Just ([],xs) else Just ((x:xs),[])

А упорядочность тут вроде почти все без рекурсий решили.

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

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

А>>>Явная рекурсия — гадость. Она — как 'goto' функционального программирования.
G>>Громкие слова, а толку ноль.
А>Слова-то не мои. Все притенции — к Эрику.
Так не надо их повторять, головой думай.

G>>Сделай-ка dropWhile без рекурсии. Или хотя бы эту самую проверку на упорядоченность.
А>Ну многие вещи через goto тоже проще и короче сделать

Какие например? Я знаю только одну — выход их вложенных циклов, она собственно так и делается при необходимости.

А>Стоило ли городить весь этот огород из Foldable да Traversable если те же деревья можно рекурсивно обойти?
Не выкручивайся теперь.

А>Ну впрочем
А>

А>myDropWhile p = foldr (++) [] . unfoldr st
А>    where
А>      st []     = Nothing
А>      st (x:xs) = if p x then Just ([],xs) else Just ((x:xs),[])
А>

Жесть

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

dropWhile p [] = []
dropWhile p x:xs = if p x then dropWhile p xs else (x:xs)

isOrdered [] = true
isOrdered [_] = true
isOrdered a:b:xs = (a<b) && isOrdered (b:xs)

Вот так очень даже ниче смотрится.

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

U>Здравствуйте, k.o., Вы писали:

KO>>С такой логикой, тебе придётся держать в голове всю историю изменений состояния нерекурсивного алгоритма.

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

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

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

FR>Конкретно строку a::b::_ when a > b можно прочитать примерно так "список должен содержать два идущих друг за другом элемента a и b
FR>(и неважный нам хвост _) таких что a > b" если это условие выполняется то элементам a и b сопоставятся реальные значения из списка
FR>и выполнится то что идет после "->" то есть вернется false.

Тогда этот шаг более-менее понятен, а вот в этом шаге:

| h::t                  -> f t

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

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

G>Только убого получилось, почти как у тебя.
G>

G>isOrdered [] = true
G>isOrdered [_] = true
G>isOrdered a:b:xs = (a<b) && isOrdered (b:xs)
G>

G>Вот так очень даже ниче смотрится.

Мне кстати ваш предыдущий вариант даже больше понравился

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

U>Здравствуйте, k.o., Вы писали:

KO>>Как-то так, компилировать не пробовал и с нерекурсивным алгоритмом мог немного налажать, он, как ни странно, оказался сложнее рекурсивного.

U>Если ты так любишь строгость определений, то нужно заменить:

U>>Поэтому использовать рекурсию нужно только там где без этого никак не обойтись

U>на

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

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

На самом деле у нерекурсивного варианта, несмотря на всю его неприглядность, есть пара важных особенностей: 1) узлы могут быть собраны сборщиком мусора сразу после их обработки и 2) в случае слишком глубокой рекурсии мы получим OutOfMemoryException, а не StackOverflowException, при котором даже блоки finally не выполняются. Эквивалентный (при наличии оптимизации хвостовых вызовов) рекурсивный код, использующий CPS, будет выгледть уже не так хорошо:

int RecursiveNodeCount(Tree root, Func<int, int> continuation)
{
    if (root == null)
    {
        return continuation(0);
    }

    return RecursiveNodeCount(
        root.Left,
        leftCount =>
            RecursiveNodeCount(
                root.Right,
                rightCount => continuation(1 + leftCount + rightCount)));
}

int RecursiveNodeCount(Tree root)
{
    return RecursiveNodeCount(root, x => x);
}

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

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

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

FR>>Конкретно строку a::b::_ when a > b можно прочитать примерно так "список должен содержать два идущих друг за другом элемента a и b
FR>>(и неважный нам хвост _) таких что a > b" если это условие выполняется то элементам a и b сопоставятся реальные значения из списка
FR>>и выполнится то что идет после "->" то есть вернется false.

U>Тогда этот шаг более-менее понятен, а вот в этом шаге:
U>

U>| h::t                  -> f t
U>

U>как компилятор догадывается, что у списка надо отсечь первый элемент?

:: — один из типов шаблонов, поддерживаемых OCaml, просто встроенная в компилятор поддержка.
Тут компилятор ничего не "отсекает", он просто проверяет совпадение списка с образцом h::t и в случае успеха (если список не пуст) предоставляет Вам имена h и t для доступа к совпавшим частям (голове и хвосту) списка.

U>Если бы надо было отсечь два первых элемента, то как бы эта строчка выглядела?

| h1::h2::tl -> f tl

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

U>Тогда этот шаг более-менее понятен, а вот в этом шаге:

U>

U>| h::t                  -> f t
U>

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

Так тут и не надо догадываться, в ФЯ список это конструкция вида <элемент>::<хвост>, например в OCaml список можно задать таким псевдокодом

type 'a list = [] | :: of 'a * 'a list

То есть список или пустой или состоит из элемента и хвоста который сам является списком.
Двоеточие это оператор конструирующий список он принимает слева элемент справа список.

Для двух элементов будет так:

 a::b::tail -> ...

Ну и учти что сопоставление идет сверху вниз, и срабатывает первое удачное.

Здравствуйте, Пельмешко, Вы писали:

U>>Если бы надо было отсечь два первых элемента, то как бы эта строчка выглядела?
П>

П>| h1::h2::tl -> f tl
П>

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

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

U>Здравствуйте, Пельмешко, Вы писали:

U>>>Если бы надо было отсечь два первых элемента, то как бы эта строчка выглядела?
П>>

П>>| h1::h2::tl -> f tl
П>>

U>А если нужно одновременно работать с двумя списками? Как компилятор определяет о каком списке идет речь?

Приведённый выше код:

let rec f = function 
    | a::b::_  when a > b   -> false
    | h::t                  -> f t
    | _                     -> true

Является укороченной записью следующего:

let rec f xs =
    match xs with
    | a::b::_  when a > b   -> false
    | h::t                  -> f t
    | _                     -> true

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

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	07.08.10 10:30
Оценка:

	От:	Undying
	Дата:	07.08.10 10:31
	Оценка:	+1

	От:	Undying
	Дата:	07.08.10 10:34
	Оценка:

	От:	Undying
	Дата:	07.08.10 10:39
	Оценка:	+1

	От:	FR
	Дата:	07.08.10 10:46
	Оценка:

От:	Пельмешко	blog
Дата:	07.08.10 13:26
Оценка:	2 (1) +1