Polynomial range function in haskell
-- Given a list of values, returns a list of the differences between | |
-- neighbouring pairs of values. | |
nextLevelDiffs (a:b:rest) = (b - a):(nextLevelDiffs (b:rest)) | |
nextLevelDiffs _ = [] | |
-- Given a list of values, returns a list of the differences such that the | |
-- first element is the 0-level differences, the second the 1-level and so | |
-- on. | |
nLevelDiffs [] = [] | |
nLevelDiffs elms = elms:(nLevelDiffs (nextLevelDiffs elms)) | |
-- Returns a list of the last values in the n-order differences for the given | |
-- values. The first element is the last value of the 0-order differences, the | |
-- second the last of the 1-order differences, and so on. | |
diffSlice values = map last (nLevelDiffs values) | |
-- Given a diff slice, returns the next one in the sequence. | |
advanceDiffSlice slice = | |
let accumulateLeft a (b:rest) = (a+b):(b:rest) | |
accumulateLeft a [] = [a] | |
in foldr accumulateLeft [] slice | |
-- Given a difference slice returns the infinitel list produced by repeatedly | |
-- advancing the slice by adding together the values. | |
expandSlice (a:rest) = a:(expandSlice (advanceDiffSlice (a:rest))) | |
-- Given a finite list of elements, returns a list starting with the same | |
-- elements and then continuing infinitely with the elements generated from | |
-- the initial ones using successive n-order differences. If we call the | |
-- length of the input n, the i'th entry in the result will be the result of | |
-- f(i) where f is the unique polynomial of rank at most n where the first n | |
-- values are equal to the elements of the input series. | |
-- | |
-- For instance | |
-- | |
-- polyEnumFrom [10] -> [10, 10, 10, 10, ...] | |
-- polyEnumFrom [0, 1] -> [0, 1, 2, 3, 4, 5, 6, ...] | |
-- polyEnumFrom [4, 6] -> [4, 6, 8, 10, 12, ...] | |
-- polyEnumFrom [10, 9] -> [10, 9, 8, 7, 6, 5, ...] | |
-- polyEnumFrom [0, 1, 4] -> [0, 1, 4, 9, 16, 25, 36, ...] | |
-- | |
polyEnumFrom elms = | |
let expansion = expandSlice (advanceDiffSlice (diffSlice elms)) | |
in elms ++ expansion | |
-- Given an infinite sequence, returns the part of it up to the given last | |
-- element. This is defined as: if the sequence is non-decreasing then it's | |
-- the values less than the last, if it's non-increasing then it's the values | |
-- greater than the last. If it's constant then there is no limit. Note that | |
-- this makes the limit function funky for non-monotone sequences since as | |
-- soon as it grows away from the limit it stops. | |
filterGrowthLimit (a:b:rest) last = | |
if (a <= b && a <= last) || (b <= a && last <= a) | |
then a:(filterGrowthLimit (b:rest) last) | |
else [] | |
-- Similar to haskell's range syntax [first, second .. last] but works with an | |
-- arbitrary number of first values, using polyExpand to generate the values. | |
polyEnumFromThenTo [f] last = polyEnumFromThenTo [f, succ f] last | |
polyEnumFromThenTo init last = filterGrowthLimit (polyEnumFrom init) last | |
filterBounds (a:rest) min max = | |
if min <= a && a <= max | |
then a:(filterBounds rest min max) | |
else [] | |
-- Similar to polyRange but given an explicit upper and lower limit. This makes | |
-- more sense for non-monotone sequences. | |
polyEnumFromThenBetween [f] min max = polyEnumFromThenBetween [f, succ f] min max | |
polyEnumFromThenBetween init min max = filterBounds (polyEnumFrom init) min max |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment