Jak zwięźle wyrażać iterację funkcji?

Question

Czy istnieje zwięzły, idiomatyczny sposób wyrażania function iteration? Oznacza to, że mając numer n i funkcję f :: a -> a, chciałbym wyrazić \x -> f(...(f(x))...), gdzie f jest stosowany n-razy.

Oczywiście, mógłbym stworzyć dla niego własną funkcję rekursywną, ale byłbym zainteresowany, jeśli istnieje sposób na szybkie wyrażenie tego przy użyciu istniejących narzędzi lub bibliotek.

tej pory mam te pomysły:

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

ale wszystkie one korzystać z list pośrednie i nie są bardzo zwięzłe.

Najkrótsza jeden znalazłem do tej pory używa półgrup:

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

ale działa tylko dla liczb dodatnich (nie na 0).

Przede wszystkim koncentruję się na rozwiązaniach w Haskell, ale chciałbym także zainteresować się rozwiązaniami Scala lub nawet innymi językami funkcjonalnymi.

Answer 1

Lubię pomysły pigworker w/Tauli jest najlepszy, ale ponieważ tylko dał je jako komentarze, Robię CW odpowiedź z niego.

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

lub

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

może nawet:

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

Answer 2

W Scala:

Function chain Seq.fill(n)(f) 

Zobacz scaladoc for Function. Leniwa wersja: Function chain Stream.fill(n)(f)

Answer 3

Ponieważ Haskell jest pod wpływem matematyki tak bardzo, the definition ze strony Wikipedii, do której link masz prawie bezpośrednio tłumaczy na ten język.

Wystarczy sprawdzić to:

Teraz w Haskell:

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

Całkiem miłe, prawda?

Co to jest? Jest to typowy wzór rekursji. I jak Haskellers zwykle to traktują? Traktujemy to z fałdami! Więc po refactoring możemy skończyć z poniższego tłumaczenia:

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

lub punktu wolne, jeśli wolisz:

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

Jak widać, nie istnieje pojęcie argumentów funkcja podmiotu zarówno w Definicja Wikipedii i przedstawione tutaj rozwiązania. Jest to funkcja na innej funkcji, tj. Funkcja podmiotu jest traktowana jako wartość.Jest to wyższe podejście do problemu niż implementacja z udziałem argumentów funkcji podmiotu.

Teraz, jeśli chodzi o twoje obawy dotyczące list pośrednich. Z perspektywy kodu źródłowego rozwiązanie to jest bardzo podobne do rozwiązania Scala opublikowanego przez @jmcejuela, ale istnieje kluczowa różnica, że ​​optymalizator GHC całkowicie odrzuca listę pośrednią, zamieniając tę ​​funkcję w prostą pętlę rekursywną nad funkcją podmiotu. Nie sądzę, żeby można go było zoptymalizować.

Aby wygodnie sprawdzić wyniki pośredniego kompilatora dla siebie, polecam użyć ghc-core.

Answer 4

Chociaż nie jest to tak zwięzłe jak odpowiedź jmcejueli (którą ja wolę), jest jeszcze inny sposób wyrażenia takiej funkcji w scala bez modułu Function. Działa to także wtedy, gdy n = 0.

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

Aby przezwyciężyć utworzenie listy, można użyć rekurencji, co wyraźnie w odwrocie wymaga wpisywanie bardziej statyczny.

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

Jest równoważne rozwiązanie stosując wzór pasujący jak roztworu w 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)) 
} 

Wreszcie, wolę krótką drogę od pisania w Caml, gdzie nie ma potrzeby definiowania typów ze zmiennych w ogóle.

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