Есть ли стандартная функция более высокого порядка для применения преобразования несколько раз?

Question

Я имею в виду функции, как это:

> let applyN (initial : 't) (n:int) (f : 't -> 't) = seq {1..n} |> Seq.fold (fun s _ -> f s) initial;; 

val applyN : initial:'t -> n:int -> f:('t -> 't) -> 't 

> applyN 0 10 (fun x -> x + 1);; 
val it : int = 10 

Примечание: Код F #, но я меченый вопрос с Haskell, OCaml и мл тегов, потому что, если функция не существует в F библиотеках # но существует в других языках. Я хотел бы использовать одно и то же имя.

Answer 1

Вы получили бы (очень близко к) ответ, используя, например Hayoo (или Hoogle, но Hoogle не столь гибки - iterateN не был найден):

• поиск Int -> (a -> a) -> a -> a показал несколько функций, которые делают то, что вы хотите, но не являются частью STDLIB.

• a search for applyN возвратил функцию с тем же именем с типом подписи, который вы ищете.

• по laxing возвращаемого значения при поиске Int -> (a -> a) -> a вместо (обратите внимание на недостающую -> a в конце), вы получаете функцию iterateN :: Int -> (a -> a) -> a -> Seq a которая erdeszt уже упоминалась.

P.S. Hoogle, похоже, более способна переворачиваться вокруг порядка аргументов: (a -> a) -> Int -> a -> Seq a успешно возвращает 'iterateN :: Int -> (a -> a) -> a -> Seq a`, которого нет в Hayoo.

Answer 2

В Haxell есть функция iterateN для модуля Data.Sequence, который похож на тот, который вы ищете.

Это на самом деле просто combinaton из итерации + взять: let iterateN n f x = take n (iterate f x) Вот F # версии итерации (from here), Seq.take является частью стандартной библиотеки F #:

let rec iterate f value = seq { 
    yield value 
    yield! iterate f (f value) } 

Answer 3

Возможным решения:

> import Data.Monoid 
> import Debug.SimpleReflect -- not really needed, just for showing the result 
> (appEndo . mconcat . replicate 5 . Endo $ f) a 
f (f (f (f (f a)))) 

Другой (уже упоминалось):

> iterate f a !! 5 
f (f (f (f (f a)))) 

(добавить лямбды, если вы хотите, чтобы превратить его в функцию)

Однако, не забывайте, что Haskell ленив: вышеуказанные методы сначала построить преобразователь, применяя f много раз, и только после этого приступить к оценке. Иногда f может быть итерирован в постоянном пространстве, например. когда f :: Int -> Int (и f сам работает в постоянном пространстве), но приведенные выше подходы работают только в линейном пространстве.

Я бы определил собственной строгой итерации комбинатора, например .:

iter :: Int -> (a -> a) -> a -> a 
iter 0 _ x = x 
iter n f x = iter (pred n) f $! f x 

или даже

iter n f x = foldl' (flip $ const f) x [1..n] 

который более менее в Haskell перевод того, что было уже размещены в этом вопросе.

В качестве альтернативы, можно можно определить строгую версию iterate (что ИМХО должно уже существовать ...)

iterate' :: (a -> a) -> a -> [a] 
iterate' f x = x : (iterate' f $! f x) 

Answer 4

Чтобы добавить в список других способов сделать это,

import Control.Monad.State.Lazy 

applyN initial n = 
    flip execState initial . replicateM_ n . modify