如何简洁地表达函数迭代？

Question

如何表达函数迭代是否有简洁,惯用的方式？也就是说,给定一个号码n和一个功能f :: a -> a,我想表达\x -> f(...(f(x))...),其中f应用n-times.

当然,我可以为此创建自己的递归函数,但是如果有一种方法可以使用现有工具或库快速表达它,我会感兴趣.

到目前为止,我有这些想法:

但他们都使用中间名单,并不是很简洁.

到目前为止我找到的最短的一个使用半群:

但它只适用于正数(不适用于0).

主要是我专注于Haskell中的解决方案,但我也对Scala解决方案甚至其他功能语言感兴趣.

Answer 1

因为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.

Answer 2

在斯卡拉:

Function chain Seq.fill(n)(f)

请参阅scaladoc for Function.懒人版:Function chain Stream.fill(n)(f)

Answer 3

我最喜欢 Pigworker/tauli 的想法，但由于他们只是将其作为评论给出，所以我正在从中做出 CW 答案。

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

或者

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

甚至可能：

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