    module Math.OEIS
      ( -- * Example usage
        -- $sample

        -- * Lookup functions
        getSequenceByID,    lookupSequenceByID
      , extendSequence,     lookupSequence
      , getSequenceByID_IO, lookupSequenceByID_IO
      , extendSequence_IO,  lookupSequence_IO
      , searchSequence_IO,  lookupOEIS
      , searchSequences_IO, lookupSequences_IO

        -- * Data structures
      , SequenceData
      , Language(..), Keyword(..)
      , OEISSequence(..)
      ) where

    --------------------------------------------------------------------------------

    import Control.Applicative ((<$>))
    import Prelude
    import Data.Char        (isDigit, isSpace)
    import Data.List        (isPrefixOf, tails, find)
    import Data.Maybe       (listToMaybe, fromMaybe)
    import Network.URI      (escapeURIString, isAllowedInURI)
    import System.IO.Unsafe (unsafePerformIO)

    import Math.OEIS.Internal
    import Math.OEIS.Types

    --------------------------------------------------------------------------------

    -- | Interpret a string as a OEIS request, and return the results as Strings.
    lookupOEIS :: String -> IO [String]
    lookupOEIS :: String -> IO [String]
    lookupOEIS String
    a = do
             let a' :: String
    a'  = String -> String
    commas (String -> String) -> (String -> String) -> String -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> String
    forall a. [a] -> [a]
    reverse (String -> String) -> (String -> String) -> String -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Char -> Bool) -> String -> String
    forall a. (a -> Bool) -> [a] -> [a]
    dropWhile Char -> Bool
    isSpace (String -> String) -> (String -> String) -> String -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> String
    forall a. [a] -> [a]
    reverse (String -> String) -> (String -> String) -> String -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Char -> Bool) -> String -> String
    forall a. (a -> Bool) -> [a] -> [a]
    dropWhile Char -> Bool
    isSpace (String -> String) -> String -> String
    forall a b. (a -> b) -> a -> b
    $ String
    a
             Maybe OEISSequence
    x <- String -> IO (Maybe OEISSequence)
    searchSequence_IO String
    a'
             case Maybe OEISSequence
    x of
                Maybe OEISSequence
    Nothing -> [String] -> IO [String]
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [String
    "Sequence not found."]
                Just OEISSequence
    s  -> [String] -> IO [String]
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [OEISSequence -> String
    description OEISSequence
    s, SequenceData -> String
    forall a. Show a => a -> String
    show (SequenceData -> String) -> SequenceData -> String
    forall a b. (a -> b) -> a -> b
    $ OEISSequence -> SequenceData
    sequenceData OEISSequence
    s]
     where commas :: String -> String
    commas []                     = []
           commas (Char
    x:Char
    ' ':String
    xs) | Char -> Bool
    isDigit Char
    x = Char
    x Char -> String -> String
    forall a. a -> [a] -> [a]
    : Char
    ',' Char -> String -> String
    forall a. a -> [a] -> [a]
    : String -> String
    commas String
    xs
           commas (Char
    x:String
    xs)                 = Char
    x Char -> String -> String
    forall a. a -> [a] -> [a]
    : String -> String
    commas String
    xs

    -- | Look up a sequence in the OEIS using its search function.
    searchSequence_IO :: String -> IO (Maybe OEISSequence)
    searchSequence_IO :: String -> IO (Maybe OEISSequence)
    searchSequence_IO String
    x = [OEISSequence] -> Maybe OEISSequence
    forall a. [a] -> Maybe a
    listToMaybe ([OEISSequence] -> Maybe OEISSequence)
    -> IO [OEISSequence] -> IO (Maybe OEISSequence)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> String -> IO [OEISSequence]
    searchSequences_IO String
    x

    -- | Look up sequences in the OEIS using its search function (returns up to
    -- 10 results).
    searchSequences_IO :: String -> IO [OEISSequence]
    searchSequences_IO :: String -> IO [OEISSequence]
    searchSequences_IO String
    x = (String -> String) -> String -> IO [OEISSequence]
    forall a. (a -> String) -> a -> IO [OEISSequence]
    getOEIS (String
    baseSearchURI String -> String -> String
    forall a. [a] -> [a] -> [a]
    ++) ((Char -> Bool) -> String -> String
    escapeURIString Char -> Bool
    isAllowedInURI String
    x)

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

    getSequenceByID :: String -> Maybe SequenceData
    getSequenceByID :: String -> Maybe SequenceData
    getSequenceByID = IO (Maybe SequenceData) -> Maybe SequenceData
    forall a. IO a -> a
    unsafePerformIO (IO (Maybe SequenceData) -> Maybe SequenceData)
    -> (String -> IO (Maybe SequenceData))
    -> String
    -> Maybe SequenceData
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> IO (Maybe SequenceData)
    getSequenceByID_IO

    -- | The same as 'getSequenceByID', but with a result in the 'IO' monad.
    getSequenceByID_IO :: String -> IO (Maybe SequenceData)
    getSequenceByID_IO :: String -> IO (Maybe SequenceData)
    getSequenceByID_IO String
    x = (Maybe OEISSequence -> Maybe SequenceData)
    -> IO (Maybe OEISSequence) -> IO (Maybe SequenceData)
    forall a b. (a -> b) -> IO a -> IO b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((OEISSequence -> SequenceData)
    -> Maybe OEISSequence -> Maybe SequenceData
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap OEISSequence -> SequenceData
    sequenceData) (String -> IO (Maybe OEISSequence)
    lookupSequenceByID_IO String
    x)

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

    lookupSequenceByID :: String -> Maybe OEISSequence
    lookupSequenceByID :: String -> Maybe OEISSequence
    lookupSequenceByID = IO (Maybe OEISSequence) -> Maybe OEISSequence
    forall a. IO a -> a
    unsafePerformIO (IO (Maybe OEISSequence) -> Maybe OEISSequence)
    -> (String -> IO (Maybe OEISSequence))
    -> String
    -> Maybe OEISSequence
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> IO (Maybe OEISSequence)
    lookupSequenceByID_IO

    -- | The same as 'lookupSequenceByID', but in the 'IO' monad.
    lookupSequenceByID_IO :: String -> IO (Maybe OEISSequence)
    lookupSequenceByID_IO :: String -> IO (Maybe OEISSequence)
    lookupSequenceByID_IO String
    x = [OEISSequence] -> Maybe OEISSequence
    forall a. [a] -> Maybe a
    listToMaybe ([OEISSequence] -> Maybe OEISSequence)
    -> IO [OEISSequence] -> IO (Maybe OEISSequence)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (String -> String) -> String -> IO [OEISSequence]
    forall a. (a -> String) -> a -> IO [OEISSequence]
    getOEIS String -> String
    idSearchURI String
    x

    -- | 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]
    extendSequence :: SequenceData -> SequenceData
    extendSequence :: SequenceData -> SequenceData
    extendSequence = IO SequenceData -> SequenceData
    forall a. IO a -> a
    unsafePerformIO (IO SequenceData -> SequenceData)
    -> (SequenceData -> IO SequenceData)
    -> SequenceData
    -> SequenceData
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . SequenceData -> IO SequenceData
    extendSequence_IO

    -- | The same as 'extendSequence', but in the 'IO' monad.
    extendSequence_IO :: [Integer] -> IO [Integer]
    extendSequence_IO :: SequenceData -> IO SequenceData
    extendSequence_IO [] = SequenceData -> IO SequenceData
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    extendSequence_IO SequenceData
    xs = do
        Maybe OEISSequence
    oeis <- SequenceData -> IO (Maybe OEISSequence)
    lookupSequence_IO SequenceData
    xs
        SequenceData -> IO SequenceData
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (SequenceData -> IO SequenceData)
    -> SequenceData -> IO SequenceData
    forall a b. (a -> b) -> a -> b
    $ case Maybe OEISSequence
    oeis of
          Maybe OEISSequence
    Nothing -> SequenceData
    xs
          Just OEISSequence
    s  -> SequenceData -> SequenceData -> SequenceData
    extend SequenceData
    xs (OEISSequence -> SequenceData
    sequenceData OEISSequence
    s)

    -- | @extend xs ext@ returns the maximal suffix of @ext@ of which @xs@ is a
    -- prefix, or @xs@ if @xs@ is not a prefix of any suffixes of @ext@. It is
    -- guaranteed that
    --
    -- > forall xs ext. xs `isPrefixOf` (extend xs ext)
    extend :: SequenceData -> SequenceData -> SequenceData
    extend :: SequenceData -> SequenceData -> SequenceData
    extend SequenceData
    xs SequenceData
    ext = SequenceData -> Maybe SequenceData -> SequenceData
    forall a. a -> Maybe a -> a
    fromMaybe SequenceData
    xs (Maybe SequenceData -> SequenceData)
    -> ([SequenceData] -> Maybe SequenceData)
    -> [SequenceData]
    -> SequenceData
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (SequenceData -> Bool) -> [SequenceData] -> Maybe SequenceData
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
    find (SequenceData
    xs SequenceData -> SequenceData -> Bool
    forall a. Eq a => [a] -> [a] -> Bool
    `isPrefixOf`) ([SequenceData] -> SequenceData) -> [SequenceData] -> SequenceData
    forall a b. (a -> b) -> a -> b
    $ SequenceData -> [SequenceData]
    forall a. [a] -> [[a]]
    tails SequenceData
    ext

    -- | 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.
    lookupSequence :: SequenceData -> Maybe OEISSequence
    lookupSequence :: SequenceData -> Maybe OEISSequence
    lookupSequence = IO (Maybe OEISSequence) -> Maybe OEISSequence
    forall a. IO a -> a
    unsafePerformIO (IO (Maybe OEISSequence) -> Maybe OEISSequence)
    -> (SequenceData -> IO (Maybe OEISSequence))
    -> SequenceData
    -> Maybe OEISSequence
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . SequenceData -> IO (Maybe OEISSequence)
    lookupSequence_IO

    -- | The same as 'lookupSequence', but in the 'IO' monad.
    lookupSequence_IO :: SequenceData -> IO (Maybe OEISSequence)
    lookupSequence_IO :: SequenceData -> IO (Maybe OEISSequence)
    lookupSequence_IO SequenceData
    x = [OEISSequence] -> Maybe OEISSequence
    forall a. [a] -> Maybe a
    listToMaybe ([OEISSequence] -> Maybe OEISSequence)
    -> IO [OEISSequence] -> IO (Maybe OEISSequence)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> SequenceData -> IO [OEISSequence]
    lookupSequences_IO SequenceData
    x

    -- | Similar to 'lookupSequence_IO', but return up to 10 results.
    lookupSequences_IO :: SequenceData -> IO [OEISSequence]
    lookupSequences_IO :: SequenceData -> IO [OEISSequence]
    lookupSequences_IO = (SequenceData -> String) -> SequenceData -> IO [OEISSequence]
    forall a. (a -> String) -> a -> IO [OEISSequence]
    getOEIS SequenceData -> String
    seqSearchURI

    --------------------------------------------------------------------------------

    {- $sample

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

    --------------------------------------------------------------------------------

    {-# ANN module "HLint: ignore Use camelCase" #-}