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

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

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

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

Так match позволяет одновременно работать с несколькими списками или нет? Т.е. можно ли написать так: match xs1, xs2 with... ?

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

U>Так match позволяет одновременно работать с несколькими списками или нет? Т.е. можно ли написать так: match xs1, xs2 with... ?

Да без проблем:

let rec iter2 f l1 l2 =
  match (l1, l2) with
    ([], []) -> ()
  | (a1::l1, a2::l2) -> f a1 a2; iter2 f l1 l2
  | (_, _) -> invalid_arg "List.iter2"

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

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

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

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

SC>Ничесе, какие у вас в мирке разночтения. Я думал, рекурсия — это вообще основа функционального программирования.

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

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

Ну это понятно, что нет смысла лепить низкоуровневую конструкцию, если у тебя есть высокоуровневая. Это вообще не ФП-специфичная вещь, а универсальная.

Спасибо за вежливый и содержательный ответ. Приятно общаться с вежливым человеком. Жаль, на RSDN не все такие.

U>Это типа здесь Arr не промежуточное состояние? И чем же оно не промежуточное и не состояние?

Типа нет, это (неизменяемые) аргументы функции. Промежуточное состояние — это когда ты создаешь переменную и ее изменяешь.

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

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

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

Рекурсия — это основная конструкция функционального программирования, обеспечивающая в нем полноту Тьюринга. Как можно говорить, что без нее можно обойтись? О чем речь вообще?

Чета, ребята, я смотрю у вас у всех разное понимание функционального программирования.

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


SC>Рекурсия — это основная конструкция функционального программирования, обеспечивающая в нем полноту Тьюринга. Как можно говорить, что без нее можно обойтись? О чем речь вообще?

Если брать математический базис ФП — лямбда исчисление, то рекурсия не является основной конструкцией, и определяется через Y — комбинатор.

SC>Чета, ребята, я смотрю у вас у всех разное понимание функционального программирования.

Так корней много у функциональщины:

1) Классическое лямбда исчисление.

2) Теория категорий.

3) Нормальные алгорифмы Маркова.

... Склероз но точно что-то еще было

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

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

В большинстве языков можно объявить функцию (метод, процедуру) самому. Представляете?

U>

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

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

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

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

K>В большинстве языков можно объявить функцию (метод, процедуру) самому. Представляете?

И? Это типа очень хорошо, когда для решения тривиальных задач нужно писать специальные функции?

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

U>>

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

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

То что неинициализированное с точки зрения алгоритма p уже получило значение корректное с точки зрения компилятора и рантайма. В некоторых случаях (например, при ошибках в реализации алгоритма) это чревато неочевидными ошибками (т.е. такими на которые ни компилятор не ругается, ни рантайм не падает).

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

U>>

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

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

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

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

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

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

K>>В большинстве языков можно объявить функцию (метод, процедуру) самому. Представляете?

U>И? Это типа очень хорошо, когда для решения тривиальных задач нужно писать специальные функции?

Это лучше чем писать циклы.

Комбинатор типа pairwise обладает в разы большим потенциалом повторного использования, чем написанный цикл.

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

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

KO>2) в случае слишком глубокой рекурсии мы получим OutOfMemoryException, а не StackOverflowException, при котором даже блоки finally не выполняются.
Покажи код где такое происходит.

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

U>Это типа очень хорошо, когда для решения тривиальных задач нужно писать специальные функции?

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

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

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

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

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

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

KO>>На самом деле у нерекурсивного варианта, несмотря на всю его неприглядность, есть пара важных особенностей:
KO>>1) узлы могут быть собраны сборщиком мусора сразу после их обработки
G>Это в случае использования генератора, а не материализованной коллекции.

Разумеется, GC не будет собирать объекты если они ещё где-то используются.

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

int RecursiveNodeCount(Tree root)
{
    if (root == null)
    {
        return 0;
    }

    return 1 + RecursiveNodeCount(root.Left) + RecursiveNodeCount(root.Right);
}

Как здесь поможет оптимизация хвостовой рекурсии и может-ли GC собрать root, до завершения работы RecursiveNodeCount(root.Left) и вызова RecursiveNodeCount(root.Right)?

KO>>2) в случае слишком глубокой рекурсии мы получим OutOfMemoryException, а не StackOverflowException, при котором даже блоки finally не выполняются.
G>Покажи код где такое происходит.

Что происходит? OutOfMemoryException? StackOverflowException? Код настолько тривиален, что, подозреваю, я неправильно тебя понял.

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

U>Хорошим инструментов является тот, в котором нужно производить декомпозицию тогда, когда это действительно нужно

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

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

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

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

KO>>>На самом деле у нерекурсивного варианта, несмотря на всю его неприглядность, есть пара важных особенностей:
KO>>>1) узлы могут быть собраны сборщиком мусора сразу после их обработки
G>>Это в случае использования генератора, а не материализованной коллекции.

KO>Разумеется, GC не будет собирать объекты если они ещё где-то используются.

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

KO>

KO>int RecursiveNodeCount(Tree root)
KO>{
KO>    if (root == null)
KO>    {
KO>        return 0;
KO>    }

KO>    return 1 + RecursiveNodeCount(root.Left) + RecursiveNodeCount(root.Right);
KO>}
KO>

KO>Как здесь поможет оптимизация хвостовой рекурсии и может-ли GC собрать root, до завершения работы RecursiveNodeCount(root.Left) и вызова RecursiveNodeCount(root.Right)?с

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

KO>>>2) в случае слишком глубокой рекурсии мы получим OutOfMemoryException, а не StackOverflowException, при котором даже блоки finally не выполняются.
G>>Покажи код где такое происходит.

KO>Что происходит? OutOfMemoryException? StackOverflowException? Код настолько тривиален, что, подозреваю, я неправильно тебя понял.

Реальный рекурсивный код где происходит OutOfMemoryException, но не происходит StackOverflowException.
И как помогут циклы в этом случае?