-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A practical arithmetic encoding (aka Godel numbering) library. -- -- A library providing tools and various schemes for encoding arbitrary -- datatypes as natural numbers. The underlying theory is that of -- isomorphisms with the natural numbers (known as Godel numbering). The -- library provides functionality for defining multiple such encodings -- for a given datatype, as well as a collection of stock encodings and -- combinators which can be used to build more complex encodings. -- -- This has various uses, among them binary serialization/deserialization -- and enumeration testing. @package arith-encode @version 1.0.1 -- | Definition of Encoding, and a set of fundamental -- Encodings and constructions. -- -- This module contains the basic definitions for Encodings. It -- defines the Encoding type, the functions for creating an -- Encoding, and a set of stock constructions. -- -- The Encoding type is encapsulated; the functions -- mkEncoding (and the variants thereof) are used to synthetically -- construct an encoding from the fundamental operations. -- -- The IllegalArgument exception datatype, as well as the -- fundamental operations are also defined here. -- -- In addition to this, a set of basic definitions and constructions are -- provided. These definitions should be suitable for defining -- Encodings for most algebraic datatypes without having to -- manually write encode/decode implementations. module Data.ArithEncode.Basic -- | Type for an encoding. The structure of this type is deliberately -- hidden from users. Use the mkEncoding functions to construct -- Encodings, and the seven functions to use them. data Encoding ty -- | Create an encoding from all the necessary components. mkEncoding :: (ty -> Integer) -> (Integer -> ty) -> Maybe Integer -> (ty -> Bool) -> Encoding ty -- | Create an infinite-sized encoding. This variant does not need a size. mkInfEncoding :: (ty -> Integer) -> (Integer -> ty) -> (ty -> Bool) -> Encoding ty -- | An exception to be thrown if an illegal argument is given to -- encode, decode. data IllegalArgument IllegalArgument :: !String -> IllegalArgument -- | Encode a ty as a positive Integer (ie. a natural -- number). -- -- If the given ty is not in the domain of the Encoding -- (meaning, inDomain returns False), the underlying -- implementation may throw IllegalArgument. However, this -- is not strictly required; therefore, do not rely on -- IllegalArgument being thrown. encode :: Encoding ty -> ty -> Integer -- | Decode a ty from a positive Integer (ie. a natural -- number). -- -- If the given Integer is out of bounds (ie. it is bigger than -- size), the underlying implementation may throw -- IllegalArgument. However, this not strictly required; -- therefore, do not rely on IllegalArgument being thrown. decode :: Encoding ty -> Integer -> ty -- | Get the size of an Encoding, or Nothing if it is -- infinite. size :: Encoding ty -> Maybe Integer -- | Indicate whether or not a value is in the domain of the encoding. inDomain :: Encoding ty -> ty -> Bool -- | The identity encoding. Maps every positive Integer to itself. -- -- Note: only positive integers are in the domain of this encoding. For -- all an encoding whose domain is all integers, use integral. identity :: Encoding Integer -- | A singleton encoding. Maps a singular value to 0. singleton :: Eq ty => ty -> Encoding ty -- | An encoding of all integers. -- -- Note: this is not an identity mapping. integral :: Integral n => Encoding n -- | Build an encoding from a finite range of Integrals. -- -- Both the upper and lower bounds are inclusive. This allows an -- Encoding to be created for bounded integer datatypes, such as -- Int8. interval :: Integral n => n -> n -> Encoding n -- | Build an encoding from a list of items with a Hashable -- instance. fromHashableList :: forall ty. (Hashable ty, Ord ty) => [ty] -> Encoding ty -- | Build an encoding from a list of items with an Ord instance. fromOrdList :: forall ty. Ord ty => [ty] -> Encoding ty -- | Wrap an encoding using a pair of functions. These functions must also -- define an isomorphism. wrap :: (a -> Maybe b) -> (b -> Maybe a) -> Encoding b -> Encoding a -- | Generate an encoding for Maybe ty from an inner encoding for -- ty. optional :: Encoding ty -> Encoding (Maybe ty) -- | The dual of optional. This construction assumes that -- Nothing maps to 0, and removes it from the input -- domain. -- -- Using this construction on encodings for Maybe ty which are -- not produced by optional may have unexpected results. mandatory :: Encoding (Maybe ty) -> Encoding ty -- | Removes the mapping to 0 (ie. the first mapping). This has -- the same effect as exclude [x], where x is the value -- that maps to 0. It is also similar to mandatory, -- except that it does not change the base type. nonzero :: Encoding ty -> Encoding ty -- | Removes the mapping to the items in the list. The resulting -- encode, decode, and highestIndex are -- O(length excludes), so this should only be used with a very -- short excludes list. exclude :: [ty] -> Encoding ty -> Encoding ty -- | Combine two encodings into a single encoding that returns an -- Either of the two types. either :: Encoding ty1 -> Encoding ty2 -> Encoding (Either ty1 ty2) -- | Combine a set of encodings with the result type into a single encoding -- which represents the disjoint union of the components. union :: forall ty. [Encoding ty] -> Encoding ty -- | Take encodings for two datatypes A and B, and build an encoding for a -- pair (A, B). pair :: Encoding ty1 -> Encoding ty2 -> Encoding (ty1, ty2) -- | Construct an encoding for a 3-tuple from the encodings for the three -- components. This is actually just a wrapper around pair. triple :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding (ty1, ty2, ty3) -- | Construct an encoding for a 4-tuple from the encodings for the four -- components. This is actually just a wrapper around pair. quad :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding (ty1, ty2, ty3, ty4) -- | Construct an encoding for a 5-tuple from the encodings for the five -- components. This is actually just a wrapper around pair. quint :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding (ty1, ty2, ty3, ty4, ty5) -- | Construct an encoding for a 6-tuple from the encodings for the six -- components. This is actually just a wrapper around pair. sextet :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding ty6 -> Encoding (ty1, ty2, ty3, ty4, ty5, ty6) -- | Construct an encoding for a 7-tuple from the encodings for the seven -- components. This is actually just a wrapper around pair. septet :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding ty6 -> Encoding ty7 -> Encoding (ty1, ty2, ty3, ty4, ty5, ty6, ty7) -- | Construct an encoding for an 8-tuple from the encodings for the eight -- components. This is actually just a wrapper around pair. octet :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding ty6 -> Encoding ty7 -> Encoding ty8 -> Encoding (ty1, ty2, ty3, ty4, ty5, ty6, ty7, ty8) -- | Construct an encoding for a 9-tuple from the encodings for the nine -- components. This is actually just a wrapper around pair. nonet :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding ty6 -> Encoding ty7 -> Encoding ty8 -> Encoding ty9 -> Encoding (ty1, ty2, ty3, ty4, ty5, ty6, ty7, ty8, ty9) -- | Construct an encoding for a 10-tuple from the encodings for the ten -- components. This is actually just a wrapper around pair. dectet :: Encoding ty1 -> Encoding ty2 -> Encoding ty3 -> Encoding ty4 -> Encoding ty5 -> Encoding ty6 -> Encoding ty7 -> Encoding ty8 -> Encoding ty9 -> Encoding ty10 -> Encoding (ty1, ty2, ty3, ty4, ty5, ty6, ty7, ty8, ty9, ty10) -- | Take an Encoding for elements and a length and produce an -- Encoding for lists of exactly that length. -- -- This differs from boundedSeq in that the resulting list is -- exactly the given length, as opposed to upper-bounded by it. power :: Integer -> Encoding ty -> Encoding [ty] -- | Build an encoding for finite sets of values of a given datatype -- from an encoding for that datatype. -- -- Note: this encoding and its variants can produce very large numbers -- for a very small set. set :: Ord ty => Encoding ty -> Encoding (Set ty) -- | Build an encoding for finite sets of values of a given datatype -- from an encoding for that datatype. Similar to set, but uses -- HashSet instead hashSet :: (Hashable ty, Ord ty) => Encoding ty -> Encoding (HashSet ty) -- | Construct an encoding for finite sequences of a type from an -- encoding for values of that type. -- -- Note: This encoding can produce very large numbers for short -- sequences. seq :: Encoding ty -> Encoding [ty] -- | Construct an encoding for sequences whose length is bounded by a given -- value from an encoding for elements of the sequence. boundedSeq :: Integer -> Encoding ty -> Encoding [ty] -- | Take a function which takes a self-reference and produces a recursive -- encoding, and produce the fixed-point encoding. recursive :: (Encoding ty -> Encoding ty) -> Encoding ty -- | A recursive construction for two mutually-recursive constructions. recursive2 :: ((Encoding ty1, Encoding ty2) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2) -> Encoding ty2) -> (Encoding ty1, Encoding ty2) -- | A recursive construction for three mutually-recursive constructions. recursive3 :: ((Encoding ty1, Encoding ty2, Encoding ty3) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3) -> Encoding ty3) -> (Encoding ty1, Encoding ty2, Encoding ty3) -- | A recursive construction for four mutually-recursive constructions. recursive4 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4) -> Encoding ty4) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4) -- | A recursive construction for five mutually-recursive constructions. recursive5 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -> Encoding ty5) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5) -- | A recursive construction for six mutually-recursive constructions. recursive6 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty5) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -> Encoding ty6) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6) -- | A recursive construction for seven mutually-recursive constructions. recursive7 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty5) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty6) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -> Encoding ty7) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7) -- | A recursive construction for eight mutually-recursive constructions. recursive8 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty5) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty6) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty7) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -> Encoding ty8) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8) -- | A recursive construction for nine mutually-recursive constructions. recursive9 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty5) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty6) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty7) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty8) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -> Encoding ty9) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9) -- | A recursive construction for ten mutually-recursive constructions. recursive10 :: ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty1) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty2) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty3) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty4) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty5) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty6) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty7) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty8) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty9) -> ((Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) -> Encoding ty10) -> (Encoding ty1, Encoding ty2, Encoding ty3, Encoding ty4, Encoding ty5, Encoding ty6, Encoding ty7, Encoding ty8, Encoding ty9, Encoding ty10) instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.ArithEncode.Basic.BinTree key val) instance GHC.Show.Show Data.ArithEncode.Basic.IllegalArgument instance GHC.Exception.Type.Exception Data.ArithEncode.Basic.IllegalArgument -- | Facilities for using Encodings as binary serializers. The -- resulting binary format is, for the most part, determined by the -- Encoding, and therefore is within a constant factor of -- succintness. -- -- In all cases, little-endian byte ordering is used in order to allow -- for very large data to be read in an decoded lazily. (Note: Haskell's -- libraries do not provide support for this functionality at this time). -- -- For finite Encodings, the binary format is just the -- little-endian encoding of the encoded value, using as few bytes as -- necessary to represent the largest encoded value. -- -- For infinite Encodings, the binary format includes a length -- field for most values. The current encoding uses length fields of -- different sizes, depending on the size of the encoded value. module Data.ArithEncode.Binary -- | Use an Encoding to extract a ty from binary data. getWithEncoding :: Encoding ty -> Get ty -- | Use an Encoding to write a ty out as binary data. putWithEncoding :: Encoding ty -> ty -> Put -- | Derived encodings for standard datatypes. -- -- This module contains a number of useful constructions which can be -- defined using the constructions from Basic. module Data.ArithEncode.Util -- | An encoding that produces (). unit :: Encoding () -- | An empty encoding, which contains no mappings. void :: Encoding b -- | Build an encoding that produces non-empty sequences from an encoding -- for the elements of the sequence. nonEmptySeq :: Encoding ty -> Encoding [ty] -- | Build an encoding for lists of Maybes, where the last element -- of the list is always guaranteed not to be Nothing. This is -- useful for building function encodings. nonEmptyOptionSeq :: Encoding ty -> Encoding [Maybe ty] -- | Build an encoding that produces non-empty sets from an encoding for -- the elements of the set. nonEmptySet :: Ord ty => Encoding ty -> Encoding (Set ty) -- | Build an encoding that produces non-empty hash sets from an encoding -- for the elements of the set. nonEmptyHashSet :: (Hashable ty, Ord ty) => Encoding ty -> Encoding (HashSet ty) -- | Build an encoding that produces a (finite partial) function from one -- type to another. This function is represented using a Map. function :: Ord keyty => Encoding keyty -> Encoding valty -> Encoding (Map keyty valty) -- | Build an encoding that produces a (finite partial) function from one -- type to another. This function is represented using a -- HashMap. functionHashable :: (Ord keyty, Hashable keyty) => Encoding keyty -> Encoding valty -> Encoding (HashMap keyty valty) -- | Build an encoding that produces relations between two types. These -- relations are represented as Maps from the first type to -- Sets of the second. relation :: (Ord keyty, Ord valty) => Encoding keyty -> Encoding valty -> Encoding (Map keyty (Set valty)) -- | Build an encoding that produces relations between two types. These -- relations are represented as HashMaps from the first type to -- HashSets of the second. relationHashable :: (Hashable keyty, Ord keyty, Hashable valty, Ord valty) => Encoding keyty -> Encoding valty -> Encoding (HashMap keyty (HashSet valty)) -- | Build an encoding that produces trees from an encoding for the node -- labels. tree :: Encoding ty -> Encoding (Tree ty) -- | ArithEncode is a library that provides tools for defining arithmetic -- encodings for arbitrary datatypes. The library is designed so that -- multiple encoding schemes can be defined for a given datatype, and a -- given encoding need not encode all possible instances of the datatype. -- -- An Encoding is an object which is passed as the first argument -- to seven different functions. The primary function of an -- Encoding is manifest in the encode and decode -- functions, which define an isomorphism between the datatype and the -- natural numbers (or a bounded set thereof), represented using -- Integers. The encode and decode functions have -- the following properties: -- -- -- -- The inDomain function indicates whether or not a given value is -- in the domain of the encoding. Passing a value v where -- inDomain enc v == False into any other function may -- result in an IllegalArgument exception. (For performance -- reasons, encodings are not strictly required to throw -- IllegalArgument, but the result should not be considered -- valid if they do not throw the exception). -- -- This library provides a large collection of combinators for -- constructing more complex Encodings out of simpler ones. The -- provided combinators should be appropriate for constructing -- Encodings for most datatypes. -- -- As an example, the following definition creates an Encoding for -- the Tree Integer type: -- -- 
--   tree :: Encoding (Tree Integer)
--   tree =
--     let
--       ...
--       nodeEncoding nodeenc =
--         wrap unmakeNode makeNode (pair interval (seq nodeenc))
--     in
--       recursive nodeEncoding
--
-- -- In this example, the makeNode and unmakeNode -- functios are simply "glue"; their definitions are -- -- 
--   makeNode (label, children) =
--     Node { rootLabel = label, subForest = children }
--   
--   unmakeNode Node { rootLabel = label, subForest = children } =
--     Just (label, children)
--
-- -- The resulting Encoding maps any Tree Integer to a -- unique Integer value. -- -- Encodings have a number of practical uses. First, all -- Encodings in this library satisfy a completeness -- property, which guarantees that they map each value to a finite -- natural number (or in the case of constructions on Encodings, -- they preserve completeness). Hence, they can be used as an enumeration -- procedure for their underlying datatype. -- -- Second, as Encodings define an isomorphism to the natural -- numbers, they provide an efficient binary encode/decode procedure in -- theory. In practice, the techniques used to guarantee the completeness -- property may result in long encodings of some types (particularly -- sequences). Also, knowledge of the distribution of the domain is -- necessary in order to achieve the most succinct possible encoding. module Data.ArithEncode