How to define a list of recursive calls to a function in Haskell

Question

What I would like to do is define a function like this:

[f 0, f f 0, f f f 0, f f f f 0, f f f f f 0..]

Or in other words, where each element is the last element that is run through a function.

I have tried a few times to get this working with ways similar to ways I have seen the Fibonacci sequence in Haskell, by calling the list with the first few elements pre-defined:

fib = 0 : 1 : zipWith (+) fib (tail fib)

ls = 0 : f 0 : f (last ls)

If I define f as a simple addOne function like so:

f = (+ 1)

I get this error:

<interactive>:124:5: error:
* Occurs check: cannot construct the infinite type: a ~ [a]
  Expected type: [[a]]
    Actual type: [a]
* In the expression: 0 : (f 0) : f (last y)
  In an equation for `y': y = 0 : (f 0) : f (last y)
* Relevant bindings include
    y :: [[a]] (bound at <interactive>:124:1)

How do I create a list that functions like this does?

Answer 1

I like your attempt

ls = 0 : f 0 : f (last ls)

These are the problems with it:

• No type signature. Always write type signatures. They are technically speaking optional, but boy do they help to understand what's going on and what you even want.
• You're trying to apply f directly to a list, but it's supposed to operate on list elements. (That's the cause of your error message.)
• last on an infinite list can be no good. Anyways this is not what you want: f should be applied to all elements of the tail instead. That's what map is there for.

So, a correct and complete implementation of that attempt is the following:

iterate' :: (a -> a) -> a -> [a]
 -- altn.:  (Int->Int) -> [Int], without x₀ but always starting from 0
iterate' f x₀ = ls
 where ls = x₀ : f x₀ : map f (tail ls)

N.B. this doesn't actually give [f 0, f (f 0), f (f (f 0)) ..] but starts from 0. To start from f 0, simply remove the standalone x₀:

iterate' f x₀ = ls
 where ls = f x₀ : map f (tail ls)

...which doesn't terminate however (thanks @WillNess), because the tail would now recurse forever. But you don't actually need tail! This is the proper definition:

iterate' f x₀ = ls
 where ls = f x₀ : map f ls

Answer 2

If you want to define this yourself, vs use iterate as pointed out by @WillemVanOnsem, then simple primitive recursion is your friend:

f :: (a -> a) -> a -> [a]
f g x = let new = g x in new `seq` new : f g new

This is similar to iterate except that iterate starts with the element you provide (the first x) instead of the first application of the function:

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

A self-education can be acquired by hoogling for functions of this type and reading the implementation of any search hits found in the base package.