Menu
I'm thinking of a function like this:
> 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
Note: The code is F# but I tagged the question with haskell, ocaml and ml tags because if the function doesn't exist in F# libraries but it exists in other languages I would like to use the same name
899
Higher order functions are also commonly used to abstract how to operate on different data types. For instance, . filter() doesn't have to operate on arrays of strings. It could just as easily filter numbers, because you can pass in a function that knows how to deal with a different data type.
First, the definition. A higher-order function is a function that either takes a function as an argument, returns a function as its return value, or both.
A function that takes another function as one of its arguments, as every does, is called a higher-order function. If we focus our attention on procedures, the mechanism through which Scheme computes functions, we think of every as a procedure that takes another procedure as an argument—a higher-order procedure.
The functions that use other functions as arguments or return functions are named higher-order functions. In the previous examples, iUseFunction() is higher-order because it accepts a function as an argument. Also iReturnFunction() is a higher-order function because it returns another function.
A function is called Higher Order Function if it contains other functions as a parameter or returns a function as an output i.e, the functions that operate with another function are known as Higher order Functions.
You would have gotten (very close to) an answer by using for example Hayoo (or Hoogle, but Hoogle's not as flexible — iterateN was not found):
a search for Int -> (a -> a) -> a -> a revealed several functions that do what you want but are not part of the stdlib.
a search for applyN returned a function of exactly the same name with the type signature you are looking.
by laxing the return value by searching for Int -> (a -> a) -> a instead (note the missing -> a at the end), you get the iterateN :: Int -> (a -> a) -> a -> Seq a function which erdeszt has already mentioned.
P.S. Hoogle seems to be more capable of flipping around argument order: (a -> a) -> Int -> a -> Seq a successfully returns 'iterateN :: Int -> (a -> a) -> a -> Seq a`, which Hayoo does not.
154
There is an iterateN function for Haskell in the Data.Sequence module that looks like the one you are looking for.
It's actually just a combinaton of iterate + take:
let iterateN n f x = take n (iterate f x)
Here's an F# version of iterate (from here), Seq.take is part of the F# standard library:
let rec iterate f value = seq {
yield value
yield! iterate f (f value) }
A possible solution:
> 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))))
Another (already mentioned):
> iterate f a !! 5
f (f (f (f (f a))))
(add lambdas if you want to turn it into a function)
However, don't forget that Haskell is lazy: the above methods will first build a thunk by applying f many times and only then start evaluating. Sometimes f could be iterated in constant space, e.g. when f :: Int -> Int (and f itself works in constant space), but the above approaches only work in linear space.
I would define by own strict iteration combinator, e.g.:
iter :: Int -> (a -> a) -> a -> a
iter 0 _ x = x
iter n f x = iter (pred n) f $! f x
or even,
iter n f x = foldl' (flip $ const f) x [1..n]
which is more of less the Haskell translation of what was already posted in the question.
Alternatively, we can can define a strict version of iterate (which IMHO should already exist...)
iterate' :: (a -> a) -> a -> [a]
iterate' f x = x : (iterate' f $! f x)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
