-- coefs starts with constant term, then coef of a(n-k) in k-term -- recurrence and goes up by indices -- vals starts with x0 and goes up by indices -- solves linear recurrences -- where xs !! (n+1) = head coefs + -- sum (zipWith (*) (tail coefs) [xs !! k | k <- [n - length coefs - 1..n]]) -- and the first few terms are given by xs !! n = vals !! n recurrence coefs vals | length coefs /= length vals + 1 = error "mismatched lengths of coefficients and values" | otherwise = vals ++ map coefSum ys where xs = recurrence coefs vals ys = transpose [drop k xs | k <- [0..length coefs - 1]] coefSum xs = head coefs + sum (zipWith (*) (tail coefs) xs) transpose xs = map head xs : transpose (map tail xs) -- This could be used, say, to generate the list of orthonormal -- polynomials generated by a three-term recurrence and then -- expand some function in a function series via Gaussian quadrature. -- e^(-x^2/2)H_n(x) or e^(-x^c/2)L^c_n(x) look especially attractive. -- OTOH that tactic may not be numerically useful, or useful only -- when the function series expansion is known a priori. -- It could also be a fancier way to generate Fibonacci numbers or -- Apery numbers or whatever. -- Not terribly deep, but it amused me for a few minutes to think of it. -- wli