Generate list of Ints in Haskell by adding Ints from a pattern list

user_11293826 0
Viewed 308

I'm playing around with Haskell, mostly trying to learn some new techniques to solve problems. Without any real application in mind I came to think about an interesting thing I can't find a satisfying solution to. Maybe someone has any better ideas?

The problem:

Let's say we want to generate a list of Ints using a starting value and a list of Ints, representing the pattern of numbers to be added in the specified order. So the first value is given, then second value should be the starting value plus the first value in the list, the third that value plus the second value of the pattern, and so on. When the pattern ends, it should start over.

For example: Say we have a starting value v and a pattern [x,y], we'd like the list [v,v+x,v+x+y,v+2x+y,v+2x+2y, ...]. In other words, with a two-valued pattern, next value is created by alternatingly adding x and y to the number last calculated.

If the pattern is short enough (2-3 values?), one could generate separate lists:

  • [v,v,v,...]
  • [0,x,x,2x,2x,3x, ...]
  • [0,0,y,y,2y,2y,...]

and then zip them together with addition. However, as soon as the pattern is longer this gets pretty tedious. My best attempt at a solution would be something like this:

generateLstByPattern :: Int -> [Int] -> [Int]
generateLstByPattern v pattern = v : (recGen v pattern)
  where
  recGen :: Int -> [Int] -> [Int]
  recGen lastN (x:[]) = (lastN + x) : (recGen (lastN + x) pattern)
  recGen lastN (x:xs) = (lastN + x) : (recGen (lastN + x) xs)

It works as intended - but I have a feeling there is a bit more elegant Haskell solution somewhere (there almost always is!). What do you think? Maybe a cool list-comprehension? A higher-order function I've forgotten about?

infinite cycle list sum haskell
5 Answers

Separate the concerns. First look a just a list to process once. Get that working, test it. Hint: “going through the list elements with some accumulator” is in general a good fit for a fold.

Then all that's left to is to repeat the list of inputs and feed it into the pass-once function. Conveniently, there's a standard function for that purpose. Just make sure your once-processor is lazy enough to handle the infinite list input.

user_7459030

What you describe is 

foo :: Num a => a -> [a] -> [a]
foo v pattern = scanl (+) v (cycle pattern)

which would normally be written even as just

foo :: Num a => a -> [a] -> [a]
foo v = scanl (+) v . cycle

scanl (+) v xs is the standard way to calculate the partial sums of (v:xs), and cycle is the standard way to repeat a given list cyclically. This is what you describe.

This works for a pattern list of any positive length, as you wanted.

Your way of generating it is inventive, but it's almost too clever for its own good (i.e. it seems overly complicated). It can be expressed with some list comprehensions, as 

foo v pat =
   let   -- the lists, as you describe them:
       lists = repeat v :
               [ replicate i 0 ++
                 [ y | x <- [p, p+p ..]
                     , y <- map (const x) pat ]
                 | (p,i) <- zip pat [1..] ]
   in
     -- OK, so what do we do with that? How do we zipWith
     --   over an arbitrary amount of lists?
     --   with a fold!
     foldr (zipWith (+)) (repeat 0) lists

map (const x) pat is a "clever" way of writing replicate (length pat) x. It can be further shortened to x <$ pat since (<$) x xs == map (const x) xs by definition. It might seem obfuscated, until you've become accustomed to it, and then it seems clear and obvious. :)

user_8498910

Surprised noone's mentioned the silly way yet.

mylist x xs = x : zipWith (+) (mylist x xs) (cycle xs)

(If you squint a bit you can see the connection to scanl answer).

user_112577150

When it is about generating series my first approach would be iterate or unfoldr. iterate is for simple series and unfoldr is for those who carry kind of state but without using any State monad.

In this particular case I think unfoldr is ideal.

series :: Int -> [Int] -> [Int]
series s [x,y] = unfoldr (\(f,s) -> Just (f*x + s*y, (s+1,f))) (s,0)

λ> take 10 $ series 1 [1,1]
[1,2,3,4,5,6,7,8,9,10]

λ> take 10 $ series 3 [1,1]
[3,4,5,6,7,8,9,10,11,12]

λ> take 10 $ series 0 [1,2]
[0,1,3,4,6,7,9,10,12,13]
user_45432070

It is probably better to implement the lists separately, for example the list with x can be implement with:

xseq :: (Enum a, Num a) => a -> [a]
xseq x = 0 : ([x, x+x ..] >>= replicate 2)

Whereas the sequence for y can be implemented as:

yseq :: (Enum a, Num a) => a -> [a]
yseq y = [0,y ..] >>= replicate 2

Then you can use zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] to add the two lists together and add v to it:

mylist :: (Enum a, Num a) => a -> a -> a -> [a]
mylist v x y = zipWith ((+) . (v +)) (xseq x) (yseq y)

So for v = 1, x = 2, and y = 3, we obtain:

Prelude> take 10 (mylist 1 2 3)
[1,3,6,8,11,13,16,18,21,23]

An alternative is to see as pattern that we each time first add x and then y. We thus can make an infinite list [(x+), (y+)], and use scanl :: (b -> a -> b) -> b -> [a] -> [b] to each time apply one of the functions and yield the intermediate result:

mylist :: Num a => a -> a -> a -> [a]
mylist v x y = scanl (flip ($)) v (cycle [(x+), (y+)])

this yields the same result:

Prelude> take 10 $ mylist 1 2 3
[1,3,6,8,11,13,16,18,21,23]

Now the only thing left to do is to generalize this to a list. So for example if the list of additions is given, then you can impelement this as:

mylist :: Num a => [a] -> [a]
mylist v xs = scanl (flip ($)) v (cycle (map (+) xs))

or for a list of functions:

mylist :: Num a => [a -> a] -> [a]
mylist v xs = scanl (flip ($)) v (cycle (xs))
user_675790
Related