Haskell List Generator

Question

I've been working with problems (such as pentagonal numbers) that involve generating a list based on the previous elements in the list. I can't seem to find a built-in function of the form I want. Essentially, I'm looking for a function of the form:

([a] -> a) -> [a] -> [a]

Where ([a] -> a) takes the list so far and yields the next element that should be in the list and a or [a] is the initial list. I tried using iterate to achieve this, but that yields a list of lists, which each successive list having one more element (so to get the 3000th element I have to do (list !! 3000) !! 3000) instead of list !! 3000.

Answer 1

If the recurrence depends on a constant number of previous terms, then you can define the series using standard corecursion, like with the fibonacci sequence:

-- fibs(0) = 1
-- fibs(1) = 1
-- fibs(n+2) = fibs(n) + fibs(n+1)
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

-- foos(0) = -1
-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : zipWith (+) foos 
                        (zipWith (+) 
                            (map (negate 2 *) (tail foos)) 
                            (tail $ tail foos))

Although you can introduce some custom functions to make the syntax a little nicer

(#) = flip drop
infixl 7 #
zipMinus = zipWith (-)
zipPlus  = zipWith (+)

-- foos(1) = 0
-- foos(2) = 1
-- foos(n+3) = foos(n) - 2*foos(n+1) + foos(n+2)
foos = -1 : 0 : 1 : ( ( foos # 0  `zipMinus` ((2*) <$> foos # 1) )
                                  `zipPlus`  foos # 2 )

However, if the number of terms varies, then you'll need a different approach.

For example, consider p(n), the number of ways in which a given positive integer can be expressed as a sum of positive integers.

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - ...

We can define this more simply as

p(n) = ∑ _{k ∈ [1,n)} q(k) p(n-k)

Where

-- q( i ) | i == (3k^2+5k)/2 = (-1) ^ k
--        | i == (3k^2+7k+2)/2 = (-1) ^ k
--        | otherwise         = 0
q = go id 1
  where go zs c = zs . zs . (c:) . zs . (c:) $ go ((0:) . zs) (negate c)

 ghci> take 15 $ zip [1..] q
 [(1,1),(2,1),(3,0),(4,0),(5,-1),(6,0),(7,-1),(8,0),(9,0),(10,0),(11,0),(12,1),
  (13,0),(14,0),(15,1)]

Then we could use iterate to define p:

 p = map head $ iterate next [1]
   where next xs = sum (zipWith (*) q xs) : xs

Note how iterate next creates a series of reversed prefixes of p to make it easy to use q to calculate the next element of p. We then take the head element of each of these reversed prefixes to find p.

ghci> next [1]
[1,1]
ghci> next it
[2,1,1]
ghci> next it
[3,2,1,1]
ghci> next it
[5,3,2,1,1]
ghci> next it
[7,5,3,2,1,1]
ghci> next it
[11,7,5,3,2,1,1]
ghci> next it
[15,11,7,5,3,2,1,1]
ghci> next it
[22,15,11,7,5,3,2,1,1]

Abstracting this out to a pattern, we can get the function you were looking for:

construct :: ([a] -> a) -> [a] -> [a]
construct f = map head . iterate (\as -> f as : as)

p = construct (sum . zipWith (*) q) [1]

Alternately, we could do this in the standard corecursive style if we define a helper function to generate the reversed prefixes of a list:

rInits :: [a] -> [[a]]
rInits = scanl (flip (:)) []

p = 1 : map (sum . zipWith (*) q) (tail $ rInits p)