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

[Андре]

Она и для фибоначчи замечательно выполняется:

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

[Андре]

И, извини, но я все-таки спрошу:

Цитата:

может, просто приведешь пример?
ну, или ссылки хотя бы )))

Цитата:

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

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

[mazzy]

Цитата:

Сообщение от Андре

Она и для фибоначчи замечательно выполняется:

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

ленивые функциональщики ))))
собственно возвращаемся к моему посту:

Цитата:

Сообщение от mazzy

тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
...
именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.
...
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.

Если бы подобная ленивость была бы в обычном языке, то...
Сейчас в .net вводят LINQ и Lazy-интерфейсы... это конечно не то, но достаточно близко...

можешь рассказать подробнее как "это" работает?

Цитата:

Сообщение от Андре

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

Спасибо что ответил.

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

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

[Андре]

Цитата:

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.

Нет! При чем тут ленивость и при чем тут побочные эффекты.

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

Теперь побочные эффекты. Их здесь нет, но если этот код переписать на C# или Java - их тоже не появится. Им просто не откуда здесь взяться. Ну и вообще, если говорить про функциональные языки программирования - то из тех, что используются в production я знаю только 1 - haskell. Все остальные функциональные языки программирования допускают побочные эффекты.

Цитата:

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))

В языке с поддержкой хвостовой ресурсии - не будет.

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

Цитата:

можешь рассказать подробнее как "это" работает?

Да вроде уже максимально подробно. Смотри - при вызове функции ты на стек помещаешь 4 вещи: адрес возрата и три параметра. Теперь происходит очередной рекурсивный вызов. По идее компилятор должен положить еще 4 параматера. Но он умный и видит, что после того, как ты вернешься из этого рекурсивного вызова то, что до этого лежало на стеке тебе просто уже не понадобится. Ну просто потому что после рекурсивного вызова уже нет никаких вычисленией. А значит текущие значения a, b и count можно смело снять со стека, заменив на новые.

Все равно не понятно ?

[Ace of Database]

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

[Андре]

Можно еще вот так попробовать расписать - вызовы функций, как они будут происходить

fib 5
fib-iter 1 0 5
fib-iter 1 1 4
fib-iter 2 1 3
fib-iter 3 2 2
fib-iter 5 3 1
fib-iter 8 5 0
-> 5

То есть, мы вызываем fib 5, оно вызывает fib-iter 1 0 5, оно вызывает fib-iter 1 1 4 и так далее, пока вызов fib-iter 8 5 0 не вернет 5-ку.

Обрати внимание, что каждый последующий вызов - он самодостаточен. То есть. когда fib-iter 8 5 0 вернет 5-ку ему эту 5-ку надо просто вернуть, а не делать с ней что-то еще вверх по стеку вызовов. Это потому, что у нас последний вызов в функции выглядит так:

(fib-iter (+ a b) a (- count 1))))

А вот если бы он выглядел как то так

a + (fib-iter (+ a b) a (- count 1))))

то рекурсию нельзя было бы оптимизировать. Так как при последнем рекурсивном вызове полученную 5-ку надо была вернуть вверх по стеку, чтобы сложить вот с этой 'a'. И так далее.

Вот. Все - лучше мне уже на форуме не объяснить

p.s.

Цитата:

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли?

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

Цитата:

обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

Вот - вот. Я собственно это и делаю (см выше стек вызовов, что я привел). Просто совместил это с рекурсией, которая при этом еще и хвостовая

[Ace of Database]

Маззи, пожалуйста не приводите мой код как пример дешевого программиста
Я выскочка с гуманитарным образованием.
Для людей с неправильным происхождением свойственно натыкаться на грабли на пути к совершенству. Сейчас я понял, что моя вчерашняя попытка написать пример была ошибкой. Но из-за некоторых таких попыток мне все-таки удалось кое-чего достичь в жизни. И я пока еще выживаю в конкурентной борьбе.
Я готов быть аутсайдером в окружении богов.
Готов получать 500 тыс рублей среди людей, которые получают миллион рублей.
Поэтому и встреваю в беседы великих

[mazzy]

Цитата:

Сообщение от Андре

Это потому, что у нас последний вызов в функции выглядит так:

(fib-iter (+ a b) a (- count 1))))

А вот если бы он выглядел как то так

a + (fib-iter (+ a b) a (- count 1))))

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

ааааааа. так вот почему ты передаешь два аргумента, где первый может потеряться...

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

public var fib(var n)
{
   fibb-iter(1, 0, n);
}

private var fib-iter(var a, var b, var n)
{
   if(n <= 0)
      return b;
   else
      return fib-iter(a+b, b, n-1);
}

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

чертовы функциональщики... )))))

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

[mazzy]

Цитата:

