Haskell List Generator -

i've been working problems (such pentagonal numbers) involve generating list based on previous elements in list. can't seem find built-in function of form want. essentially, i'm looking function of form:

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

where ([a] -> a) takes list far , yields next element should in list , a or [a] initial list. tried using iterate achieve this, yields list of lists, each successive list having 1 more element (so 3000th element have (list !! 3000) !! 3000) instead of list !! 3000.

if recurrence depends on constant number of previous terms, can define series using standard corecursion, 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 can introduce custom functions make syntax 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 number of terms varies, you'll need different approach.

for example, consider p(n), number of ways in given positive integer can expressed 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 more

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

where

-- q( ) | == (3k^2+5k)/2 = (-1) ^ k --        | == (3k^2+7k+2)/2 = (-1) ^ k --        | otherwise         = 0 q = go id 1   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 use iterate define p:

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

note how iterate next creates series of reversed prefixes of p make easy use q calculate next element of p. take head element of each of these reversed prefixes find p.

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

abstracting out pattern, can function looking for:

construct :: ([a] -> a) -> [a] -> [a] construct f = map head . iterate (\as -> f : as)  p = construct (sum . zipwith (*) q) [1] 

alternately, in standard corecursive style if define helper function generate reversed prefixes of list:

rinits :: [a] -> [[a]] rinits = scanl (flip (:)) []  p = 1 : map (sum . zipwith (*) q) (tail $ rinits p)