是否有一个标准的高阶函数可以多次应用一个变换

Question

我正在考虑这样一个函数:

> let applyN (initial : 't) (n:int) (f : 't -> 't) = seq {1..n} |> Seq.fold (fun s _ -> f s) initial;;
val applyN : initial:'t -> n:int -> f:('t -> 't) -> 't
> applyN 0 10 (fun x -> x + 1);;
val it : int = 10

注意:代码是f#，但我用haskell, ocaml和ml标记的问题，因为如果函数不存在于f#库中，但它存在于其他语言中，我想使用相同的名称

Answer 1

你会得到(非常接近)一个答案通过使用例如Hayoo(或Hoogle，但Hoogle不是灵活的- iterateN未被发现):

• 搜索Int -> (a -> a) -> a -> a，发现有几个函数可以做你想要的，但不是标准库的一部分。

• 搜索applyN返回一个与您正在寻找的类型签名完全相同的名称的函数。

• 通过搜索Int -> (a -> a) -> a来松弛返回值(注意最后缺失的-> a)，您得到了erdeszt已经提到的iterateN :: Int -> (a -> a) -> a -> Seq a函数。

注:Hoogle似乎更有能力改变参数顺序:(a -> a) -> Int -> a -> Seq a成功返回'iterateN:: Int -> (a -> a) -> a -> Seq a '，而Hayoo没有。

Answer 2

在Data中有一个用于Haskell的iterateN函数。序列模块，看起来像一个你正在寻找。

它实际上只是迭代+ take的组合:let iterateN n f x = take n (iterate f x)这是一个f#版本的迭代(从这里)，Seq。take是f#标准库的一部分:

let rec iterate f value = seq { 
   yield value
   yield! iterate f (f value) }

Answer 3

一个可能的解决方案:

> import Data.Monoid
> import Debug.SimpleReflect -- not really needed, just for showing the result
> (appEndo . mconcat . replicate 5 . Endo $ f) a
f (f (f (f (f a))))

另一个(已经提到):

> iterate f a !! 5
f (f (f (f (f a))))

(如果你想把它变成一个函数，可以添加lambdas)

然而，不要忘记Haskell是懒惰的:上面的方法将首先通过多次应用f来构建一个思想库，然后才开始计算。有时f可以在常数空间中迭代，例如当f :: Int -> Int(和f本身在常数空间中工作)，但上述方法只在线性空间中工作。

我将定义自己的严格迭代组合子，例如:

iter :: Int -> (a -> a) -> a -> a
iter 0 _ x = x
iter n f x = iter (pred n) f $! f x

,

iter n f x = foldl' (flip $ const f) x [1..n]

差不多就是问题中已经发布的Haskell翻译。

或者，我们可以定义一个严格版本的iterate (IMHO应该已经存在了…)

iterate' :: (a -> a) -> a -> [a]
iterate' f x = x : (iterate' f $! f x)

Answer 4

要添加其他方法，

import Control.Monad.State.Lazy
applyN initial n =
  flip execState initial . replicateM_ n . modify