Зачем нужна хвостовая рекурсия?

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

f = 1
m = n
while (m != 1){
  f = f*m
  m = m-1
}

cycle(f = 1, m = n) 
where cycle(f, m) = 
  if (m != 1) cycle(
   f = f*m, 
   m = m-1
  ) else f

Вообще какой-то лол, очень видно совпадение. Но конечно предыдущий вариант рекурсии короче и все равно понятный

Ну естественно я имел ввиду привычные foldLeft/reduce, map, filter.

ФВП на то и функции, что их можно добавлять. Кстати, чем тебе takeWhile не понравился — не хуже, чем foldLeft? Ещё бы они оптимизировались получше...

ФВП на то и функции, что их можно добавлять

Я понимаю. Просто использовал этот термин имея ввиду стандартный ФВП

Кстати, чем тебе takeWhile не понравился — не хуже, чем foldLeft

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

Ну, хорошо, признаю, что твой вариант достаточно ясный. Но ты ж сам пишешь

Другое дело что ФВП - намного лучший вариант по сравнению с циклами и хвостовой рекурсией

Но хвосторекурсивный вариант с ФВП пишется как то так:

(define (fact n k) (if (< n 2) (k n) (k (fact (- n 1) (lambda(comp) (* n comp))))))

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

range(1,n).foldLeft(1)((x,acc)=>x*acc)

Лапша где какие-то кастомные ФВП ради самого факта ФВП не нужны. Только если это делает код чистым и понятным. Вот как выше привели пример ФВП асимптотического приближения

в целом если в команде новички, то проще уже в таких случаях писать потрадиционне

Так зависит от традиций. Для Scheme естественна рекурсия, для Haskell — ФВП.

steps x = 1:map (\y -> (y + x/y)/2) (steps x)
sqrt x eps = last (takeWhile (\y -> abs (x-y*y) > eps) (steps x))

Всё только стандартными функциями.

Вычисляемый goto это switch. Преобразуется тривиально.

хвосторекурсивный вариант с ФВП (define (fact n k) ...)

Ты ФВП с CPS не путай. C ФВП будет (define (fact n) (foldl 1 * (in-range n))) или как-то так.

Ну да, не силен в трминологии. Я имел в виду «с использованием ФВП», ведь продолжение которое там используется по факту является функцией высшего порядка.

У тебя CPS, а не ФВП.

Да, это CPS, стиль, но это не отменяет, что тут используются ФВП. Я уже сказал.

тут используются ФВП.

Можно мильоном разных способов написать с использованием ФВП. Почему ты выбрал именно этот?

Просто первое, что в голову пришло.

Ну может не стоит делать выводы по первому, что пришло в твою голову?

Приведи пример.

Циклы - источник мягко говоря тормозов. Идея, реализовать программу без циклов, но с одним большим, системным - не совсем бесполезная.

Странно. Обычно это как раз таки рекурсия всегда считалась источником тормозов и прерасхода памяти. Оптимизация хвостовой рекурсии как раз и призвана преодолеть эту проблему. Попросту, разворачивать хвосторекурсивные вызовы в цикл. А Ваше мнение воистину оригинально.

хвостовая по-сути: это возможность задания метки для безопасного и безусловного перехода. В многом, это реализуется, если сущности - иммутабельные.

Ну в большинстве языков поддерживаются break и continue, почему они должны быть источниками тормозов? Или это не Вы писали про тормоза в циклах?

monk привел

Я не понял из этого обрывка ничего. Приведи полностью.

И где у него там вообще, рекурсия?

Платиновые треды ЛОРа от деревянных пользователей ЛОРа

Ты овец в стойло загнал уже?

Да, конечно

Я не понял из этого обрывка ничего. Приведи полностью.

(define (fact n) (foldl * 1 (in-range n)))

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

* — перемножает два числа

in-range — возвращает список от 1 до n

Таким образом fact = «перемножить числа от 1 до n».

И где у него там вообще, рекурсия?

Ты ФВП просил.

Циклы - источник мягко говоря тормозов.

напиши qsort с циклом и без него, скомпиляй с -O0 (дабы компилятор рекурсию в цикл не развернул ненароком), и сравни скорость. Будешь удивлён.

Идея, реализовать программу без циклов, но с одним большим, системным - не совсем бесполезная.

Т.е. если мне нужно обратить матрицу 10×10, мне требуется 100³ строчек написать?

Я не просил.:) Речь шла об хвосторекурсивных вызовах. Я привел пример кода хвосторекурсивного, с использованием ФВП (он же CPS, да). Анонимус меня спросил, почему я выбрал именно этот вариант факториала: очевидно же, коль речь идет о хвостовой рекурсии, я привел хвосторекурсивный код. Ладно, проехали.

Ты, баран, так и не понял CPS.

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

на самом деле, дело совсем не в замене call на goto.

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

Вот посмотри на пример из вики:

(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (fac-times n 1))

Т.о. в этом случае TCO позволило добиться быстродействия _равного_ коду на C. Потому-то борщееды и фапают на TCO.

Кстати, глядя на твой пример так и тянется рука переписать в императивном стиле, типо

(define (fact n) (let ((acc 1)) (while (> n 0) (set! acc (* acc n)) (set! n (- n 1))) acc))

А почему ты меня про овец спросил?

Потому-то борщееды и фапают на TCO.

Я об этом сразу и сказал. Причина этого дерьма в том, и только в том, что в некоторых ЯП запрещена муттабельность. Других причин использовать TCO нет, если только не брать в расчет fp-фапанье. Они просто строят циклы черз жопу.

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

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

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

Они просто строят циклы черз жопу.

