CODEWITHSUNDEEP
haskell
hdgarrood
hdgarrood

Reputation: 2151

Haskell: turning a non-infinite list into an infinite one + laziness (euler 391)

I've written the following Haskell code to produce a list where the nth element is the number of 1s in writing 1..n as binary numbers (it's related to euler 391, incidentally):

buildList :: a -> (a -> a) -> [a]
buildList start f = start : buildList (f start) f

differences :: [[Int]]
differences = buildList [0] (\x -> x ++ map (+1) x)

sequenceK' :: Int -> [Int]
sequenceK' n = tail $ scanl (+) 0 (last $ take n differences)

which results in sequenceK' n giving a list of 2^(n-1) elements.

This question has two parts:

a) Why does the time taken to compute head $ sequenceK' n increase with n? -- due to ghc's laziness, I would expect the time to remain more or less constant.

b) Is it possible to define an infinite version of this list so that I can do things like take and takeWhile without having to worry about the value of the parameter passed to sequenceK'?

Upvotes: 3

Views: 228

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

a) Because you're calling last $ take n differences, which has to do more work the bigger n is.

b) Yep, it's possible. The least-thinking solution is to just take the earliest element we see at each particular depth:

*Main> take 20 . map head . transpose $ differences
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3]

The better solution is to generate only the meaningful bits. We can do this by observing the following equality:

differences' = 1 : (differences' >>= \x -> [x, x+1])

Actually, this is slightly off, as you can probably guess:

*Main> take 20 differences'
[1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3]

But it's easily fixed by just tacking a 0 on front.

Upvotes: 5

Related Questions