dyckword (empty) → 0.1.0.1
raw patch · 7 files changed
+641/−0 lines, 7 filesdep +ansi-terminaldep +basedep +dyckwordsetup-changed
Dependencies added: ansi-terminal, base, dyckword, exact-combinatorics, hspec, text
Files
- LICENSE +30/−0
- README.md +23/−0
- Setup.hs +2/−0
- dyckword.cabal +47/−0
- src/Math/DyckWord/Binary.hs +342/−0
- src/Math/DyckWord/Binary/Internal.hs +16/−0
- tests/Suite.hs +181/−0
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Johannes Hilden (c) 2017++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Author name here nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,23 @@+# dyckword++In formal language theory, the *Dyck language* consists of all strings of evenly balanced left and right parentheses, brackets, or some other symbols, together with the *empty* word. Words in this language (named after German mathematician Walther von Dyck) are known as *Dyck words*, some examples of which are `()()()`, `(())((()))`, and `((()()))()`.++The type of Dyck language considered here is defined over a binary alphabet. We will take this alphabet to be the set Σ = {(, )} in the following examples. The binary Dyck language is the subset of Σ* (the Kleene closure of Σ) of all words that satisfy two conditions:++1. The number of left brackets must be the same as the number of right brackets.+2. Going from left to right, for each character read, the total number of right brackets visited must be less than or equal to the number of left brackets up to the current position.++E.g., `(()(()` and `())(())()` are **not** Dyck words.++When regarded as a combinatorial class – with the size of a word defined as the number of bracket pairs it contains – the counting sequence associated with the Dyck language is the *Catalan numbers*.++| Size | Count | Words |+| --- | ----- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |+| 0 | 1 | ε |+| 1 | 1 | ⟨⟩ |+| 2 | 2 | ⟨⟩⟨⟩ ⟨⟨⟩⟩ |+| 3 | 5 | ⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟨⟩⟩ ⟨⟨⟩⟩⟨⟩ ⟨⟨⟩⟨⟩⟩ ⟨⟨⟨⟩⟩⟩ |+| 4 | 14 | ⟨⟩⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟩⟨⟨⟩⟩ ⟨⟩⟨⟨⟩⟩⟨⟩ ⟨⟩⟨⟨⟩⟨⟩⟩ ⟨⟩⟨⟨⟨⟩⟩⟩ ⟨⟨⟩⟩⟨⟩⟨⟩ ⟨⟨⟩⟩⟨⟨⟩⟩ ⟨⟨⟩⟨⟩⟩⟨⟩ ⟨⟨⟨⟩⟩⟩⟨⟩ ⟨⟨⟩⟨⟩⟨⟩⟩ ⟨⟨⟩⟨⟨⟩⟩⟩ ⟨⟨⟨⟩⟩⟨⟩⟩ ⟨⟨⟨⟩⟨⟩⟩⟩ ⟨⟨⟨⟨⟩⟩⟩⟩ |+| 5 | 42 | ⟨⟩⟨⟩⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟩⟨⟩⟨⟨⟩⟩ ⟨⟩⟨⟩⟨⟨⟩⟩⟨⟩ ⟨⟩⟨⟩⟨⟨⟩⟨⟩⟩ ⟨⟩⟨⟩⟨⟨⟨⟩⟩⟩ … |+| 6 | 132 | … |+
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ dyckword.cabal view
@@ -0,0 +1,47 @@+name: dyckword+version: 0.1.0.1+synopsis: A library for working with binary Dyck words.+description:+ The binary Dyck language consists of all strings of evenly balanced left + and right parentheses, brackets, or some other symbols, together with the + /empty/ word. Words in this language are known as /Dyck words/, some + examples of which are @()()()@, @(())((()))@, and @((()()))()@.+ .+ The counting sequence associated with the Dyck language is the + /Catalan numbers/, who describe properties of a great number of + combinatorial objects.++homepage: https://github.com/johanneshilden/dyckword#readme+license: BSD3+license-file: LICENSE+author: Johannes Hildén+maintainer: johannes@isomorphic.co+copyright: 2017 Johannes Hildén+category: Math+build-type: Simple+extra-source-files: README.md+cabal-version: >=1.10++library+ hs-source-dirs: src+ exposed-modules: Math.DyckWord.Binary+ , Math.DyckWord.Binary.Internal+ build-depends: base >= 4.7 && < 5+ , text+ , exact-combinatorics+ default-language: Haskell2010++Test-Suite dyckword-testsuite+ hs-source-dirs: tests+ Type: exitcode-stdio-1.0+ Main-is: Suite.hs+ Build-depends: base+ , hspec+ , dyckword+ , text+ , ansi-terminal+ default-language: Haskell2010++source-repository head+ type: git+ location: https://github.com/johanneshilden/dyckword
+ src/Math/DyckWord/Binary.hs view
@@ -0,0 +1,342 @@+-- |+--+-- Module : Math.DyckWord.Binary+-- Copyright : (c) 2017 Johannes Hildén+-- License : BSD3+-- Maintainer : johannes@isomorphic.co+-- Stability : experimental+-- Portability : GHC+--+-- == Background+--+-- In formal language theory, the /Dyck language/ consists of all strings of +-- evenly balanced left and right parentheses, brackets, or some other +-- symbols, together with the /empty/ word. Words in this language (named +-- after German mathematician Walther von Dyck) are known as /Dyck words/, +-- some examples of which are @()()()@, @(())((()))@, and @((()()))()@.+--+-- The type of Dyck language considered here is defined over a binary alphabet. +-- We will take this alphabet to be the set Σ = {(, )} in the following +-- examples. The binary Dyck language is the subset of Σ* (the Kleene +-- closure of Σ) of all words that satisfy two conditions:+-- +-- 1. The number of left brackets must be the same as the number of right +-- brackets.+-- 2. Going from left to right, for each character read, the total number of +-- right brackets visited must be less than or equal to the number of left +-- brackets up to the current position.+--+-- E.g., @(()(()@ and @())(())()@ are __not__ Dyck words.+--+-- When regarded as a combinatorial class—with the 'size' of a word defined as +-- the number of bracket pairs it contains—the counting sequence associated +-- with the Dyck language is the /Catalan numbers/.+--+-- \[ +-- \begin{array}{ccl}+-- \text{Size} & \text{Count} & \text{Words}+-- \\+-- 0 & 1 & \epsilon+-- \\+-- 1 & 1 & ⟨⟩+-- \\+-- 2 & 2 & ⟨⟩⟨⟩, \ ⟨⟨⟩⟩+-- \\+-- 3 & 5 & ⟨⟩⟨⟩⟨⟩, \ ⟨⟩⟨⟨⟩⟩, \ ⟨⟨⟩⟩⟨⟩, \ ⟨⟨⟩⟨⟩⟩, \ ⟨⟨⟨⟩⟩⟩+-- \\+-- 4 & 14 & ⟨⟩⟨⟩⟨⟩⟨⟩, \ ⟨⟩⟨⟩⟨⟨⟩⟩, \ ⟨⟩⟨⟨⟩⟩⟨⟩, \ ⟨⟩⟨⟨⟩⟨⟩⟩, \ ⟨⟩⟨⟨⟨⟩⟩⟩, \ ⟨⟨⟩⟩⟨⟩⟨⟩, \ ⟨⟨⟩⟩⟨⟨⟩⟩, \ ⟨⟨⟩⟨⟩⟩⟨⟩,+-- \\+-- & & ⟨⟨⟨⟩⟩⟩⟨⟩, \ ⟨⟨⟩⟨⟩⟨⟩⟩, \ ⟨⟨⟩⟨⟨⟩⟩⟩, \ ⟨⟨⟨⟩⟩⟨⟩⟩, \ ⟨⟨⟨⟩⟨⟩⟩⟩, \ ⟨⟨⟨⟨⟩⟩⟩⟩+-- \\+-- 5 & 42 & ⟨⟩⟨⟩⟨⟩⟨⟩⟨⟩, \ ⟨⟩⟨⟩⟨⟩⟨⟨⟩⟩, \ ⟨⟩⟨⟩⟨⟨⟩⟩⟨⟩, \ ⟨⟩⟨⟩⟨⟨⟩⟨⟩⟩, \ ⟨⟩⟨⟩⟨⟨⟨⟩⟩⟩, \ \dots, \ ⟨⟨⟨⟨⟨⟩⟩⟩⟩⟩+-- \\+-- 6 & 132 & \dots+-- \end{array}+-- \]++module Math.DyckWord.Binary ( + -- * Types+ Size+ , Rank+ , DyckWord+ -- * Creating and inspecting Dyck words+ , empty+ , size + , setAlphabet+ , concatWords + -- ** Textual form+ , fromText + , fromText'+ , toText+ -- * Ranking and unranking+ -- $ranking+ , rank + , rankRelative + , unrank + , unrankRelative + , unrankRelative'+ , wordsOfSize + ) where++import Data.Maybe ( fromJust )+import Data.Monoid ( (<>) )+import Data.Text ( Text, unfoldrN )+import Math.DyckWord.Binary.Internal++import qualified Data.Text as T++-- $ranking+--+-- To /rank/ a Dyck word is to determine its position in some ordered sequence +-- of words. The dual of this—to produce the Dyck word corresponding to a +-- position in said sequence—is called /unranking/. The order we are +-- interested in here is known as /shortlex/, and it demands that a smaller +-- Dyck word always gets precedence over a bigger one. When comparing words of +-- the same size, normal lexicographical order applies. +--+-- === Relative vs. absolute rank+--+-- In this library, we adopt the following (non-standard) terminology.+-- The /relative/ rank of a Dyck word /w/ is its position in the sequence of +-- those words with the same size as /w/. By contrast, the /absolute/ rank +-- means a word's position in the shortlex sequence of __all__ Dyck words.+-- /For example:/ The (absolute) rank of @(((())))@ is 9, but the relative rank +-- of the same word is 0, since it is the first word of size four.+--+-- \[+-- \begin{array}{lccc}+-- \text{Word} & \text{Size} & \text{Rank} & \text{Relative rank}+-- \\+-- \epsilon & 0 & 0 & 0 \\+-- ⟨⟩ & 1 & 1 & 0 \\+-- ⟨⟨⟩⟩ & 2 & 2 & 0 \\+-- ⟨⟩⟨⟩ & 2 & 3 & 1 \\+-- ⟨⟨⟨⟩⟩⟩ & 3 & 4 & 0 \\+-- ⟨⟨⟩⟨⟩⟩ & 3 & 5 & 1 \\+-- ⟨⟨⟩⟩⟨⟩ & 3 & 6 & 2 \\+-- ⟨⟩⟨⟨⟩⟩ & 3 & 7 & 3 \\+-- ⟨⟩⟨⟩⟨⟩ & 3 & 8 & 4 \\+-- ⟨⟨⟨⟨⟩⟩⟩⟩ & 4 & 9 & 0 \\+-- ⟨⟨⟨⟩⟨⟩⟩⟩ & 4 & 10 & 1 \\+-- \;\;\;\; \vdots & \vdots & \vdots & \vdots+-- \end{array}+-- \]+--+-- If we let \(r(w)\) denote the relative rank of a word \(w\), and \(C_i\) the +-- \(i^{th}\) Catalan number, then the absolute rank \(R(w)\) of \(w\) is given +-- by the formula \( R(w) = r(w) + \sum_{i=0}^{s-1} C_i, \) where \(s\) is the +-- size of \(w\).++-- | See 'size'.+type Size = Integer++-- | Represents the /rank/ of a Dyck word.+type Rank = Integer++-- | Opaque Dyck word type. For functions to build Dyck words, see:+--+-- * 'empty', +-- * 'fromText', +-- * 'fromText'', +-- * 'unrank', +-- * 'unrankRelative', and +-- * 'unrankRelative''.+--+-- Conceptually, every non-empty Dyck word has the form /(a)b/, where /a/ and+-- /b/ are Dyck words. The BNF grammar for this language is given by +-- \( \omega = \epsilon \mid ( \omega ) \omega \).+data DyckWord = DyckWord + { _size :: !Size+ , _absRank :: !Rank+ , _relRank :: !Rank+ , _text :: !Text+ } deriving (Show)++-- | Two Dyck words are considered equal when they have the same /absolute/+-- rank. +-- +-- >>> fromText' "010011000111" == fromText' "xyxxyyxxxyyy"+-- True+instance Eq DyckWord where+ a == b = _absRank a == _absRank b++-- | Dyck words of the same size are ordered lexicographically, and a smaller +-- Dyck word always gets precedence over a bigger one.+--+-- >>> fromText' "0011" < fromText' "0101"+-- True+--+-- >>> fromText' "0101" > fromText' "01"+-- True+instance Ord DyckWord where+ a <= b = _absRank a <= _absRank b++-- | The /empty/ Dyck word.+empty :: DyckWord+empty = DyckWord + { _size = 0+ , _absRank = 0+ , _relRank = 0+ , _text = T.empty } ++-- | The /size/ of a Dyck word is the number of bracket pairs it contains, +-- i.e., half of the length of the word's string representation. Inductively, +-- it can be defined as+--+-- \[ +-- \text{size}\;w = +-- \begin{cases}+-- 0 && \text{if} \; w = \epsilon \\+-- 1 + \text{size}\;u + \text{size}\;v && \text{if} \; w = (u)v. +-- \end{cases}+-- \]+size :: DyckWord -> Size+size = _size++juxtapose :: DyckWord -> DyckWord -> Text+juxtapose a b + | compatible = _text a <> _text b+ | otherwise = _text a <> _text (setAlphabet (firstChar a) (finalChar a) b)+ where+ firstChar = T.head . _text+ finalChar = T.last . _text+ compatible + | 0 == _absRank a = True+ | 0 == _absRank b = True+ | otherwise = firstChar a == firstChar b && finalChar a == finalChar b++-- | Change the alphabet of a Dyck word. An alphabet has two characters, here+-- referred to as the /left/ and /right/ symbol, respectively. For example:+--+-- >>> toText (setAlphabet 'x' 'o' (unrank 55))+-- xoxxoxxooo+setAlphabet :: Char -- ^ Left symbol+ -> Char -- ^ Right symbol+ -> DyckWord + -> DyckWord+setAlphabet a' b' w = w { _text = f `T.map` t }+ where+ t = _text w+ a = T.head t+ b = T.last t+ f c | c == a = a'+ | c == b = b'+ | otherwise = error "not a valid dyck word"++-- | Concatenate two Dyck words. Corresponds to ordinary string concatenation.+--+-- \[ +-- \begin{align}+-- \epsilon +\!\!\!+\;w &= w +-- \\+-- (u)v +\!\!\!+\;w &= (u)[ v +\!\!\!+\; w ]+-- \end{align}+-- \]+--+-- If the two words have different alphabets, the concatenated word will +-- inherit the first word's symbol set.+concatWords :: DyckWord -> DyckWord -> DyckWord+concatWords a b = fromText' (juxtapose a b)++instance Monoid DyckWord where+ mappend = concatWords+ mempty = empty++-- | Return the /absolute/ rank of a Dyck word. That is, its position in the +-- (shortlex) ordered sequence of /all/ Dyck words.+rank :: DyckWord -> Rank+rank = _absRank++-- | Return the /relative/ rank of a Dyck word. +rankRelative :: DyckWord -> Rank+rankRelative = _relRank++-- | Parse a 'Text' value to a 'DyckWord'. The result is wrapped in a 'Maybe', +-- so that the value becomes 'Nothing' if parsing fails. The alphabet is +-- determined by looking at the first and last characters of the input.+fromText :: Text -> Either String DyckWord+fromText t + | T.null t = Right empty+ | odd len = Left "odd length input"+ | a == b = err+ | otherwise = case T.foldr f (Right (0, s, s)) (T.reverse t) of+ Left e -> Left e+ Right (r,_,_) -> Right $ DyckWord + { _size = s+ , _absRank = catalanSum (fromIntegral s) + r+ , _relRank = r+ , _text = t } + where+ a = T.head t+ b = T.last t+ s = fromIntegral (len `div` 2)+ len = T.length t+ err = Left "bad input"+ f c (Right (i, x, y))+ | x > y || x < 0 = err+ | c == a = Right (i, x - 1, y)+ | c == b = Right (i + catalanTriangle y (x - 1), x, y - 1)+ f _ _ = err++-- | Parse a 'Text' value to a 'DyckWord'. Throws an error if parsing fails.+-- This is an unsafe version of 'fromText'.+fromText' :: Text -> DyckWord+fromText' t = + case fromText t of+ Right r -> r + Left _ -> error "not a valid dyck word"++-- | Return a textual representation of a 'DyckWord'.+toText :: DyckWord -> Text+toText = _text++-- | Return the /n/-th Dyck word in the (shortlex) ordered sequence of /all/+-- Dyck words. +unrank :: Rank -> DyckWord +unrank r + | r < 0 = error "rank cannot be negative"+ | otherwise = unrankRelative' s i+ where+ (s, i) = sizeOffs r 0 ++sizeOffs :: Integral a => Integer -> a -> (a, Integer)+sizeOffs n x + | n < c = (x, n)+ | otherwise = sizeOffs (n - c) (x + 1) + where + c = catalan (fromIntegral x)++-- | Return the /n/-th Dyck word, restricted to only words of a given size.+-- Words are lexicographically ordered. The result is wrapped in a 'Maybe', +-- and is equal to 'Nothing' if the given rank is outside of the valid range. +unrankRelative :: Size -> Rank -> Maybe DyckWord +unrankRelative s r + | r < 0 + || r >= catalan s = Nothing+ | otherwise = Just DyckWord + { _size = s+ , _absRank = offset + r+ , _relRank = r+ , _text = t } + where + t = unfoldrN (fromIntegral (2*s)) f (r, s, s)+ offset = catalanSum (fromIntegral s)+ f (i, x, y) + | 0 == y = Nothing + | j >= 0 = Just (')', (j, x, y - 1))+ | otherwise = Just ('(', (i, x - 1, y)) + where + j = i - catalanTriangle y (x - 1) ++-- | Unsafe version of 'unrankRelative'. This function throws an error if the +-- given rank is outside of the valid range. +unrankRelative' :: Size -> Rank -> DyckWord+unrankRelative' s = fromJust . unrankRelative s++-- | Return a lexicographically ordered list with all Dyck words of a specific +-- size.+wordsOfSize :: Size -> [DyckWord]+wordsOfSize = ofSize unrankRelative' ++ofSize :: (Size -> Integer -> b) -> Size -> [b]+ofSize f s = f s <$> [0 .. catalan (fromIntegral s) - 1]
+ src/Math/DyckWord/Binary/Internal.hs view
@@ -0,0 +1,16 @@+module Math.DyckWord.Binary.Internal where++import Math.Combinatorics.Exact.Binomial++catalanTriangle :: Integer -> Integer -> Integer+catalanTriangle _ 0 = 1+catalanTriangle n k = (choose (n + k) (k - 1) * (n - k + 1)) `div` k ++catalanSum :: Int -> Integer+catalanSum = (scanl (+) 0 (catalan <$> [0..]) !!)++catalan :: (Integral a, Integral b) => a -> b+catalan 0 = 1+catalan 1 = 1+catalan 2 = 2+catalan n = let m = fromIntegral n in (2*m) `choose` m `div` (m + 1)
+ tests/Suite.hs view
@@ -0,0 +1,181 @@+{-# LANGUAGE OverloadedStrings #-}+module Main where++import Control.Monad ( forM_ )+import Data.Either ( isLeft )+import Data.Monoid ( (<>) )+import System.Console.ANSI+import System.Exit ( exitFailure )+import System.IO+import Test.Hspec++import Math.DyckWord.Binary+import Math.DyckWord.Binary.Internal++import qualified Data.Text as T++lastN :: Int -> [a] -> [a]+lastN n xs = drop (length xs - n) xs++showN :: Integer -> String+showN n+ | n > 10^30 = "..." ++ lastN 20 (show n) ++ " (huge number)"+ | otherwise = show n++saysThat :: String -> IO a -> IO a+saysThat s action = do+ setCursorColumn 2+ putStr s+ clearFromCursorToLineEnd+ hFlush stdout+ action++resetCursor :: IO ()+resetCursor = do+ setCursorColumn 0+ clearFromCursorToLineEnd++infixl 0 `saysThat` ++makeSure :: Bool -> Expectation+makeSure = shouldBe True ++rankAfterUnrank :: Integer -> IO ()+rankAfterUnrank n = showN n `saysThat` rank (unrank n) `shouldBe` n++checkSize :: Integer -> Integer -> IO ()+checkSize s n = show (s, n) `saysThat` size (unrankRelative' s n) `shouldBe` s++sizeShouldBeHomomorphic :: T.Text -> T.Text -> Expectation+sizeShouldBeHomomorphic a b = size (u <> v) `shouldBe` (size u + size v)+ where+ u = fromText' a+ v = fromText' b++checkIdentity :: Integer -> IO ()+checkIdentity n = show n `saysThat` do + empty <> unrank n `shouldBe` (unrank n)+ unrank n <> empty `shouldBe` (unrank n)++checkAssociativity :: (Integer, Integer, Integer) -> IO ()+checkAssociativity triple@(a, b, c) = show triple `saysThat` p+ where+ p = ((u <> v) <> w) `shouldBe` (u <> (v <> w))+ u = unrank a+ v = unrank b+ w = unrank c++checkWordsOfSizeCatalan :: Integer -> IO ()+checkWordsOfSizeCatalan n = + show c_n ++ " words of size " ++ show n `saysThat` + length (wordsOfSize n) `shouldBe` c_n+ where+ c_n = catalan n++checkWordsOfSizeAgainstUnrank :: Integer -> Integer -> IO ()+checkWordsOfSizeAgainstUnrank i j =+ show (i, j) `saysThat` + wordsOfSize i !! (fromIntegral j) `shouldBe` unrankRelative' i j++main :: IO ()+main = hspec $ do++ describe "unrankRelative" $ do+ it "returns a dyck word with the expected size" $ do+ forM_ [10, 12, 22, 123, 425, 1028] $+ forM_ [1..22] . checkSize + resetCursor++ describe "rank" $ do+ it "is the inverse of unrank" $ do+ forM_ ( [catalan 31..catalan 31+80]+ ++ [catalan 131..catalan 131+192]+ ++ [catalan 431..catalan 431+95]+ ++ [catalan 21..catalan 21+284] + ++ [catalan 11..catalan 11+989] + ++ [0..1000] ) rankAfterUnrank+ resetCursor++ describe "unrankRelative" $ do+ it "returns Nothing for invalid relative rank" $ do+ unrankRelative 0 2 `shouldBe` Nothing+ unrankRelative 1 8 `shouldBe` Nothing+ unrankRelative 3 5 `shouldBe` Nothing+ unrankRelative 1111 (catalan 1111) `shouldBe` Nothing+ unrankRelative 0 (-1) `shouldBe` Nothing+ unrankRelative 5 (-1) `shouldBe` Nothing+ unrankRelative 5 1231231238837431321283123981237123 `shouldBe` Nothing++ describe "empty" $ do+ it "has size 0" $+ size empty `shouldBe` 0+ it "matches the empty Text value" $+ toText empty `shouldBe` T.empty+ it "has rank 0, and relative rank 0" $ do+ rank empty `shouldBe` 0+ rankRelative empty `shouldBe` 0++ describe "Ord" $ do+ it "works as expected" $ do+ makeSure (unrank 100 <= unrank 101) + makeSure (unrank 0 <= unrank 1) + makeSure (unrank 1 > unrank 0) + makeSure (unrank (10^16) > unrank (10^15)) + makeSure $ not (unrank 1235 > unrank 2000) ++ describe "Eq" $ do+ it "works with unrank" $ do+ makeSure (unrank 0 == empty)+ makeSure (unrank 1 == fromText' "()") + makeSure (unrank 2 == fromText' "(())") + makeSure (unrank 3 == fromText' "()()")+ makeSure (unrank 123 == fromText' "(()(())()())") + makeSure (unrank 123 == fromText' "001001101011") ++ it "works with different alphabets" $ do+ makeSure (fromText' "(()(())()())" == fromText' "001001101011") ++ describe "setAlphabet" $ do+ it "replaces the characters in a word's Text value" $ do+ toText (setAlphabet '0' '1' $ unrank 10) `shouldBe` "00010111"+ toText (setAlphabet '(' ')' $ fromText' "0000111101") `shouldBe` "(((())))()"+ toText (setAlphabet '1' '0' $ fromText' "0000111101") `shouldBe` "1111000010"+ toText (setAlphabet 'a' 'b' $ fromText' "xyxyxxyy") `shouldBe` "ababaabb"++ describe "concatWords" $ do+ it "returns a word with size equal to the sum of the sizes of the inputs" $ do+ sizeShouldBeHomomorphic "(()())" "(((())))"+ sizeShouldBeHomomorphic "ababaaaabbbb" "(((())))"+ sizeShouldBeHomomorphic "" "(((())))"++ it "works with different alphabets" $ do+ concatWords (fromText' "()()") (fromText' "aaaabbbb") `shouldBe` (fromText' "()()(((())))")+ concatWords (fromText' "()()") (fromText' "aaaabbbb") `shouldBe` (fromText' "010100001111")++ it "satisfies the identity law" $ do+ forM_ [0, 20..33350] checkIdentity+ resetCursor++ it "is associative" $ do+ forM_ [(a, b, c) | a <- [0, 20, 1000], b <- [0..300], c <- [0, 50..200]] checkAssociativity+ resetCursor++ describe "wordsOfSize" $ do+ it "matches the Catalan numbers" $ do+ forM_ [0..17] checkWordsOfSizeCatalan+ resetCursor++ it "matches the result of unrankRelative'" $ do+ forM_ [8..12] $ forM_ [8..1125] . checkWordsOfSizeAgainstUnrank+ resetCursor++ describe "fromText" $ do+ it "should return a Left value on bad input" $ do+ fromText "(((" `shouldSatisfy` isLeft+ fromText "((()" `shouldSatisfy` isLeft+ fromText "((())" `shouldSatisfy` isLeft+ fromText "))(" `shouldSatisfy` isLeft+ fromText "))()" `shouldSatisfy` isLeft+ fromText "(()))" `shouldSatisfy` isLeft+ fromText "((x)" `shouldSatisfy` isLeft+