Как кратко выразить функциональную итерацию?

Есть ли сжатый, идиоматический способ выражения итерации функций? То есть, учитывая число n и функцию f :: a -> a, я хотел бы выразить \x -> f(...(f(x))...), где f применяется n -times.

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

До сих пор у меня были следующие идеи:

\n f x -> foldr (const f) x [1..n]
\n -> appEndo . mconcat . replicate n . Endo

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

Самый короткий, который я нашел до сих пор, использует полугруппы:

\n f -> appEndo . times1p (n - 1) . Endo,

но он работает только для положительных чисел (не для 0).

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

Ответ 1

Мне нравятся идеи свиней/таули, но, поскольку они только давали это как комментарии, я делаю из него ответ CW.

\n f x -> iterate f x !! n

или

\n f -> (!! n) . iterate f

возможно даже:

\n -> ((!! n) .) . iterate

Ответ 2

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

Просто проверьте это:

Теперь в Haskell:

iterateF 0 _ = id
iterateF n f = f . iterateF (n - 1) f

Довольно аккуратно, да?

Так что это? Это типичный рекурсивный рисунок. И как Хаскеллеры обычно относятся к этому? Мы относимся к этому с складками! Поэтому после рефакторинга мы получим следующий перевод:

iterateF :: Int -> (a -> a) -> (a -> a)
iterateF n f = foldr (.) id (replicate n f)

или без точек, если вы предпочитаете:

iterateF :: Int -> (a -> a) -> (a -> a)
iterateF n = foldr (.) id . replicate n

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

Теперь о ваших заботах о промежуточных списках. С точки зрения исходного кода это решение оказывается очень похожим на решение Scala, отправленное @jmcejuela, но есть ключевое отличие, которое оптимизатор GHC полностью исключает промежуточный список, превращая функцию в простой рекурсивный цикл над объектом функция. Я не думаю, что его можно было бы оптимизировать лучше.

Чтобы комфортно проверить результаты промежуточного компилятора для себя, я рекомендую использовать ghc-core.

Ответ 3

В Scala:

Function chain Seq.fill(n)(f)

Смотрите scaladoc для функции. Ленивая версия: Function chain Stream.fill(n)(f)

Ответ 4

Хотя это не так лаконично, как ответ jmcejuela (что я предпочитаю), есть еще один способ в scala выразить такую функцию без модуля Function. Он также работает, когда n = 0.

def iterate[T](f: T=>T, n: Int) = (x: T) => (1 to n).foldLeft(x)((res, n) => f(res))

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

def iterate[T](f: T=>T, n: Int): T=>T = (x: T) => (if(n == 0) x else iterate(f, n-1)(f(x)))

Существует эквивалентное решение, использующее сопоставление шаблонов, например, решение в Haskell:

def iterate[T](f: T=>T, n: Int): T=>T = (x: T) => n match {
  case 0 => x
  case _ => iterate(f, n-1)(f(x))
}

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

let iterate f n x = match n with 0->x | n->iterate f (n-1) x;;
let f5 = iterate f 5 in ...