Generating an infinite sequence in Haskell

Question

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?

Martin Jonáš · Accepted Answer · 2009-11-23T19:27:33.900

14

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. :)

edited Nov 23 '09 at 19:27

answered Nov 23 '09 at 19:12

Martin Jonáš

2,309
15
12

yairchu · Answer 2 · 2023-02-26T19:20:57.517

13

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.

Update (2023): Hoogle's scoring appears to have changed and iterate is no longer given with this query. It's full type has another a parameter and with the full type it is given in the results.

edited Feb 26 '23 at 19:20

answered Nov 23 '09 at 19:27

yairchu

23,680
7
69
109

I'm confused. iterate is not in Hoogle's list now. I just clicked on the link and I couldn't find it. What do I miss here? – Arpad Horvath -- Слава Україні Feb 25 '23 at 17:30
1

@ArpadHorvath--СлаваУкраїні It appears than since 2009 Hoogle's scoring function changed. The full type for iterate has an additional "a -> " and with that query it does give iterate as of now. – yairchu Feb 26 '23 at 19:19

score 7 · Answer 3 · answered Nov 23 '09 at 19:15

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).

Generating an infinite sequence in Haskell

3 Answers3