5

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?

Improve this question

4 Answers 4

Reset to default
6

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

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.

Improve this answer

Comments

4

Or roll your own:

fn f a = (f a) : (fn f (f a))

main = print $ take 6 $ fn (5+) 1

Output:

[6,11,16,21,26,31]
Improve this answer

Comments

3

Haskell has already a function for that: iterate :: (a -> a) -> a -> [a]. For example:

Prelude> take 10 (iterate (2*) 1)
[1,2,4,8,16,32,64,128,256,512]

Your question is slightly different since the first element should be f 0, instead of 0, but we can simply apply f to it, or use tail :: [a] -> [a] on the result. For example:

ls :: Num a => (a -> a) -> [a]
ls = tail . flip iterate 0

For example:

Prelude> take 10 (ls (1+))
[1,2,3,4,5,6,7,8,9,10]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.