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

Question

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?

Answer 1

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.

Answer 2

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. :)