The dyckword package

[ Tags: bsd3, library, math ] [ Propose Tags ]

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.


[Skip to Readme]

Properties

Versions 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.1.0.4
Dependencies base (==4.*), exact-combinatorics, text [details]
License BSD3
Copyright 2017 Johannes Hildén
Author Johannes Hildén
Maintainer hildenjohannes@gmail.com
Category Math
Home page https://github.com/laserpants/dyckword#readme
Source repository head: git clone https://github.com/johanneshilden/dyckword
Uploaded Mon May 1 11:43:02 UTC 2017 by arbelos
Updated Mon Oct 2 12:58:12 UTC 2017 by arbelos to revision 1   [What is this?]
Distributions NixOS:0.1.0.4
Downloads 851 total (366 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-05-01 [all 1 reports]
Hackage Matrix CI

Modules

[Index]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for dyckword-0.1.0.4

[back to package description]

dyckword Build Status

Documentation

See Hackage.

Install

cabal install dyckword

Examples

λ> :set -XOverloadedStrings 

λ> toText $ unrank (10^889)
(()((()((())(()()((()()()((()((())())(()(()()()(())()()()))((()()))())(()()(())((((()())((((()()(()()(())((()(())
((((())))))(((((((()((())()()((())))()(()((())))(((())))))()())()()()()))(()))()(())(((())))))))()(())))()))()(()
(((()())((()())()(()())())))())))))))))(((((()((())()))((()())()(((()()()(()(()))))((())((()))))((()())())())((()
(()()))))))())()((())((((()(()(()()()((())((((((((()(((((((((()(())()(()()()((()))))()((())(((())(()())())((()())
((()(()))())()())(()))))))()((()((())(())())(()))))()())()()(())(()()))()))((((()())(()()()))(())))((())))))())((
()))))))))()(())((()((((((())(())))()(()(((((()()()))())))())(((())(()((()(((((((())())((())(()))((()(()()(()(()(
())()(()))()()(((()(((()))(())))(()))((()))()(()))((())(()()()((()()())))(()))())(()))))()()))((())()())())(()())
)))((()()))(((()))(()))((()))))())())()(()(()))())((())))()()()()(()())()(())())(((((()))())()(()())()()(((((())(
)))(()(()))(((()()()())()()())())())(((((()())))))()))())())))(()()))()))()()))))())()(((((((())()(()(()))))(((((
((((((()()((()())())(())))())))()(()))((((()))()()((()()()(()(((()))((())(((((((()()((())))())(()()(((()(()))))))
))))()()((()(()()))())(())()(())(((()((((())))((()(((())(((()())))))(((((()))()(()((()()((()())())(((())())(())()
)(()))())((((()(()())()(())(()(((()())()(()))()(()((()(((())))(())(()())))())(())()))((((()()(()))()()((((())()((
((((())())())(()()((()(()())))))())())())))()))()))))((())((()))()()))((()()))(((()())()()()))()())))(((())))))))
(((((())())()(())))((()()())()((((()())((((((((()(()()))))(()(())))))(())()(()((()()))(((((()(((())(((((((()))(((
))(()(()(()()()(((())())))()((((((((())((((()((()(((((()))(())((()))))())(()(()())))((((())(()((()()))(((((()((((
(((())()())())(()))()))()(()(()(((((()))(()))))))()())()))))()()())())((()(())))((())(((((((()()))((()()))))(((((
(((()())()()))()())()(())()(()()(()))))))()))))()))())((())))))((()())(()(()))()()))()(())())((()())()))()())(())
())(()()))())(()()))(()()()())()()())((())))))()(()())(()))()()())))(((())()(()()((()()))))))())((((((()()())))()
())())((()())(((((()()(((((())()()()((()()(((((()((()(()())))(()(())(()()(()()(()(())))))()()(()())(()()))((())))
))(())()))((()(()())((()))((()()()()()())))))())))()))()(((((((())))))))((())))))(((()()()())()()()()(()(()))(()(
()())()(()()(()()(((())(())))))()((()))((()))(((((()(()()(()(((()((())))(()()(()()()(()((())()((()))()))(()()))))
)()())((((())())(())()()()()((((()))))))((()()((())((()((((()())()))()((()((())())()()(((())()(((()(((((()((()))(
)))))(())((()())()(()(((())))((((()(((()()())((()()()())())((((()(((()))()((((()(()))(()(((()()(()))())))())()(((
()((()((())))(())))))))(()())()))()())())()))())()))())))))(((())))))))(()))((()())((())()())((()))))))()(()))())
)(())))))))()())())))))))(()()(((())))(())((()(()()))(()()()()))(()()((()()()())))(()(()(()()))(())))(()())((())(
)((()((()))(()()(()(()))(())))))))()()))())))))))))(()()))))(()))))())()(()()))()))((())))))()()()(()))))()(()(()
((()))()(()(()(()))))()))())))()

λ> size $ unrank (10^989)
1651

λ> rank $ fromText' "(())()(((())))"
480

λ> rank $ fromText' "ooxxoxooooxxxx"
480

λ> fromText "aaaa"
Left "bad input"

λ> fromText "()()" > fromText "(())"
True

λ> mapM_ print (toText <$> wordsOfSize 5)
"((((()))))"
"(((()())))"
"(((())()))"
"(((()))())"
"(((())))()"
"((()(())))"
"((()()()))"
"((()())())"
"((()()))()"
"((())(()))"
"((())()())"
"((())())()"
"((()))(())"
"((()))()()"
"(()((())))"
"(()(()()))"
"(()(())())"
"(()(()))()"
"(()()(()))"
"(()()()())"
"(()()())()"
"(()())(())"
"(()())()()"
"(())((()))"
"(())(()())"
"(())(())()"
"(())()(())"
"(())()()()"
"()(((())))"
"()((()()))"
"()((())())"
"()((()))()"
"()(()(()))"
"()(()()())"
"()(()())()"
"()(())(())"
"()(())()()"
"()()((()))"
"()()(()())"
"()()(())()"
"()()()(())"
"()()()()()"

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. If we take this alphabet to be the set Σ = {(, )}, then 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.

λ> take 15 $ (length . wordsOfSize) <$> [0..]
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]