Re: [Чайник] Хвостовая рекурсия - Декларативное программирование

Стало интересно попробовать на вкус функциональную парадигму (в том виде, в котором она представлена в F#) и окунуться в мир декларативности, так сказать

Вопрос такой: можно ли достигнуть "хвостатости" рекурсии в таком случае:

let rec gen n =
    if n = 1 then ff 0
    else func (gen (n-1))

Если да, то каким образом...
Сейчас fsc не делает из такой функции цикла...
То есть мне надо получить такую конструкцию вида:

func (func (func ... func (ff 0)))

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

П>Вопрос такой: можно ли достигнуть "хвостатости" рекурсии в таком случае:

Любую рекурсию можно преобразовать в хвостовую. В данном случае:

let gen n =
  let rec gen' c n =
    if n = 1 then c (ff 0)
    else gen' (func >> c) (n-1)
  gen' id n

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

N>Любую рекурсию можно преобразовать в хвостовую.

Подробнее смотреть Continuation-passing style

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

N>let gen n =
N>  let rec gen' c n =
N>    if n = 1 then c (ff 0)
N>    else gen' (func >> c) (n-1)
N>  gen' id n
N>

Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
$func^i (ff(0))$ .

Не знаю ваших окамлов, но как-то так:

let gen n =
  let rec gen' acc n =
    if n = 0 then acc
    else gen' (func acc) (n-1)
  gen' (ff 0) n

Твой вариант не дает O(1) по памяти (т.к. континуация должна где-то храниться), тогда как этот дает, если
$func^i (ff(0))$
— это скаляр или растет с ростом i медленнее, чем континуация.

И да, может в окамле есть какой-нить стандартный комбинатор, типа:
$coolCombinator(f,n)=f^n$ .

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

MC>Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
MC> $func^i (ff(0))$ .

Так и происходит. gen' на каждой итерации возвращает int.

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

S>Здравствуйте, Mr.Cat, Вы писали:

MC>>Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
MC>> $func^i (ff(0))$ .

S>Так и происходит. gen' на каждой итерации возвращает int.
не int, конечно, а а', где
val func : a' -> a'

Здравствуйте, samius, Вы писали:
MC>>Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
S>Так и происходит.
В исходном варианте от nikov? Либо я совершенно не втыкаю в ocaml, либо одно из двух. Мне показалось, что gen' аккумулирует в первом аргументе func^n и на последней итерации применяет ее к ff(0).

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

MC>Здравствуйте, samius, Вы писали:
MC>>>Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
S>>Так и происходит.
MC>В исходном варианте от nikov? Либо я совершенно не втыкаю в ocaml, либо одно из двух. Мне показалось, что gen' аккумулирует в первом аргументе func^n и на последней итерации применяет ее к ff(0).

Так и есть. Я ошибся.

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

Но такие вещи все равно приятнее писать на Haskell:

fpower = (foldr (.) id .) . replicate

или

fpower = (appEndo.) . (.Endo) . (mconcat.) . replicate

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

N>

N>fpower = (foldr (.) id .) . replicate
N>

Однако стоит заметить, что эта версия приводит к stack overflow при больших n.

А вот такая строгая, например, не приводит:

fpower' :: Int -> (a -> a) -> a -> a
fpower' n f f0 = foldr' ($) f0 (replicate n f)

Здравствуйте, nikov, Вы писали:
N>Но такие вещи все равно приятнее писать на Haskell:

Я побаиваюсь его, если честно

Синтаксис устрашающе выглядит...
Я сегодня CPS'ом-то себе мозг разрушил окончательно...

Просто интересно развить в себе функциональную составляющую и узнать новые слова типа "комбинатор" и "монада"

Спасибо всем за ответы, вроде разобрался

Здравствуйте, Пельмешко, Вы писали:
П>Я побаиваюсь его, если честно

Синтаксис устрашающе выглядит...
Стоит ли мне продублировать этот совет тут?..

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

П>Я побаиваюсь его, если честно :) Синтаксис устрашающе выглядит...

А в нем ничего страшного нет. Спецификация у него (haskell report) вдвое меньше, чем у C#. Синтаксис, хоть и сжатый, но на мой взгляд очень понятный и удобный. Возможности к абстракции гораздо выше. В сети есть куча учебных материалов.

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

А>А вот такая строгая, например, не приводит:
А>

А>fpower' :: Int -> (a -> a) -> a -> a
А>fpower' n f f0 = foldr' ($) f0 (replicate n f) 
А>

такое и на OCaml близко можно написать

let fpower n f f0 = fold_right (%) (take n [f]) f0;;

Здравствуйте, Mr.Cat, Вы писали:
MC>Другой вариант — не конструировать континуацию целиком, а аккумулировать значение
MC> $func^i (ff(0))$ .

А можно-ли так же аккумулируя значение преобразовать и такой случай:

let rec gen n =
    if n = 1 then ff 0
    else func n (gen (n-1))

То есть если func зависит ещё и от n...

Здравствуйте, Пельмешко, Вы писали:
П>А можно-ли так же аккумулируя значение преобразовать и такой случай:
П>

П>let rec gen n =
П>    if n = 1 then ff 0
П>    else func n (gen (n-1))
П>

П>То есть если func зависит ещё и от n...

Так, тут т.е. получается
$func\ n\ (func\ \dots\ (func\ 3\ (func\ 2\ ff(0)\,)\,)\,)$
Ну тогда надо просто итерировать не от n до 1, а от 2 до n, что-то навроде

let gen n =
  let rec gen' acc i =
    if i > n then acc
    else gen' (func i acc) (i+1)
  gen' (ff 0) 2

От:	Пельмешко	blog
Дата:	14.06.09 13:54
Оценка:

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	14.06.09 14:22
Оценка:	10 (1)

От:	nikov	http://www.linkedin.com/in/nikov
Дата:	14.06.09 14:29
Оценка:

	От:	Mr.Cat
	Дата:	14.06.09 14:50
	Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	14.06.09 15:16
Оценка: