Sequence :: [Integer]

I thought I should first make sequence [1,2,3,...] and iterate each item to make a sequence of 1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1, ....

How to put this in a Haskell way of code?

CodePudding user response：

Basically here you have subsequences which each time decrement to 1, so:

[1]
[2, 1]
[3, 2, 1]
[4, 3, 2, 1]
⋮

We can thus work with list comprehension and define this as:

[x | b <- [1 ..], x <- …]

where I leave filling in … as an exercise. It should construct a list that starts at b and ends with 1, so b, b-1, b-2, etc.

For the first 20 items, we then get:

[1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,6,5,4,3,2]

or with a monadic function:

[1 ..] >>= \b -> …

which produces the same values:

[1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,6,5,4,3,2]

CodePudding user response：

This is a simple way to do it:

sequence = concatMap (\n -> [n, n-1 .. 1]) [1..]

(note that you can't call it Sequence, as names with an uppercase first letter are reserved for either types or data constructors, not normal values)

I hope this is simple enough to understand. What we do is:

1. take the infinite list of integers [1..]
2. apply to each integer the function \n -> [n, n-1 .. 1] - this is the function which takes eg 2 to [2,1], 5 to [5, 4, 3, 2, 1] and so on
3. use concatMap to apply this function to each element of the list but flatten the resulting list of lists into one. Had you used map instead of concatMap, the result would be [[1], [2, 1], [3, 2, 1], ...] - using concatMap instead is what removes the inner lists.

CodePudding user response：

Simple. Start with what you have:

xs1 = [1]

But that's not the while story of course. You have

xs2 = [1]    [2,1]

but actually

xs4 = [1]    [2,1]    [3,2,1]    [4,3,2,1]

If now you give this to somebody and they check it with e.g. take 7 they won't even see the difference! But of course we want to generalize it, so that take n for any n will see the correct sequence.

What if we write it as

ys4 = [ [i,i-1 .. 1] | i <- [1..4] ]

? To get xs4 from ys4 we just need to apply to it another, common function.

And why should we limit ourselves to just 4? Let's make it a parameter:

ysn n = function [ [i,i-1 .. 1] | i <- [1..n] ]

But do we really need that n?