Сообщение от mazzy

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

Интересно, а как Silence свою рекурсию написал?
может, зря я на него бочку качу...

Цитата:

Сообщение от Silence

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

[Андре]

Цитата:

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

Да. Я правда подозреваю, что хороший оптимизатор это в цикл преобразует.

Цитата:

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

Зависит от языка. Есть языки где вообще нет ленивых вычислений. Есть языки, где можно "включить" ленивость используя специальные выражения (ключевое слово lazy в F#), есть языки где все лениво по умолчанию (Haskell).

[Ace of Database]

Маззи, а как вам такой вариант?

static void Job46(Args _args)
{
     int j;
     
     real fibonaci(int n)
     {
        real    first = 0;
        real    second = 1;
        real    result = 0;
        int     i;
        for (i = 0; i < n; i++)
        {
            result = first + second;
            second = first;
            first = result;
        }
        return result;
    }
    ;
    for (j = 0; j < 50; j++)
    {
        info(strfmt("%1", fibonaci(j)));
    }
}

[mazzy]

Цитата:

Сообщение от Ace of Database

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

не знаю. это вам решать.

ваш кусок кода выполняет вычисления за один проход без повторных вычислений. что является достижением. и потребляет фиксированную память.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))

[Ace of Database]

Цитата:

Сообщение от mazzy

не знаю. это вам решать.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))

Нет, теперь я отрекусь от этого! Я постоянно меняюсь.

[mazzy]

Цитата:

Сообщение от Ace of Database

Маззи, а как вам такой вариант?

вложенные то циклы зачем? раньше был один. и это было хорошо.

и снова без комментариев в коде нет комментариев по поводу используемого типа real )
и магическая константа в коде... константу-то можно было бы и прокомментировать.

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

заодно это и было бы обоснованием для магической константы ))))

[Ace of Database]

Цитата:

Сообщение от mazzy

вложенные то циклы зачем?
.....
заодно это и было бы обоснованием для магической константы ))))

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

Константа 50 - тоже для наглядности. Просто красивое число для примера вывода первых 50 членов последовательности.

[Андре]

Прошу прощения, но не удержался:

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.take 50

А вот получение первых 50-ти членов на F#. Ленивое, как ты, mazzy, и хотел

[mazzy]

Some? почему some?
вернее, а что значит Some в данном контексте?

и почему целые 0, 1?
а целые в F# скольки разрядные? как F# относится к переполнению целого?

Цитата:

Сообщение от Андре

Ленивое, как ты, mazzy, и хотел

я не то, чтобы хотел.
я опасался, что построенное супер-выражение в стек ляжет.

причем лобовое решение fib(n-1)+fib(n-2) скорее всего быстро переполнит стек и в функциональном языке за счет повторных подстановок в результирующее супер-выражение.

[mazzy]

int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!

еще фибоначчи на F#
https://msdn.microsoft.com/en-us/vis...n-%5Bfsharp%5D
http://www.blogs.sigristsoftware.com...-Sequence.aspx

мдя...

=========================
а как это ленивое чудо потребляет память?

[Андре]

Цитата:

int - 32 разряда
суффикс I означает bigInt
some(a,b) означает some(tuple(a,b)), что означает nullable tuple(a,b)
tuple(a,b) в контексте функции unfold означает: a - текущее состояние, b - следующее состояние.

так? ахренеть!

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

0I,1I - как ты правильно заметил, что BigInteger, а точнее, обертка вот над этой .NET структурой: https://msdn.microsoft.com/ru-ru/lib...v=vs.110).aspx

Цитата:

The T:System.Numerics.BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.

fun (x, y) -> Some(x, (y, x + y))

Вот это функция, которая на вход принимает некое текущее состояние, а на выходе может быть (ну, если получится) вернет пару значений: очередной элемент последовательности и новое состояние.

Эта функция (как видно по ее названию) противоположна более популярной функции fold (которая в python называется reduce, а в C# LINQ - aggregate):

Цитата:

Seq.fold (fun acc elem -> acc + elem) 0 seq

Здесь мы сворачивает последовательность в одно число путем указания функции - "как именно это делать - суммировать". Вот LINQ:

Цитата:

seq.Aggregate(0, (acc, elen) => acc + elem);

unfold - противоположна - из неких начальных значений обратно разворачивает последовательность.

Теперь про Some - я там выше написал, что эта функция "постарается" вернуть очередное значение. Но компилятор понимает, что это не всегда возможно. И хочет, чтобы ты это понимал и не забывал и предлагает использовать тебе "option type" - аналог монады MayBe из других языков программирования.

[mazzy]

Цитата:

Сообщение от Андре

Слишком много ньюансов, которые уже надо знать.

угу.
http://coub.com/view/b8if4
)