-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Rivers are like Streams, but different.
--
-- This library intends to unify, classify, demonstrate, and promote the
-- use, abuse, and exploration of Streams and other infinite (co)data
-- types. Many other languages have substantial feature overlap with
-- Haskell, but Streams and friends proivde excellent demonstrations of
-- Haskell features like laziness.
--
-- Rivers are not currently defined in this package, because they are
-- still ill-defined. The goal of this package in the meantime is,
-- therefore, is to focus on Streams.
--
-- Another goal of this package is to demonstrate the ecosystem of Rivers
-- (and Streams), how identical (and indeed sometimes isomorphic) streams
-- can be constucted in many different ways. OEIS
-- (http://www.oeis.org) is used to verify the correctness of
-- numeric streams, where possible.
@package rivers
@version 0.1.0
-- | Adds a few useful operators/functions to |Num|.
module Data.Rivers.NumExt
class (Num a, Ord a) => NumExt a
(/, ^) :: NumExt a => a -> a -> a
fact :: NumExt a => a -> a
fall, choose :: NumExt a => a -> a -> a
instance (NumExt a, Integral a) => NumExt (Ratio a)
instance NumExt Integer
module Data.Rivers.Idiom
class Idiom f
pure :: Idiom f => a -> f a
srepeat :: Idiom f => a -> f a
(<>) :: Idiom f => f (a -> b) -> f a -> f b
smap :: Idiom f => (a -> b) -> f a -> f b
zip :: Idiom f => (a -> b -> c) -> f a -> f b -> f c
-- | My module for streams
module Data.Rivers.Streams
-- | Your standard Streams, renamed to S because S
-- looks like a meandering stream.
data S v
Cons :: v -> (S v) -> S v
(<||) :: a -> S a -> S a
(<<|) :: [a] -> S a -> S a
(|~|) :: S a -> S a -> S a
ago :: Integer -> S a -> a
anyA :: S a
z0 :: Num a => S a
asum :: Num a => S a -> S a
bsum :: Num a => S a -> S a
csum :: Num a => S a -> S a
diff :: Num a => S a -> S a
inv :: Num a => S a -> S a
sconst :: Num a => a -> S a
times :: Num a => a -> S a -> S a
plus :: Num a => S a -> S a -> S a
interleave :: S a -> S a -> S a
interleave' :: S a -> S a -> S a
alternate :: S a -> S a -> S a
combStreams :: [[a]] -> [[a]]
drop0L :: S a -> S a
dropIp1L :: S a -> S a
dup :: S a -> S a
(|!|) :: Ord a => S a -> S a -> S a
merge :: Ord a => S a -> S a -> S a
union :: Ord a => S a -> S a -> S a
allEqual :: Eq a => [a] -> Bool
group :: Eq a => S a -> S [a]
fix :: (a -> a) -> a
inits :: S a -> S [a]
interleave3 :: S a -> S a -> S a
intersperse :: a -> S a -> S a
map1 :: (a -> b) -> S a -> S b
mapAdjacent :: (a -> a -> b) -> [a] -> [b]
turn :: Integral a => a -> [a]
-- | A generating function for Streams.
type G v o = [v] -> o
fromFG :: G a a -> S a
revFix :: G a a -> S a
rgen :: G a b -> S a -> S b
fwdFix :: G a a -> S a
grow :: G a b -> S a -> S b
hOfFG :: G a b -> b
tOfFG :: G a b -> a -> G a b
rep :: (S a -> S b) -> G a b
rgen' :: G a b -> [a] -> S a -> S b
hOfRG :: (G a b, [a]) -> b
tOfRG :: (G a b, [a]) -> a -> (G a b, [a])
fromRG :: (G a a, [a]) -> S a
toT :: G a b -> Tree a b
toG :: Tree a b -> G a b
-- | An infinite Tree. Used to represent Streams
data Tree a o
Node :: o -> (a -> Tree a o) -> Tree a o
branches :: Tree a b -> a -> Tree a b
fromT :: Tree a a -> S a
label :: Tree a b -> b
-- | Your standard Co-Algebra (dual to Algebra).
type Coalg c a b = (c -> b, c -> a -> c)
unfold :: Coalg c a b -> c -> Tree a b
cfix :: Coalg c a a -> c -> S a
groW :: Coalg c a b -> c -> S a -> S b
sMap :: (a -> b) -> S a -> S b
sMap2 :: (a -> b -> c) -> S a -> S b -> S c
sMap3 :: (a -> b -> c -> d) -> S a -> S b -> S c -> S d
sMap4 :: (a -> b -> c -> d -> e) -> S a -> S b -> S c -> S d -> S e
sEven :: S a -> S a
seven :: S a -> S a
sOdd :: S a -> S a
sodd :: S a -> S a
sbreak :: (a -> Bool) -> S a -> ([a], S a)
sdropWhile :: (a -> Bool) -> S a -> S a
stakeWhile :: (a -> Bool) -> S a -> [a]
sfilter :: (a -> Bool) -> S a -> S a
spartition :: (a -> Bool) -> S a -> (S a, S a)
sspan :: (a -> Bool) -> S a -> ([a], S a)
scan :: (a -> b -> a) -> a -> S b -> S a
scan' :: (a -> b -> a) -> a -> S b -> S a
scan1 :: (a -> a -> a) -> S a -> S a
scan1' :: (a -> a -> a) -> S a -> S a
scycle :: [a] -> S a
siterate :: (a -> a) -> a -> S a
shead :: S a -> a
stail :: S a -> S a
tail2 :: S a -> S a
tails :: S a -> S (S a)
stake :: Integer -> S a -> [a]
sdrop :: Int -> S a -> S a
ssplitAt :: Int -> S a -> ([a], S a)
smerge :: S a -> S a -> S a
sunzip :: S (a, b) -> (S a, S b)
szipWith :: (a -> b -> c) -> S a -> S b -> S c
transpose :: S (S a) -> S (S a)
fromJust :: Maybe a -> a
fromOEIS :: String -> [Integer]
-- | unzip, specialized to Stream tuples
--
-- filter p xs, removes any elements from
-- xs that do not satisfy p.
--
-- Beware: this function may diverge if there is no element of
-- xs that satisfies p, e.g. filter odd (repeat
-- 0) will loop.
--
-- takeWhile p xs returns the longest prefix of
-- the stream xs for which the predicate p holds.
--
-- dropWhile p xs returns the suffix remaining
-- after takeWhile p xs.
--
-- Beware: this function may diverge if every element of
-- xs satisfies p, e.g. dropWhile even (repeat
-- 0) will loop.
--
-- sspan p xs returns the longest prefix of
-- xs that satisfies p, together with the remainder of
-- the stream.
--
-- The break p function is equivalent to span
-- not . p.
--
-- The splitAt function takes an integer n and a stream
-- xs and returns a pair consisting of the prefix of xs
-- of length n and the remaining stream immediately following
-- this prefix.
--
-- Beware: passing a negative integer as the first argument will
-- cause an error.
--
-- The partition function takes a predicate p and a
-- stream xs, and returns a pair of streams. The first stream
-- corresponds to the elements of xs for which p holds;
-- the second stream corresponds to the elements of xs for which
-- p does not hold.
--
-- Beware: One of the elements of the tuple may be undefined. For
-- example, fst (partition even (repeat 0)) == repeat 0; on the
-- other hand snd (partition even (repeat 0)) is undefined.
--
-- The group function takes a stream and returns a stream of lists
-- such that flattening the resulting stream is equal to the argument.
-- Moreover, each sublist in the resulting stream contains only equal
-- elements. For example,
--
-- drop n xs drops the first n elements
-- off the front of the sequence xs.
--
-- Beware: passing a negative integer as the first argument will
-- cause an error.
--
-- The stails function takes a stream xs and returns
-- all the suffixes of xs.
--
-- merge, version 2 [Hinze UFP p.35]
--
-- map, version 1 | map, version 2 | map2, really zip?
--
-- from Unique Fixed Point p.35
--
-- union for streams
--
-- Interleave two Streams xs and ys, alternating
-- elements from each list.
--
--
-- [x1,x2,...] `interleave` [y1,y2,...] == [x1,y1,x2,y2,...]
--
--
-- intersperse y xs creates an alternating
-- stream of elements from xs and y.
--
-- infix prepend
--
-- turn something
--
-- cycle xs returns the infinite repetition of
-- xs:
--
--
-- cycle [1,2,3] = Cons 1 (Cons 2 (Cons 3 (Cons 1 (Cons 2 ...
--
--
-- Arithmatic, Jumping, ...
--
-- multiplication | stream inversion | finite (forward) difference |
-- duplicate the head of the stream | even (indexed) elements | odd
-- (indexed) elements | even (indexed) elements, v2 | odd (indexed)
-- elements, v2 | drop function, results in (4*n - 1) | drop function,
-- results in (2*n) | an alternative tail function
--
-- a kind of sum function | right inverse of diff
--
-- from Hinze UFP p.45
--
-- from Hinze UFP p.49
--
-- from Hinze UFP p.4
--
-- iterate (inductively) over a stream
--
-- this can't be stopped?
--
-- from Hinze UFP p.39
--
-- from Hinze UFP p.41
--
-- 2D operator?
--
-- from Hinze UFP p.45
--
-- from Hinze UFP p.45
--
-- mutually recursive
--
-- from Hinze UFP p.45
--
-- from Hinze UFP p.45
--
--
-- scan f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
--
--
-- scan' is a strict scan.
--
-- scan1 is a variant of scan that has no starting value
-- argument:
--
--
-- scan1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
--
--
-- scan1' is a strict scan that has no starting value.
--
-- transpose computes the transposition of a stream of streams.
--
-- from Hinze UFP p.45
--
-- from Hinze UFP p.45
--
-- standard fix-point function | standard fix-point function, specialized
-- to Streams (forward ordering) | standard fix-point function,
-- specialized to Streams (reverse ordering)
--
-- transform a generator to a Stream operator | transform a generator to
-- a Stream operator - v2? | transform a Stream operator to a generator |
-- transform a generator, along with a reversed list, into a Stream
-- operator
--
-- smart constructor for Tree labels | smart constructor for Tree
-- branches | translate a Tree to a Generator | translate a Generator to
-- a Tree | translate a Tree element to a Stream element | translate a
-- Generator element to a Stream element | fromFG helper function (head)
-- | fromFG helper function (tail) | fromRG: translate a Generator (and a
-- reversed list) to a Stream element | fromRG helper function (head) |
-- fromRG helper function (tail)
--
-- unfold operator, specialized to Co-Algebras | standard fix-point
-- function, specialized to Co-Algebras | generate a Stream operator,
-- given a Co-Algebra
--
-- utility function to lookup sequence in OEIS | utility function to
-- check of all elements of a list are equal | utility function to unwrap
-- a (known good) Maybe | utility function to map over adjacent elements
-- in a list
--
-- Power Series Glasses
--
-- Horner's Rule on Streams
--
-- s = sconst (shead t) + (z |*| stail s)
--
-- implies
--
-- z |*| s = 0 <|| s
main :: IO ()
instance Eq v => Eq (S v)
instance Ord v => Ord (S v)
instance Show v => Show (S v)
instance Read v => Read (S v)
instance Fractional a => Fractional (S a)
instance Integral a => Integral (S a)
instance Real a => Real (S a)
instance Enum a => Enum (S a)
instance Num a => Num (S a)
instance Idiom S
instance Serial a => Serial (S a)
instance CoArbitrary a => CoArbitrary (S a)
instance Arbitrary a => Arbitrary (S a)
instance Monad S
instance Functor S
-- | This module is an attempt to construct many and varied examples of
-- Rivers and Streams. At the moment, the concept of what
-- Rivers are (or are not) is not entirely clear in the mind of
-- any particular person on Earth, myself foremost amoung the befuddled.
--
-- Primarily because I lay claim to inventing the idea, this is a
-- worrisome situation. Nevertheless, whatever these things are, regular
-- old Data.Stream streams (and kin) are subsets (or sub-classes,
-- or.. sub-something) of these things, and hence they must qualify to be
-- mapped in this ecosystem (by definition).
--
-- As of now, these example originate primarily from three excellent
-- papers on Streams and their properties. More precisey, they originate
-- from my haphazard and occasionally mindless transcription of what I
-- saw from these documents. Therefore, the authors of the following
-- papers deserve much of the credit, but bear none of the
-- responsibility of the contents of this module.
--
--
--
--
--
--
--
--
--
--
--
--
--
-- This module should clearly document the behavior of all
-- functions. In fact, the code in this module is generally not intended
-- to be imported and used directly. Instead the purpose of this module
-- is to:
--
--
-- - show *many* examples of Streams, especially non-trivial ones (ie,
-- more complicated than fibionacci)
-- - provide visual (and eventually, pictoral) *proof* of equality
-- (insofar that this is possible)
-- - ... more things
-- - ... should go here
-- - ... becuase there's a point to all of this, right?
--
--
-- Note: To accomidate the documentation, the text-width of this document
-- is 129 characters.
--
-- As a witness to the correctness of the examples, I include the result
-- of running doctest:
--
--
-- $ doctest Data/Rivers/Ecology.hs
-- Cases: 74 Tried: 74 Errors: 0 Failures: 0
--
module Data.Rivers.Ecology
-- |
-- >>> stake 30 $ sZero
-- [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
--
sZero :: S Integer
-- |
-- >>> stake 30 $ fwdFix gZero
-- [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
--
gZero :: G Integer Integer
-- |
-- >>> stake 30 $ revFix rZero
-- [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
--
rZero :: G Integer Integer
-- |
-- >>> stake 30 $ cZero
-- [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
--
cZero :: S Integer
cZeroH :: Num a => ([a], Int) -> a
cZeroT :: Num t => ([a], t) -> a -> ([a], t)
-- | Believe it or not, this is in OEIS:
--
--
-- >>> take 30 $ fromOEIS "A000012"
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
--
--
-- >>> stake 30 $ sOne
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
sOne :: S Integer
-- |
-- >>> stake 30 $ sOnes
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
sOnes :: S Integer
gOne :: G Integer Integer
-- |
-- >>> stake 30 $ fwdFix gOne
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
gOne' :: G Integer Integer
-- |
-- >>> stake 30 $ revFix rOne
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
rOne :: G Integer Integer
-- |
-- >>> stake 30 $ cOne
-- [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
--
cOne :: S Integer
cOneH :: t -> t
cOneT :: t -> t -> t
-- |
-- >>> take 30 $ fromOEIS "A000027"
-- [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
--
--
--
-- >>> stake 30 $ sNat
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
sNat :: S Integer
-- |
-- >>> stake 30 $ siterate (+1) 0
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
sNatIt :: S Integer
-- |
-- >>> stake 30 $ natnat
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
natnat :: S Integer
gNat :: G Integer Integer
-- |
-- >>> stake 30 $ fwdFix gNat
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
gNat' :: [a] -> Int
-- |
-- >>> stake 30 $ revFix rNat
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
rNat :: G Integer Integer
-- |
-- >>> stake 30 $ cNat
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
cNat :: S Integer
cNatH :: t -> t
cNatT :: Num a => a -> t -> a
-- |
-- >>> stake 30 $ bin
-- [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
bin :: S Integer
-- |
-- >>> take 15 $ fromOEIS "A122803"
-- [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
--
--
--
-- >>> stake 15 $ revPowersOfN2
-- [1,-2,4,-8,16,-32,64,-128,256,-512,1024,-2048,4096,-8192,16384]
--
revPowersOfN2 :: S Integer
a122803 :: G Integer Integer
-- |
-- >>> stake 15 $ pot
-- [True,True,False,True,False,False,False,True,False,False,False,False,False,False,False]
--
pot :: S Bool
-- |
-- >>> take 15 $ fromOEIS "A000244"
-- [1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969]
--
--
--
-- >>> stake 15 $ revPowersOf3
-- [1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969]
--
revPowersOf3 :: S Integer
pothree :: G Integer Integer
-- |
-- >>> take 30 $ fromOEIS "A000290"
-- [0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841]
--
--
--
-- >>> stake 30 $ bsum $ 2 * sNat + 1
-- [0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841]
--
a000290 :: S Integer
-- |
-- >>> take 10 $ fromOEIS "A000142"
-- [1,1,2,6,24,120,720,5040,40320,362880]
--
--
--
-- >>> stake 10 $ sFac
-- [1,1,2,6,24,120,720,5040,40320,362880]
--
sFac :: S Integer
-- |
-- >>> take 29 $ fromOEIS "A000045"
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
--
--
-- >>> stake 29 $ sFib
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
sFib :: S Integer
-- |
-- >>> stake 29 $ sFib2
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
sFib2 :: S Integer
-- |
-- >>> stake 29 $ revFix revGfibs
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
revGfibs :: G Integer Integer
cFib :: S Integer
cFibH :: (a, b) -> a
-- |
-- >>> stake 29 $ cFib
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
cFibT :: Num a => (a, a) -> a -> (a, a)
-- |
-- >>> stake 29 $ fwdFix gFibs
-- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811]
--
gFibs :: G Integer Integer
-- |
-- >>> take 28 $ fromOEIS "A000032"
-- [2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,15127,24476,39603,64079,103682,167761,271443,439204]
--
--
--
-- >>> stake 28 $ sLucas
-- [2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,15127,24476,39603,64079,103682,167761,271443,439204]
--
sLucas :: S Integer
-- |
-- >>> stake 28 $ revFix rLucas
-- [2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,15127,24476,39603,64079,103682,167761,271443,439204]
--
rLucas :: G Integer Integer
-- | The Fibionacci (4n + 1) and Lucas (4n + 1) numbers
--
-- drop0L is evidently a bisect twice function
--
--
-- >>> stake 10 $ drop0L sFib
-- [1,5,34,233,1597,10946,75025,514229,3524578,24157817]
--
--
--
-- >>> take 10 $ fromOEIS "A033889"
-- [1,5,34,233,1597,10946,75025,514229,3524578,24157817]
--
fib4np1 :: S Integer
-- |
-- >>> stake 10 $ drop0L sLucas
-- [1,11,76,521,3571,24476,167761,1149851,7881196,54018521]
--
--
--
-- >>> take 10 $ fromOEIS "A056914"
-- [1,11,76,521,3571,24476,167761,1149851,7881196,54018521]
--
luc4np1 :: S Integer
-- | The Fib (2*n) and Lucas (2*n) numbers
--
-- dromIp1L is evidently a bisect function
--
--
-- >>> stake 20 $ dropIp1L sFib
-- [0,1,3,8,21,55,144,377,987,2584,6765,17711,46368,121393,317811,832040,2178309,5702887,14930352,39088169]
--
--
--
-- >>> take 20 $ fromOEIS "A001906"
-- [0,1,3,8,21,55,144,377,987,2584,6765,17711,46368,121393,317811,832040,2178309,5702887,14930352,39088169]
--
fib2n :: S Integer
-- |
-- >>> stake 20 $ dropIp1L sLucas
-- [2,3,7,18,47,123,322,843,2207,5778,15127,39603,103682,271443,710647,1860498,4870847,12752043,33385282,87403803]
--
--
--
-- >>> take 20 $ fromOEIS "A005248"
-- [2,3,7,18,47,123,322,843,2207,5778,15127,39603,103682,271443,710647,1860498,4870847,12752043,33385282,87403803]
--
luc2n :: S Integer
-- |
-- >>> stake 21 $ [1] <<| plus sFib sFib
-- [1,0,2,2,4,6,10,16,26,42,68,110,178,288,466,754,1220,1974,3194,5168,8362]
--
--
--
-- >>> take 21 $ fromOEIS "A006355"
-- [1,0,2,2,4,6,10,16,26,42,68,110,178,288,466,754,1220,1974,3194,5168,8362]
--
fibpfib :: S Integer
-- |
-- >>> take 20 $ fromOEIS "A039834"
-- [1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]
--
--
--
-- >>> stake 20 $ [1] <<| diff sFib
-- [1,1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]
--
dxFib :: S Integer
-- |
-- >>> take 20 $ fromOEIS "A061084"
-- [1,2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778]
--
--
--
-- >>> stake 20 $ diff sLucas
-- [-1,2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778]
--
dxLucas :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A000931"
-- [1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616]
--
--
--
-- >>> stake 30 $ padovanPP11010
-- [1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616]
--
padovanPP11010 :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A134816"
-- [1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616,816,1081,1432,1897,2513]
--
--
--
-- >>> stake 30 $ padovan
-- [1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616,816,1081,1432,1897,2513]
--
padovan :: S Integer
-- |
-- >>> stake 30 $ revFix rpadovan
-- [1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465,616,816,1081,1432,1897,2513]
--
rpadovan :: G Integer Integer
-- |
-- >>> take 31 $ fromOEIS "A133034"
-- [1,0,1,1,1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265]
--
--
--
-- >>> stake 30 $ diff $ diff $ revFix rpadovan
-- [0,1,-1,1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265]
--
d2xpadovan :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A001608"
-- [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51,68,90,119,158,209,277,367,486,644,853,1130,1497,1983,2627,3480]
--
--
--
-- >>> stake 30 $ perrin
-- [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51,68,90,119,158,209,277,367,486,644,853,1130,1497,1983,2627,3480]
--
perrin :: S Integer
-- |
-- >>> stake 30 $ revFix rperrin
-- [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51,68,90,119,158,209,277,367,486,644,853,1130,1497,1983,2627,3480]
--
rperrin :: G Integer Integer
-- | Generating Function:
--
-- z -------------------- z^2 + 2z - 1
--
--
-- >>> take 20 $ fromOEIS "A000129"
-- [0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,195025,470832,1136689,2744210,6625109]
--
cPell :: S Integer
cPellH :: (a, a) -> a
-- |
-- >>> stake 20 $ cPell
-- [0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,195025,470832,1136689,2744210,6625109]
--
cPellT :: Num a => (a, a) -> a -> (a, a)
-- |
-- >>> stake 20 $ revFix rpell
-- [0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,195025,470832,1136689,2744210,6625109]
--
rpell :: G Integer Integer
-- |
-- >>> take 20 $ fromOEIS "A001045"
-- [0,1,1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,43691,87381,174763]
--
--
--
-- >>> stake 20 $ jacob
-- [0,1,1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,43691,87381,174763]
--
jacob :: S Integer
-- |
-- >>> stake 20 $ revFix rjacob
-- [0,1,1,3,5,11,21,43,85,171,341,683,1365,2731,5461,10923,21845,43691,87381,174763]
--
rjacob :: G Integer Integer
-- |
-- >>> take 20 $ fromOEIS "A014551"
-- [2,1,5,7,17,31,65,127,257,511,1025,2047,4097,8191,16385,32767,65537,131071,262145,524287]
--
--
--
-- >>> stake 20 $ jacobl
-- [2,1,5,7,17,31,65,127,257,511,1025,2047,4097,8191,16385,32767,65537,131071,262145,524287]
--
jacobl :: S Integer
-- |
-- >>> stake 20 $ revFix rjacobl
-- [2,1,5,7,17,31,65,127,257,511,1025,2047,4097,8191,16385,32767,65537,131071,262145,524287]
--
rjacobl :: G Integer Integer
-- |
-- >>> take 30 $ drop 1 $ fromOEIS "A006257"
-- [1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29]
--
--
--
-- >>> stake 30 $ jos
-- [1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29]
--
jos :: S Integer
-- |
-- >>> stake 30 $ josAlt
-- [1,1,3,1,3,5,7,1,3,5,7,9,11,13,15,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29]
--
josAlt :: S Integer
-- |
-- >>> take 30 $ drop 1 $ fromOEIS "A053644"
-- [1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16]
--
--
--
-- >>> stake 30 $ msb
-- [1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16]
--
msb :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A010060"
-- [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
--
--
--
-- >>> stake 30 $ athue
-- [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
--
athue :: S Integer
thue :: S Integer
-- |
-- >>> stake 30 $ thue
-- [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0]
--
thue' :: S Integer
-- |
-- >>> stake 30 $ binlike1
-- [0,1,0,1,2,0,0,1,2,2,4,0,0,0,0,1,2,2,4,2,4,4,8,0,0,0,0,0,0,0]
--
binlike1 :: S Integer
-- |
-- >>> stake 30 $ binlike2
-- [0,1,1,0,1,2,0,2,1,0,2,2,0,4,2,0,1,4,0,2,2,0,2,4,0,4,4,0,2,8]
--
binlike2 :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A000035"
-- [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]
--
--
--
-- >>> stake 30 $ bsum 0 |~| 1
-- [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]
--
lsb :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A011371"
-- [0,0,1,1,3,3,4,4,7,7,8,8,10,10,11,11,15,15,16,16,18,18,19,19,22,22,23,23,25,25]
--
--
--
-- >>> stake 30 $ sumcarry
-- [0,0,1,1,3,3,4,4,7,7,8,8,10,10,11,11,15,15,16,16,18,18,19,19,22,22,23,23,25,25]
--
sumcarry :: S Integer
-- |
-- >>> take 20 $ fromOEIS "A060790"
-- [1,2,2,3,15,38,110,323,927,2682,7754,22403,64751,187134,540822,1563011,4517183,13054898,37729362,109039875]
--
--
--
-- >>> stake 20 $ revFix apolloD2
-- [2.0,2.0,3.0,15.0,38.0,110.0,323.0,927.0,2682.0,7754.0,22403.0,64751.0,187134.0,540822.0,1563011.0,4517183.0,1.3054898e7,3.7729362e7,1.09039875e8,3.15131087e8]
--
apolloD2 :: Floating a => [a] -> a
-- |
-- >>> stake 20 $ revFix apolloD2alt
-- [2.0,2.0,3.0,-1.0,2.0,2.0,3.0,-1.0,2.0,2.0,3.0,-1.0,2.0,2.0,3.0,-1.0,2.0,2.0,3.0,-1.0]
--
apolloD2alt :: Floating a => [a] -> a
apd2 :: Floating a => [a] -> a
fr :: Num t => (t, t, t, t, t, t, t, t) -> (t, t, t, t, t, t, t, t)
apd3 :: Coalg (Integer, (Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer)) Integer Integer
proy :: (a, a, a, a, a, a, a, a) -> Integer -> a
-- |
-- >>> stake 32 $ streamApD3
-- [0,0,1,1,1,2,2,3,4,8,9,9,15,32,32,33,56,120,121,121,209,450,450,451,780,1680,1681,1681,2911,6272,6272,6273]
--
streamApD3 :: S Integer
-- |
-- >>> stake 4 $ streamApD3'
-- [(0,0,1,1,1,2,2,3),(4,8,9,9,15,32,32,33),(56,120,121,121,209,450,450,451),(780,1680,1681,1681,2911,6272,6272,6273)]
--
streamApD3' :: S (Integer, Integer, Integer, Integer, Integer, Integer, Integer, Integer)
-- |
-- >>> take 30 $ fromOEIS "A025480"
-- [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2,10,5,11,1,12,6,13,3,14,7]
--
--
--
-- >>> stake 30 $ frac
-- [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2,10,5,11,1,12,6,13,3,14,7]
--
frac :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A000265"
-- [1,1,3,1,5,3,7,1,9,5,11,3,13,7,15,1,17,9,19,5,21,11,23,3,25,13,27,7,29,15]
--
--
--
-- >>> stake 30 $ god
-- [1,1,3,1,5,3,7,1,9,5,11,3,13,7,15,1,17,9,19,5,21,11,23,3,25,13,27,7,29,15]
--
god :: S Integer
-- |
-- diverges!!
--
blah :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A051037"
-- [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80]
--
--
--
-- >>> stake 30 $ hamming
-- [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80]
--
hamming :: S Integer
montest :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A092323"
-- [0,1,1,3,3,3,3,7,7,7,7,7,7,7,7,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
--
--
--
-- >>> stake 30 $ (diff sNat - msb)
-- [0,-1,-1,-3,-3,-3,-3,-7,-7,-7,-7,-7,-7,-7,-7,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15,-15]
--
a092323 :: S Integer
-- |
-- >>> take 30 $ fromOEIS "A007814"
-- [0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1]
--
--
--
-- >>> stake 30 $ carry
-- [0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1]
--
carry :: S Integer
-- | FIXME: Incorrect!
altCarry :: S Integer
-- |
-- >>> stake 30 $ tree 0
-- [0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1]
--
tree :: Integral a => a -> S a
-- |
-- >>> take 30 $ fromOEIS "A004526"
-- [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14]
--
--
--
-- >>> stake 30 $ a004526
-- [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14]
--
a004526 :: S Integer
-- |
-- >>> take 16 $ 0 : fromOEIS "A000330"
-- [0,0,1,5,14,30,55,91,140,204,285,385,506,650,819,1015]
--
--
--
-- >>> stake 16 $ a000330
-- [0,0,1,5,14,30,55,91,140,204,285,385,506,650,819,1015]
--
a000330 :: S Integer
-- |
-- >>> take 21 $ 1 : fromOEIS "A078008"
-- [1,1,0,2,2,6,10,22,42,86,170,342,682,1366,2730,5462,10922,21846,43690,87382,174762]
--
iterk2nk :: S Integer
iterk2nkH :: (a, b) -> a
-- |
-- >>> stake 21 $ [1,1] <<| iterk2nk
-- [1,1,0,2,2,6,10,22,42,86,170,342,682,1366,2730,5462,10922,21846,43690,87382,174762]
--
iterk2nkT :: Num a => (a, a) -> a -> (a, a)
-- |
-- >>> take 15 $ fromOEIS "A090017"
-- [0,1,4,18,80,356,1584,7048,31360,139536,620864,2762528,12291840,54692416,243353344]
--
--
--
-- >>> stake 15 $ revFix a090017
-- [0,1,4,18,80,356,1584,7048,31360,139536,620864,2762528,12291840,54692416,243353344]
--
a090017 :: G Integer Integer
-- |
-- >>> take 15 $ fromOEIS "A085449"
-- [0,1,2,8,24,80,256,832,2688,8704,28160,91136,294912,954368,3088384]
--
--
--
-- >>> stake 15 $ revFix horadam0142
-- [0,1,2,8,24,80,256,832,2688,8704,28160,91136,294912,954368,3088384]
--
horadam0142 :: G Integer Integer
-- |
-- >>> take 15 $ fromOEIS "A002605"
-- [0,1,2,6,16,44,120,328,896,2448,6688,18272,49920,136384,372608]
--
--
--
-- >>> stake 15 $ revFix a002605
-- [0,1,2,6,16,44,120,328,896,2448,6688,18272,49920,136384,372608]
--
a002605 :: G Integer Integer