это ты так думаешь, потому что пишешь только под свой локалхост. На разных платформах циклы надо по разному организовывать, или даже не разворачивать вовсе. На практике вполне существуют случаи, когда нужно сравнительно много памяти для итерации, и потому её повторное выделение не самая лучшая идея. Часто быстрее занять следующий блок, а не возвращаться к уже использованному. Особенно учитывая тот факт, что уже использованный _может_ понадобится в будущем и/или занят другой нитью. В случае мутабельности тебе придётся создавать блокировки, семафоры, и прочие костыли, что убьёт производительность. Ежели же ты каждый раз занимаешь новый блок, то такой проблемы просто нет(конечно возникают другие проблемы, связанные со сборкой мусора и нехваткой памяти).

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

и да, поганость повторного использования видна даже на коде вычисления факториала выше: всё хорошо, пока факториал влезает в машинное слово, но это только для очень маленьких n. Потом придётся использовать какую-нибудь длинную арифметику, а она умножает _не_ _туда_, где аргументы. Т.е. для вычисления X*Y→X, нам нужно сначала вычислить X*n→tmp, а потом tmp->X. Второй операции можно автоматически избежать, если НЕ делать TCO. Т.к. n всё равно небольшое, то время умножения примерно равно времени копирования, и отказ от TCO даёт увеличение скорости почти вдвое.

У тебя стека не хватит без TCO на больших числах. Там уже по*ю быстрей или медленней

Я конечно, не знаю низкоуровневое программировани, но подозреваю, что все перечисленные тобой проблемы — это недостатки современной архитектуры

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

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

раньше и задачи были другие. И методы разработки.

Ещё раз: на всяких lisp'ах _можно_ добиться производительности как на сишке, но кому это надо? Слишком дорого надо за это платить. Дешевле нанять жаба-юниора и купить ещё десяток гигабайт RAM.

У тебя стека не хватит без TCO на больших числах.

кто тебе сказал, что я буду юзать машинный стек? Или что его юзает компилятор ФП язычка? Там внутри неонкаmalloc(3).

Было время, когда мегабайт памяти был за счастье
при этом все летало даже на слабых процессорах

Дай угадаю: тогда не было кеширования всего и вся, 4k-текстур, H.264, AAC и вообще всего, кроме сосноли 80х25.

Не надо ля-ля. Вот что говорил Алан Кей по этому поводу:

Да, в действительности и Lisp и Smalltalk были погублены восьмибитными микропроцессорами и не потому, что они были восьмибитными, а потому что их архитектура была плохой и они они поставили крест на динамических языках. Сегодня эти языки работают приемлемо несмотря на ту же плохую архитектуру из-за гигантских размеров кэша 2 уровня. Некоторая часть работы производится быстро прямо в кэше. Поэтому Lisp и Smalltalk жизнеспособны сегодня. Но оба они, конечно, абсолютно устарели

Вот с тех пор, видать, все и пошло на перекосяк.

Дай угадаю: тогда не было кеширования всего и вся, 4k-текстур, H.264, AAC и вообще всего, кроме сосноли 80х25.

не, ну mp3 было. Правда грузило процессор на 95%, и заикалось, если что-то скомпилировать ☺

Да, в действительности и Lisp и Smalltalk были погублены восьмибитными микропроцессорами и не потому, что они были восьмибитными, а потому что их архитектура была плохой и они они поставили крест на динамических языках. Сегодня эти языки работают приемлемо несмотря на ту же плохую архитектуру из-за гигантских размеров кэша 2 уровня. Некоторая часть работы производится быстро прямо в кэше. Поэтому Lisp и Smalltalk жизнеспособны сегодня. Но оба они, конечно, абсолютно устарели

ну я тебе о том же и говорю.

Проблема только в том, что кроме этих «восьмибитных микропроцессоров» у нас ничего нет. lisp жизнеспособен не только из-за L2, но и из-за виртуальной памяти, которая позволяет программам жрать память сотнями гигабайт, не заморачиваясь её менеджментом. Т.е. сейчас можно организовать стек, который практически никогда не переполнится.

Толку-то от плача Алана? Ну вот такие вот у нас дерьмовые CPU, и что делать? Делать недерьморвые не получается, ибо УЖЕ написаны миллионы строк для дерьмовых. Так и тащим архитектуру i8080 подпирая её костылями каждый год.

Ээ. Рекурсия у тебя в любом случае есть в языке. Вопрос: зачем довешивать в язык ещё одну конструкцию, если можно просто добавить оптимизацию хвостовой рекурсии?

Ну и, собственно, ничего не мешает написать функцию

for :: [a] -> (a -> b) -> [b]

for = flip map

(for xs (\x -> x*x))

p.s.: о господи, ну и LORCODE у вас здесь

нет ни циклов, ни рекурсии, ни ложки.
Есть jnz, jz, jmp. Остальное - рюшечки и бантики.

Фича — это когда что-то есть

назови фичей ссылочную прозрачность и повтори исходный вопрос

Нет jz, есть только колебания электромагнитного поля. И вообще, электромагнитным взаимодействием объясняется подавляющее большинство явлений, наблюдаемых невооружённым взглядом.

Странно, почему ТС не пустился в философские рассуждения о физике

здесь дополнительная функция fac-times как раз и нужна для того, что-бы создать переменную счётчика цикла, в параметре n

В Схемке не нужна, есть же форма let с меткой

(define (factorial n)
  (let loop ((n n) (acc 1))
    (if (< n 0)
        acc
        (loop (- n 1) (* acc n)))))

Других причин использовать TCO нет

Рекурсию используют потому что это удобно, а чтобы свободно использовать рекурсию - нужна ТСО.