How to create a list in a recursive call where the first element needs to be handled differently?

user_3236779 0
Viewed 234

I am learning functional programming using Haskell. I am trying to create a function that takes a function f, and executes the function on some input x, n number of times.

repeat :: (a -> a) -> a -> Int -> [a]
repeat f x n

So, the output list is like this:

[x, f(x), f(f(x)), ..., f^n(x)]

So far I have been able to come up with a function that I believe does this. It performs n times:

fn f a n = f a : fn f (f a) (n-1)

The problem I have now, is that I want the first element of the list to just be x. Right now, it is starting my list off at f(x). I tried playing around, but I'm not sure how to cover this "base" case in Haskell. Could someone lend a hand?

haskell
2 Answers

You apply the function in two places: once in the "simple" first element case and again in the recursion.

fn f a n = f a : fn f (f a) (n-1)
           ^^^         ^^^

If you want the first element to be a, simply remove the first one; you don't need it.

fn f a n = a : fn f (f a) (n-1)

Now we have a working function, but it will run forever. You also need a base case. If we tell a function to repeat zero times, we should get the empty list.

fn _ _ 0 = []
fn f a n = a : fn f (f a) (n-1)

Finally, for readability and by usual Haskell coding standards, we'll want to give this thing a type signature. The most general possible type, which we can query from ghci is

*Main> :t fn
fn :: (Eq t1, Num t1) => (t2 -> t2) -> t2 -> t1 -> [t2]

But it's highly unlikely we're ever going to call this thing with non-Int values, and the extra typeclasses may just confuse the inference engine when trying to call it later, so I recommend

fn :: (a -> a) -> a -> Int -> [a]
fn _ _ 0 = []
fn f a n = a : fn f (f a) (n-1)
user_22886590

I would advise to implement this with two functions: one where we construct an infinite list, so (a -> a) -> a -> [a], and then we can construct a function Int -> [a] -> [a] which takes the first n items. Both functions exist in Haskell's base package. Indeed, the fn function is implemented as iterate :: (a -> a) -> a -> [a] and take :: Int -> [a] -> [a].

We can implement iterate as:

iterate :: (a -> a) -> a -> [a]
iterate f = go
    where go x = x : go (f x)

here x : thus yields x and makes a recursive call with go (f x) so the recursive call will yield f(x), and then f(f(x)), etc.

The take function can be implemented as:

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

Your fn function is then:

fn :: (a -> a) -> a -> Int -> [a]
fn f x n = take n (iterate f x)

Now we thus have two extra utility functions that can be used, not per se for our fn function.

user_675790
Related