Skip to content

Instantly share code, notes, and snippets.

# plesner/polyenum.hs Last active Feb 9, 2017

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, ...] -- 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
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.