CODEWITHSUNDEEP
listhaskell
peer
peer

Reputation: 4729

Infinite sequence with last

I want to realize a sequence where x_n depends only on x_{n-1} as an infinite list.

next x_k = x_k +1 --get next element

seq1 n = n : seq1 (next n)

seq2 = 0:[next (last seq2)]

seq1 works, seq2 does not.
What exactly happens in seq1?
Is it because last waits forever? If so, how can I see that e.g. last is not good for infinite lists?

Upvotes: 0

Views: 46

Answers (1)

Random Dev
Random Dev

Reputation: 52300

seq1

the only magic here is the fact that the list constructor is of course lazy so seq1 (next n) will be evaluated on demand and you cannot get into trouble

seq2

As you already saw that your sequence will be infinite it makes no sense to ask for the last element of it (using last) - so of course this will enter an infinite loop (while trying to find said last element of an infinite list)

If you want to know the details look at what happens when you want the second element of seq2

remember last is defined like this:

last [x]                =  x
last (_:xs)             =  last xs

next (last seq2)
= last seq2 + 1
= last (0:[next (last seq2)]) + 1
{ as `seq2` = 0:_ only the second case in `last` applies }
= last [next (last seq2)] + 1
        ^^^^^^^^^^^^^^^^
{ now you are basically back at the first step and you enter an infinite loop }

using unfoldr

you can use unfoldr to define this rather easily:

seq3 = unfoldr (\b -> Just (b, next b)) 0

using iterate

as @ReinHeinrichs commented you can also just do

seq3 = iterate next 0

using iterate

indeed iterate is actually implemented just like seq1:

iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

Upvotes: 2

Related Questions