Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.