Come esprimere in modo conciso l'iterazione della funzione?

Question

Esiste un modo sintetico e idiomatico per esprimere function iteration? Cioè, dato un numero n e una funzione f :: a -> a, mi piacerebbe esprimere \x -> f(...(f(x))...) dove f è applicato n volte.

Naturalmente, potrei creare la mia funzione ricorsiva, ma sarei interessato se c'è un modo per esprimerlo a breve usando gli strumenti o le librerie esistenti.

Finora, ho queste idee:

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

ma tutti usano liste intermedi, e non sono molto conciso.

Quello più breve che ho trovato finora utilizza semigruppi:

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

ma funziona solo per i numeri positivi (non per 0).

Principalmente sono concentrato su soluzioni in Haskell, ma sarei interessato anche a soluzioni Scala o anche ad altri linguaggi funzionali.

Answer 1

mi piace idee di pigworker/di Tauli il meglio, ma dal momento che hanno dato solo come un commenti, sto facendo una risposta CW fuori di esso.

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

o

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

forse anche:

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

Answer 2

In Scala:

Function chain Seq.fill(n)(f) 

Vedi scaladoc for Function. Versione Lazy: Function chain Stream.fill(n)(f)

Answer 3

Poiché Haskell è influenzato dalla matematica così tanto, the definition dalla pagina di Wikipedia che hai collegato alla traduzione quasi diretta nella lingua.

Basta controllare questo fuori:

Ora in Haskell:

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

Abbastanza carino, eh?

Quindi cos'è questo? È un tipico schema di ricorsione. E come viene trattato solitamente Haskellers? Lo trattiamo con le pieghe! Così, dopo il refactoring si finisce con la seguente traduzione:

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

o libero-punto, se si preferisce:

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

Come si vede, non v'è alcuna nozione di argomenti della funzione soggetto sia nel Definizione di Wikipedia e nelle soluzioni presentate qui. È una funzione su un'altra funzione, cioè la funzione soggetto viene trattata come un valore.Questo è un approccio di livello superiore a un problema rispetto all'implementazione che coinvolge argomenti della funzione soggetto.

Ora, riguardo alle tue preoccupazioni per gli elenchi intermedi. Dal punto di vista del codice sorgente questa soluzione risulta essere molto simile a una soluzione Scala pubblicata da @jmcejuela, ma c'è una differenza fondamentale che l'ottimizzatore di GHC getta via completamente la lista intermedia, trasformando la funzione in un semplice loop ricorsivo sulla funzione soggetto. Non penso che potrebbe essere ottimizzato meglio.

Per ispezionare comodamente i risultati del compilatore intermedio, raccomando di utilizzare ghc-core.

Answer 4

Anche se non è così conciso come la risposta di jmcejuela (che preferisco), esiste un altro modo in scala per esprimere una tale funzione senza il modulo Function. Funziona anche quando n = 0.

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

Per superare la creazione di un elenco, si può usare la ricorsione esplicita, che al contrario richiede la digitazione più statico.

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

C'è una soluzione equivalente utilizzando pattern matching, come la soluzione in 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)) 
} 

Infine, io preferisco la via breve di scrivere in Caml, dove non v'è alcuna necessità di definire i tipi delle variabili a tutti.

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