oeis-0.3.6: Interface to the Online Encyclopedia of Integer Sequences (OEIS)

Safe Haskell | None
Language | Haskell2010

Math.OEIS

Contents

- Example usage
- Lookup functions
- Data structures

Synopsis

- getSequenceByID :: String -> Maybe SequenceData
- lookupSequenceByID :: String -> Maybe OEISSequence
- extendSequence :: SequenceData -> SequenceData
- lookupSequence :: SequenceData -> Maybe OEISSequence
- getSequenceByID_IO :: String -> IO (Maybe SequenceData)
- lookupSequenceByID_IO :: String -> IO (Maybe OEISSequence)
- extendSequence_IO :: [Integer] -> IO [Integer]
- lookupSequence_IO :: SequenceData -> IO (Maybe OEISSequence)
- searchSequence_IO :: String -> IO (Maybe OEISSequence)
- lookupOEIS :: String -> IO [String]
- type SequenceData = [Integer]
- data Language
  - = Mathematica
  - | Maple
  - | Other
- data Keyword
  - = Base
  - | Bref
  - | Changed
  - | Cofr
  - | Cons
  - | Core
  - | Dead
  - | Dumb
  - | Dupe
  - | Easy
  - | Eigen
  - | Fini
  - | Frac
  - | Full
  - | Hard
  - | More
  - | Mult
  - | New
  - | Nice
  - | Nonn
  - | Obsc
  - | Sign
  - | Tabf
  - | Tabl
  - | Uned
  - | Unkn
  - | Walk
  - | Word
- data OEISSequence = OEIS {
  - catalogNums :: [String]
  - sequenceData :: SequenceData
  - signedData :: SequenceData
  - description :: String
  - references :: [String]
  - links :: [String]
  - formulas :: [String]
  - xrefs :: [String]
  - author :: String
  - offset :: Int
  - firstGT1 :: Int
  - programs :: [(Language, String)]
  - extensions :: [String]
  - examples :: [String]
  - keywords :: [Keyword]
  - comments :: [String]
  }

# Example usage

Suppose we are interested in answering the question, "how many distinct binary trees are there with exactly 20 nodes?" Some naive code to answer this question might be as follows:

    import Data.List (genericLength)

    -- data-less binary trees.
    data BTree = Empty | Fork BTree BTree  deriving Show

    -- A list of all the binary trees with exactly n nodes.
    listTrees :: Int -> [BTree]
    listTrees 0 = [Empty]
    listTrees n = [Fork left right |
                   k <- [0..n-1],
                   left <- listTrees k,
                   right <- listTrees (n-1-k) ]

    countTrees :: Int -> Integer
    countTrees = genericLength . listTrees

The problem, of course, is that `countTrees` is horribly inefficient:

    *Main> :set +s
    *Main> countTrees 5
    42
    (0.00 secs, 0 bytes)
    *Main> countTrees 10
    16796
    (0.47 secs, 27513240 bytes)
    *Main> countTrees 12
    208012
    (7.32 secs, 357487720 bytes)
    *Main> countTrees 13
    *** Exception: stack overflow

There's really no way we can evaluate `countTrees 20`. The solution? Cheat!

    import Math.OEIS

    -- countTrees works ok up to 10 nodes.
    -- [1,2,5,14,42,132,429,1430,4862,16796]
    smallTreeCounts = map countTrees [0..10]

    -- now, extend the sequence via the OEIS!
    treeCounts = extendSequence smallTreeCounts

Now we can answer the question:

    *Main> treeCounts !! 20
    6564120420

Sweet. Of course, to have any sort of confidence in our answer, more research is required! Let's see what combinatorial goodness we have stumbled across.

    *Main> description `fmap` lookupSequence smallTreeCounts
    Just "Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers."

Catalan numbers, interesting. And a nice formula we could use to code up a real solution! Hmm, where can we read more about these so-called 'Catalan numbers'?

    *Main> (head . references) `fmap` lookupSequence smallTreeCounts
    Just ["A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, preprint, 2007."]
    *Main> (head . links) `fmap` lookupSequence smallTreeCounts
    Just ["N. J. A. Sloane, <a href=\"http://www.research.att.com/~njas/sequences/b000108.txt\">The first 200 Catalan numbers</a>"]

And so on. Reams of collected mathematical knowledge at your fingertips! You must promise only to use this power for Good.

# Lookup functions

getSequenceByID :: String -> Maybe SequenceData Source

Look up a sequence in the OEIS by its catalog number. Generally this would be its A-number, but M-numbers (from the /Encyclopedia of Integer Sequences) and N-numbers (from the Handbook of Integer Sequences/) can be used as well.

