n-term recurrences

[William Lee Irwin III]

-- 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