views:

205

answers:

3

I know that infinite sequences are possible in Haskell - however, I'm not entirely sure how to generate one

Given a method

generate::Integer->Integer

which take an integer and produces the next integer in the sequence, how would I build an infinite sequence out of this?

+10  A: 

If you want your sequence to start from 1 then it is -

iterate generate 1

Please notice that first letter of function is lowercase, not uppercase. Otherwise it would be data type, not function.

//edit: I just realized not just data types start with capital, it could be data constructor or type class as well, but that wasn't the point. :)

Matajon
+4  A: 

There are several ways to do it, but one is:

gen :: (a -> a) -> a -> [a]
gen f s = s : gen f (f s)

This function takes a functon f and some valus s and returns s, after wich it calls itself with that same f, and the result of f s. Demonstration:

Prelude> :t succ
succ :: (Enum a) => a -> a
Prelude> let gen f s = s : gen f (f s)
Prelude> take 10 $ gen succ 3
[3,4,5,6,7,8,9,10,11,12]

In the above example succ acts as the function generate :: Integer -> Integer which you mention. But observe that gen will work with any function of type a -> a.

Edit: and indeed, gen is identical to the function iterate from the Prelude (and Data.List).

Stephan202
+9  A: 

Adding to Matajon's answer: a way to discover the iterate function other than asking here would be to use Hoogle.

Hoogle's first answer for the query (a -> a) -> [a] is iterate.

yairchu
+1 for spreading Hoogle awareness.
Mike B
+1 for introducing me to Hoogle :D
Martin