Polynomial range function in haskell

polyenum.hs

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