6

I want to define an infinite list where each element is a function of all the previous elements.

So, the n+1th element of the list would be f [x1, x2, ..., xn].

This seems simple, but I cannot seem to get my head around how to do it. Can anyone help?

Cameron Martin
  • 5,952
  • 2
  • 40
  • 53
  • By chance, I just wrote [an answer to another question](http://stackoverflow.com/a/28101516/791604) that does just that. – Daniel Wagner Feb 02 '15 at 21:03

3 Answers3

11
gen f = xs where xs = map f $ inits xs

Or

gen f = fix $ map f . inits
effectfully
  • 12,325
  • 2
  • 17
  • 40
4

As an alternative to the other answer, hopefully a little more readable but less laconic:

-- "heads f" will generate all of the the prefixes of the inflist
heads f = map ( (flip take) (inflist f) ) [1..]
-- inflist will generate the infinite list
inflist f = ( f [] ) : map f (heads f)

-- test function
sum1 s = 1 + sum s

-- test run
>> take 5 (inflist sum1)
[1,2,4,8,16]

Upd: As pointed above the heads function can be replaced with inits, which I wasn't aware of it's existence.

Eugene Sh.
  • 17,802
  • 8
  • 40
  • 61
  • 1
    Note that in versions of GHC before 7.8.4, `inits` is incredibly slow, so your version would be better. In 7.8.4 and above, `inits` works well. – dfeuer Feb 03 '15 at 16:07
2

You can use unfoldr:

import Data.List

gen :: ([a] -> a) -> a -> [a]
gen f init = unfoldr (\l -> let n = f (reverse l) in (Just (n, n:l))) [init]

note this has to reverse the input list each time. You could use Data.Sequence instead:

import Data.Sequence

genSeq :: (Seq a -> a) -> a -> Seq a
genSeq f init = unfoldr (\s -> let n = f s in (Just (n, s |> n))) (singleton init)
Lee
  • 142,018
  • 20
  • 234
  • 287