Skip to content

Instantly share code, notes, and snippets.

@plesner
Last active February 9, 2017 02:55
Show Gist options
  • Save plesner/47088aaf68206c9bcc44 to your computer and use it in GitHub Desktop.
Save plesner/47088aaf68206c9bcc44 to your computer and use it in GitHub Desktop.
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