22

関数の反復 を表現する簡潔で慣用的な方法はありますか? つまり、数値nと関数が与えられたとき、どこに何倍が適用されるかf :: a -> aを表現したいのです。\x -> f(...(f(x))...)fn

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

これまでのところ、次のようなアイデアがあります。

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

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

これまでに見つけた最短のものはセミグループを使用しています:

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

ただし、正の数に対してのみ機能します (0 に対しては機能しません)。

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

4

4 に答える 4

23

Haskell は数学の影響を大きく受けているため、リンク先のウィキペディアのページの定義はほぼそのまま言語に翻訳されます。

これをチェックしてください：

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を使用することをお勧めします。

于 2013-04-15T11:28:48.403 に答える
15

スカラの場合:

Function chain Seq.fill(n)(f)

Function については scaladoc を参照してください。怠惰なバージョン:Function chain Stream.fill(n)(f)

于 2013-04-15T09:29:47.720 に答える
1

私は pigworker/tauli のアイデアが一番好きですが、彼らはコメントとしてのみ提供したので、それから CW の回答を作成しています。 

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

また

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

おそらくさえ：

\n -> ((!! n) .) . iterate
于 2013-05-02T09:12:45.867 に答える