Note that the result is not in the `IO` monad, even though the implementation requires looking up information via the Internet. There are no side effects to speak of, and from a practical point of view the function is referentially transparent (OEIS A-numbers could change in theory, but it's extremely unlikely).

Examples:

    Prelude Math.OEIS> getSequenceByID "A000040"    -- the prime numbers
    Just [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47...

    Prelude Math.OEIS> getSequenceByID "nosuch"     -- no such sequence!
    Nothing

lookupSequenceByID :: String -> Maybe OEISSequence Source

Look up a sequence by ID number, returning a data structure containing the entirety of the information the OEIS has on the sequence.

The standard disclaimer about not being in the `IO` monad applies.

Examples:

    Prelude Math.OEIS> description `fmap` lookupSequenceByID "A000040"
    Just "The prime numbers."

    Prelude Math.OEIS> keywords `fmap` lookupSequenceByID "A000105"
    Just [Nonn,Hard,Nice,Core]

extendSequence :: SequenceData -> SequenceData Source

Extend a sequence by using it as a lookup to the OEIS, taking the first sequence returned as a result, and using it to augment the original sequence.

Note that `xs` is guaranteed to be a prefix of `extendSequence xs`. If the matched OEIS sequence contains any elements prior to those matching `xs`, they will be dropped. In addition, if no matching sequences are found, `xs` will be returned unchanged.

The result is not in the `IO` monad even though the implementation requires looking up information via the Internet. There are no side effects, and practically speaking this function is referentially transparent (technically, results may change from time to time when the OEIS database is updated; this is slightly more likely than the results of `getSequenceByID` changing, but still unlikely enough to be essentially a non-issue. Again, purists may use `extendSequence_IO`).

Examples:

    Prelude Math.OEIS> extendSequence [5,7,11,13,17]
    [5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71...

    Prelude Math.OEIS> extendSequence [2,4,8,16,32]
    [2,4,8,16,32,64,128,256,512,1024,2048,4096,8192...

    Prelude Math.OEIS> extendSequence [9,8,7,41,562]   -- nothing matches
    [9,8,7,41,562]

lookupSequence :: SequenceData -> Maybe OEISSequence Source

Find a matching sequence in the OEIS database, returning a data structure containing the entirety of the information the OEIS has on the sequence.

The standard disclaimer about not being in the `IO` monad applies.

getSequenceByID_IO :: String -> IO (Maybe SequenceData) Source

The same as `getSequenceByID`, but with a result in the `IO` monad.

lookupSequenceByID_IO :: String -> IO (Maybe OEISSequence) Source

The same as `lookupSequenceByID`, but in the `IO` monad.

extendSequence_IO :: [Integer] -> IO [Integer] Source

The same as `extendSequence`, but in the `IO` monad.

lookupSequence_IO :: SequenceData -> IO (Maybe OEISSequence) Source

The same as `lookupSequence`, but in the `IO` monad.

searchSequence_IO :: String -> IO (Maybe OEISSequence) Source

Look up a sequence in the OEIS using its search function.

lookupOEIS :: String -> IO [String] Source

Interpret a string as a OEIS request, and return the results as Strings.

# Data structures

type SequenceData = [Integer] Source

data Language Source

Programming language that some code to generate the sequence is written in. The only languages indicated natively by the OEIS database are Mathematica and Maple; any other languages will be listed (usually in parentheses) at the beginning of the actual code snippet.

Constructors

Mathematica |
Maple |
Other |

Instances

Show Language Source |

data Keyword Source

OEIS keywords. For more information on the meaning of each keyword, see http://oeis.org/eishelp2.html#RK.

Constructors

Base |
Bref |
Changed |
Cofr |
Cons |
Core |
Dead |
Dumb |
Dupe |
Easy |
Eigen |
Fini |
Frac |
Full |
Hard |
More |
Mult |
New |
Nice |
Nonn |
Obsc |
Sign |
Tabf |
Tabl |
Uned |
Unkn |
Walk |
Word |

Instances

Eq Keyword Source |
Read Keyword Source |
Show Keyword Source |

data OEISSequence Source

Data structure for storing an OEIS entry. For more information on the various components, see http://oeis.org/eishelp2.html.

Constructors

OEIS |

Fields

catalogNums :: [String]

  Catalog number(s), e.g. A000040, N1425. (%I)

sequenceData :: SequenceData

  The actual sequence data (or absolute values of the sequence data in the case of signed sequences). (%S,T,U)

signedData :: SequenceData

  Signed sequence data (empty for sequences with all positive entries). (%V,W,X)

description :: String

  Short description of the sequence. (%N)

references :: [String]

  List of academic references. (%D)

links :: [String]

  List of links to more information on the web. (%H)

formulas :: [String]

  Formulas or equations involving the sequence. (%F)

xrefs :: [String]

  Cross-references to other sequences. (%Y)

author :: String

  Author who input the sequence into the database. (%A)

offset :: Int

  Subscript/index of the first term. (%O)

firstGT1 :: Int

  Index of the first term > 1. (%O)

programs :: [(Language, String)]

  Code that can be used to generate the sequence. (%p,t,o)

extensions :: [String]

  Corrections, extensions, or edits. (%E)

examples :: [String]

  Examples. (%e)

keywords :: [Keyword]

  Keywords. (%K)

comments :: [String]

  Comments. (%C)

Instances

Show OEISSequence Source |