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 深受数学的影响,您链接到的 Wikipedia 页面上的定义几乎直接翻译成该语言。

看看这个:

现在在 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

如您所见,在 Wikipedia 定义和此处提供的解决方案中都没有主题函数参数的概念。它是另一个函数上的函数,即主题函数被视为一个值。这是比涉及主题函数的参数的实现更高级别的问题方法。

现在,关于您对中间列表的担忧。从源代码的角度来看,这个解决方案与@jmcejuela 发布的 Scala 解决方案非常相似,但有一个关键区别是 GHC 优化器完全抛弃了中间列表,将函数变成了主题函数的简单递归循环。我不认为它可以更好地优化。

为了自己方便地检查中间编译器结果,我建议使用ghc-core

于 2013-04-15T11:28:48.403 回答
15

在斯卡拉:

Function chain Seq.fill(n)(f)

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

于 2013-04-15T09:29:47.720 回答
1

虽然这不像 jmcejuela 的回答(我更喜欢)那么简洁,但 scala 中还有另一种方法可以在没有Function模块的情况下表达这样的功能。当 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 ...
于 2013-04-18T12:06:09.523 回答
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 回答