oeis 0.1 → 0.2
raw patch · 4 files changed
+114/−63 lines, 4 files
Files
- Math/OEIS.hs +67/−48
- README +6/−7
- example/Catalan.hs +26/−0
- oeis.cabal +15/−8
Math/OEIS.hs view
@@ -1,18 +1,19 @@ -- | A Haskell interface to the Online Encyclopedia of Integer -- Sequences (OEIS), <http://www.research.att.com/~njas/sequences/>.--- Comments, suggestions, or bug reports should be sent to +-- Comments, suggestions, or bug reports should be sent to -- Brent Yorgey, byorgey /at/ gmail /dot/ com. -module Math.OEIS - ( +module Math.OEIS+ ( -- * Example usage -- $sample- + -- * Lookup functions- getSequenceByID, lookupSequenceByID, + getSequenceByID, lookupSequenceByID, extendSequence, lookupSequence, getSequenceByID_IO, lookupSequenceByID_IO, extendSequence_IO, lookupSequence_IO,+ searchSequence_IO, lookupOEIS, -- * Data structures SequenceData,@@ -21,16 +22,33 @@ ) where -import Network.HTTP-import Network.URI-import System.IO.Unsafe (unsafePerformIO)+import Control.Arrow (second, (***))+import Data.Char (isDigit, isSpace, toUpper, toLower) import Data.List (intersperse, isPrefixOf, tails, foldl')-import Data.Char (toUpper, toLower, isSpace) import Data.Maybe (listToMaybe, fromMaybe)-import Control.Arrow+import Network.HTTP -- (simpleHTTP, rspBody, rspCode, rqBody, rqHeaders, rqMethod, rqURI, Request(..), GET)+import Network.URI (escapeURIString, isAllowedInURI, parseURI, URI)+import System.IO.Unsafe (unsafePerformIO) type SequenceData = [Integer] +-- | Interpret a string as a OEIS request, and return the results as Strings+lookupOEIS :: String -> IO [String]+lookupOEIS a = do+ let a' = commas . reverse . dropWhile isSpace . reverse . dropWhile isSpace $ a+ x <- searchSequence_IO a'+ case x of+ Nothing -> return ["Sequence not found. "]+ Just s -> return [description s, show $ sequenceData s]+ where commas [] = []+ commas (x:' ':xs) | isDigit x = x : ',' : commas xs+ commas (x:xs) = x : commas xs+++-- | Look up a sequence in the OEIS using its search function+searchSequence_IO :: String -> IO (Maybe OEISSequence)+searchSequence_IO x = getOEIS (baseSearchURI ++) (escapeURIString isAllowedInURI $ 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@@ -43,9 +61,9 @@ -- (OEIS A-numbers could change in theory, but it's extremely -- unlikely). If you're a nitpicky purist, feel free to use the -- provided 'getSequenceByID_IO' instead.--- +-- -- 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... -- >@@ -81,8 +99,8 @@ lookupSequenceByID_IO :: String -> IO (Maybe OEISSequence) lookupSequenceByID_IO = getOEIS idSearchURI --- | 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 +-- | 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@.@@ -117,7 +135,7 @@ extendSequence_IO :: [Integer] -> IO [Integer] extendSequence_IO [] = return [] extendSequence_IO xs = do oeis <- lookupSequence_IO xs- case oeis of + case oeis of Nothing -> return xs Just s -> return $ extend xs (sequenceData s) @@ -141,6 +159,7 @@ extend :: SequenceData -> SequenceData -> SequenceData extend xs ext = fromMaybe xs . listToMaybe . filter (xs `isPrefixOf`) $ tails ext +baseSearchURI :: String baseSearchURI = "http://www.research.att.com/~njas/sequences/?n=1&fmt=3&q=" idSearchURI :: String -> String@@ -163,7 +182,7 @@ get uri = do eresp <- simpleHTTP (request uri) case eresp of- (Left e) -> return (Left LookupError)+ (Left _) -> return (Left LookupError) (Right resp) -> case rspCode resp of (2,0,0) -> return (Right $ rspBody resp) _ -> return (Left LookupError)@@ -189,7 +208,7 @@ data Keyword = Base | Bref | 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 + Unkn | Walk | Word deriving (Eq,Show,Read) readKeyword :: String -> Keyword@@ -203,38 +222,38 @@ -- on the various components, see -- <http://www.research.att.com/~njas/sequences/eishelp2.html>. -data OEISSequence = - OEIS { catalogNums :: [String], +data OEISSequence =+ OEIS { catalogNums :: [String], -- ^ Catalog number(s), e.g. A000040, N1425. (%I)- sequenceData :: SequenceData, + sequenceData :: SequenceData, -- ^ The actual sequence data (or absolute values of the sequence data in the case of signed sequences). (%S,T,U)- signedData :: SequenceData, + 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], + references :: [String], -- ^ List of academic references. (%D)- links :: [String], + links :: [String], -- ^ List of links to more information on the web. (%H)- formulas :: [String], + formulas :: [String], -- ^ Formulas or equations involving the sequence. (%F)- xrefs :: [String], + xrefs :: [String], -- ^ Cross-references to other sequences. (%Y)- author :: String, + author :: String, -- ^ Author who input the sequence into the database. (%A)- offset :: Int, + offset :: Int, -- ^ Subscript\/index of the first term. (%O)- firstGT1 :: Int, + firstGT1 :: Int, -- ^ Index of the first term \> 1. (%O)- programs :: [(Language,String)], + programs :: [(Language,String)], -- ^ Code that can be used to generate the sequence. (%p,t,o)- extensions :: [String], + extensions :: [String], -- ^ Corrections, extensions, or edits. (%E)- examples :: [String], + examples :: [String], -- ^ Examples. (%e)- keywords :: [Keyword], + keywords :: [Keyword], -- ^ Keywords. (%K)- comments :: [String] + comments :: [String] -- ^ Comments. (%C) } deriving Show @@ -244,31 +263,32 @@ addElement :: (Char, String) -> (OEISSequence -> OEISSequence) addElement ('I', x) c = c { catalogNums = words x } addElement (t, x) c | t `elem` "STU" = c { sequenceData = nums ++ (sequenceData c) }- where nums = map read $ csvItems x + where nums = map read $ csvItems x addElement (t, x) c | t `elem` "VWX" = c { signedData = nums ++ (signedData c) } where nums = map read $ csvItems x addElement ('N', x) c = c { description = x }-addElement ('D', x) c = c { references = x : (references c) } +addElement ('D', x) c = c { references = x : (references c) } addElement ('H', x) c = c { links = x : (links c) } addElement ('F', x) c = c { formulas = x : (formulas c) } addElement ('Y', x) c = c { xrefs = x : (xrefs c) } addElement ('A', x) c = c { author = x }-addElement ('O', x) c = c { offset = read o +addElement ('O', x) c = c { offset = read o , firstGT1 = read f } where (o,f) = second tail . span (/=',') $ x addElement ('p', x) c = c { programs = (Mathematica, x) : (programs c) } addElement ('t', x) c = c { programs = (Maple, x) : (programs c) }-addElement ('o', x) c = c { programs = (Other, x) : +addElement ('o', x) c = c { programs = (Other, x) : (programs c) } addElement ('E', x) c = c { extensions = x : (extensions c) } addElement ('e', x) c = c { examples = x : (examples c) } addElement ('K', x) c = c { keywords = parseKeywords x } addElement ('C', x) c = c { comments = x : (comments c) }+addElement _ c = c parseOEIS :: String -> Maybe OEISSequence-parseOEIS x = if "no match" `isPrefixOf` (ls!!1) +parseOEIS x = if "no match" `isPrefixOf` (ls!!1) then Nothing else Just . foldl' (flip addElement) emptyOEIS . reverse . parseRawOEIS $ ls' where ls = lines x@@ -292,16 +312,15 @@ | otherwise = (x:xs) parseItem :: String -> (Char, String)-parseItem s = (c, str) +parseItem s = (c, str) where ( '%':c:_ , rest) = splitWord s- ( idNum, str ) = if (c == 'I') then ("", rest)+ (_, str ) = if (c == 'I') then ("", rest) else splitWord rest- + combineConts :: [String] -> [String]-combineConts [] = []-combineConts [x] = [x]-combineConts (s@('%':c:_) : ss) = +combineConts (s@('%':_:_) : ss) = uncurry (:) . (joinConts s *** combineConts) . break isItem $ ss+combineConts ss = ss splitWord :: String -> (String, String) splitWord = second trimLeft . break isSpace@@ -329,11 +348,11 @@ > -- A list of all the binary trees with exactly n nodes. > listTrees :: Int -> [BTree] > listTrees 0 = [Empty]-> listTrees n = [Fork left right | +> listTrees n = [Fork left right | > k <- [0..n-1], > left <- listTrees k, > right <- listTrees (n-1-k) ]-> +> > countTrees :: Int -> Integer > countTrees = genericLength . listTrees @@ -360,7 +379,7 @@ > > -- countTrees works ok up to 10 nodes. > smallTreeCounts = map countTrees [0..10]-> +> > -- now, extend the sequence via the OEIS! > treeCounts = extendSequence smallTreeCounts @@ -390,5 +409,5 @@ @ And so on. Reams of collected mathematical knowledge at your-fingertips! You must promise only to use this power for Good. +fingertips! You must promise only to use this power for Good. -}
README view
@@ -1,4 +1,3 @@- Math.OEIS is a library module for interfacing with the Online Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/).@@ -10,22 +9,22 @@ Get the dependencies Math.OEIS depends on the network and HTTP libraries. On some platforms,- these come bundled with GHC. On others, such as Debian/Ubuntu, you can get + these come bundled with GHC. On others, such as Debian/Ubuntu, you can get them from your package manager: apt-get install libghc6-network-dev Build with Cabal: - runhaskell Setup.lhs configure --prefix=$HOME- runhaskell Setup.lhs build- runhaskell Setup.lhs install --user+ runhaskell Setup configure --prefix=$HOME+ runhaskell Setup build+ runhaskell Setup install --user Building Haddock documentation (optional): - runhaskell Setup.lhs haddock+ runhaskell Setup haddock - Once the documentation has been built, you can access it by + Once the documentation has been built, you can access it by pointing your browser to dist/doc/html/index.html. It contains descriptions of the exported functions, in addition to many examples of the library's use.
+ example/Catalan.hs view
@@ -0,0 +1,26 @@+import Math.OEIS+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) ]++-- HORRIBLY INEFFICIENT!!+countTrees :: Int -> Integer+countTrees = genericLength . listTrees++-- This is about the best we can do.+smallTreeCounts = map countTrees [0..10]++-- so... cheat! Extend the sequence via the OEIS.+treeCounts = extendSequence smallTreeCounts++countTrees' :: Int -> Integer+countTrees' n = treeCounts !! n
oeis.cabal view
@@ -1,14 +1,21 @@ Name: oeis-Version: 0.1+Version: 0.2 Stability: experimental-Description: Haskell interface to the Online Encyclopedia of Integer Sequences.-Synopsis: Interface to the Online Encyclopedia of Integer Sequences++Author: Brent Yorgey+Maintainer: Brent Yorgey <byorgey@gmail.com> License: BSD3 License-file: LICENSE-Extra-source-files: README-Author: Brent Yorgey-Maintainer: byorgey@gmail.com+ Category: Math-Build-Depends: base,network,HTTP+Synopsis: Interface to the Online Encyclopedia of Integer Sequences+Description: Haskell interface to the Online Encyclopedia of Integer Sequences.+Homepage: http://code.haskell.org/oeis++data-files: README, example/Catalan.hs++Build-Depends: base, network, HTTP+Build-Type: Simple+ Exposed-Modules: Math.OEIS-ghc-options: -O2+ghc-options: -Wall