関数の繰り返しを簡潔に表現するには？

Question

function iterationを簡潔で慣用的に表現する方法はありますか？すなわち、数字nと関数f :: a -> aが与えられていると、\x -> f(...(f(x))...)を表現したいと思います。ここで、fが適用されます。n回。

もちろん、独自の再帰的な関数を作成することもできますが、既存のツールやライブラリを使用してすぐに表現する方法があれば興味があります。

はこれまでのところ、私はこれらのアイデアを持っている：

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

それらはすべて中間のリストを使用し、非常に簡潔ではありません。

私がこれまでに半群を使用した最短1：

、

• \n f -> appEndo . times1p (n - 1) . Endoそれが唯一の正の数について（0ではないため）動作します。

  主に私はHaskellのソリューションに焦点を当てていますが、Scalaソリューションやその他の機能的言語にも興味があります。 Scalaで

Answer 1

私は最高のpigworkerさん/ tauliのアイデアを好きですが、彼らは唯一のコメントとしてそれを与えたことから、私はそれのうちCWの答えを作ってるんです。でも多分

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

または

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

：おそらく、 `iterate`を使用して

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

Answer 2

：

Function chain Seq.fill(n)(f) 

がscaladoc for Functionを参照してください。レイジーバージョン：Function chain Stream.fill(n)(f)

Answer 3

ハスケルは数学の影響をあまり受けないため、リンクしているウィキペディアのページのthe definitionはほとんどの言語に翻訳されます。

ただ、このチェックアウト：

を今Haskellで：

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

はかなりきちんとした、ハァッ？

これはなんですか？これは典型的な再帰パターンです。そしてHaskellersはそれをどう扱うのですか？私たちはそれを折り目で扱います！だから、リファクタリングの後、私たちは以下の翻訳で終わる：

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 

ご覧のとおり、対象の関数の引数の概念は、両方ありませんウィキペディアの定義とここに提示されているソリューションです。それは別の関数上の関数です。つまり、対象関数は値として扱われています。これは、対象関数の引数を含む実装よりも、問題に対する上位レベルのアプローチです。

ここで、中間リストについての心配について。ソースコードの観点からは、このソリューションは@jmcejuelaによって投稿されたScalaソリューションと非常によく似ていますが、GHCオプティマイザが中間リストを完全に破棄して、関数を対象関数の単純な再帰ループに変換するという大きな違いがあります。私はそれが最適化されるとは思わない。

自分で中間コンパイラの結果を快適に調べるには、ghc-coreを使用することをおすすめします。

Answer 4

これはjmcejuelaの答え（私が好む）ほど簡潔ではありませんが、Functionモジュールがないと、scalaにそのような機能を表現する別の方法があります。また、ときの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 ...