Gibt es eine Standardfunktion höherer Ordnung, um eine Transformation mehrmals anzuwenden?

Question

Ich denke an eine Funktion wie folgt aus:

> 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 

Hinweis: Der Code F # ist, aber ich die Frage mit Haskell getaggt, ocaml und ml-Tags, weil, wenn die Funktion in F # Bibliotheken gibt es nicht, aber es existiert in anderen Sprachen Ich möchte den gleichen Namen verwenden

Answer 1

Sie haben (ganz in der Nähe) eine Antwort bekommen würde durch die Verwendung zum Beispiel Hayoo (oder Hoogle, aber Hoogle ist nicht so flexibel - iterateN wurde nicht gefunden):

• eine Suche nach Int -> (a -> a) -> a -> a mehrere Funktionen aufgedeckt, die das tun, was Sie wollen, aber sind nicht Teil der stdlib.

• Eine Suche nach applyN ergab eine Funktion mit genau dem gleichen Namen mit der Typ-Signatur, die Sie suchen.

• durch den Rückgabewert laxing für Int -> (a -> a) -> a anstatt durch die Suche (man beachte die fehlende -> a am Ende), erhalten Sie die iterateN :: Int -> (a -> a) -> a -> Seq a Funktion, die erdeszt bereits erwähnt hat.

P.S. Hoogle scheint besser in der Lage zu sein, die Reihenfolge der Argumente umzukehren: (a -> a) -> Int -> a -> Seq a liefert erfolgreich 'iterateN :: Int -> (a -> a) -> a -> Seq a', was Hayoo nicht tut.

Answer 2

Es gibt eine iterateN Funktion für Haskell im Data.Sequence Modul, die aussieht wie die, die Sie suchen.

Es ist eigentlich nur ein combinaton von Iterierte + nehmen: let iterateN n f x = take n (iterate f x) Hier ist ein F # Version von iterate (from here) ist Seq.take Teil der F # Standardbibliothek:

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

Answer 3

Eine mögliche Lösung:

> 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)))) 

weitere (bereits erwähnt):

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

(fügen lambdas, wenn Sie es in eine Funktion aktiviert werden sollen)

jedoch nicht vergessen, dass Haskell faul ist: die oben genannten Methoden werden zunächst durch die Anwendung f oft eine Thunk bauen und erst dann beginnen zu bewerten. Manchmal könnte f in konstantem Raum iteriert werden, z. wenn f :: Int -> Int (und f selbst in konstantem Raum arbeitet), aber die oben genannten Ansätze arbeiten nur im linearen Raum.

ich durch eigene strenge Iteration combinator definieren würde, z.B .:

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

oder sogar

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

, die mehr oder weniger die Haskell Übersetzung von dem, was bereits in der Frage gestellt.

Alternativ können wir eine strenge Version von iterate definieren (die IMHO sollte bereits vorhanden sein ...)

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

Answer 4

in der Liste der anderen Möglichkeiten hinzuzufügen, es zu tun,

import Control.Monad.State.Lazy 

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