Index of /~nad/listings/lib-0.2

[ICO]NameLast modifiedSizeDescription

[DIR]Parent Directory   -  
[TXT]Agda.css 07-Jul-2009 23:35 1.0K 
[TXT]Data.Empty1.html 07-Jul-2009 23:35 1.7K 
[TXT]Data.Unit1.html 07-Jul-2009 23:35 1.7K 
[TXT]Data.Empty.html 07-Jul-2009 23:35 2.8K 
[TXT]Size.html 07-Jul-2009 23:35 3.4K 
[TXT]Data.Bool.Show.html 07-Jul-2009 23:34 3.4K 
[TXT]Data.Maybe.Core.html 07-Jul-2009 23:34 3.7K 
[TXT]Relation.Binary.Part..>07-Jul-2009 23:34 4.1K 
[TXT]Algebra.RingSolver.S..>07-Jul-2009 23:35 4.3K 
[TXT]Algebra.FunctionProp..>07-Jul-2009 23:35 4.8K 
[TXT]Category.Monad.Ident..>07-Jul-2009 23:35 5.1K 
[TXT]Relation.Binary.Stri..>07-Jul-2009 23:34 5.1K 
[TXT]Relation.Binary.EqRe..>07-Jul-2009 23:35 5.6K 
[TXT]Relation.Nullary.Cor..>07-Jul-2009 23:35 6.3K 
[TXT]Category.Applicative..>07-Jul-2009 23:35 6.3K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:35 6.8K 
[TXT]Category.Functor.html 07-Jul-2009 23:35 7.1K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:35 8.0K 
[TXT]Relation.Nullary.Pro..>07-Jul-2009 23:34 8.3K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:34 8.6K 
[TXT]Coinduction.html 07-Jul-2009 23:35 8.6K 
[TXT]Data.Star.Fin.html 07-Jul-2009 23:35 8.8K 
[TXT]Relation.Binary.Simp..>07-Jul-2009 23:35 8.8K 
[TXT]Data.Star.List.html 07-Jul-2009 23:35 9.3K 
[TXT]Relation.Binary.Cons..>07-Jul-2009 23:35 9.6K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:35 9.8K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:34 9.9K 
[TXT]Data.Conat.html 07-Jul-2009 23:35 10K 
[TXT]Data.Sign.html 07-Jul-2009 23:34 11K 
[TXT]Data.Sign.Properties..>07-Jul-2009 23:35 11K 
[TXT]Data.Nat.Show.html 07-Jul-2009 23:35 11K 
[TXT]Induction1.Nat.html 07-Jul-2009 23:35 11K 
[TXT]Data.DifferenceNat.html07-Jul-2009 23:35 12K 
[TXT]Data.Integer.Divisib..>07-Jul-2009 23:35 13K 
[TXT]Foreign.Haskell.html 07-Jul-2009 23:34 13K 
[TXT]Category.Monad.html 07-Jul-2009 23:34 14K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:34 14K 
[TXT]IO.Primitive.html 07-Jul-2009 23:35 14K 
[TXT]Relation.Nullary.Sum..>07-Jul-2009 23:35 14K 
[TXT]Data.Char.html 07-Jul-2009 23:34 15K 
[TXT]Induction.WellFounde..>07-Jul-2009 23:35 16K 
[TXT]Induction1.WellFound..>07-Jul-2009 23:35 16K 
[TXT]Relation.Unary1.html 07-Jul-2009 23:34 16K 
[TXT]Data.BoundedVec.Inef..>07-Jul-2009 23:35 18K 
[TXT]Data.Star.Nat.html 07-Jul-2009 23:35 18K 
[TXT]Data.Star.Environmen..>07-Jul-2009 23:35 19K 
[TXT]Data.Cofin.html 07-Jul-2009 23:35 19K 
[TXT]Relation.Binary.Orde..>07-Jul-2009 23:35 19K 
[TXT]Relation.Binary.Preo..>07-Jul-2009 23:34 20K 
[TXT]README.Nat.html 07-Jul-2009 23:35 20K 
[TXT]Algebra.Props.Lattic..>07-Jul-2009 23:34 20K 
[TXT]Data.Unit.html 07-Jul-2009 23:34 22K 
[TXT]Data.Vec1.html 07-Jul-2009 23:35 23K 
[TXT]Data.Fin.Substitutio..>07-Jul-2009 23:34 24K 
[TXT]Induction1.html 07-Jul-2009 23:34 24K 
[TXT]Induction.html 07-Jul-2009 23:35 24K 
[TXT]Data.AVL.Sets.html 07-Jul-2009 23:34 25K 
[TXT]Algebra.Morphism.html 07-Jul-2009 23:35 25K 
[TXT]Data.String.html 07-Jul-2009 23:35 26K 
[TXT]Relation.Nullary.Dec..>07-Jul-2009 23:35 27K 
[TXT]Data.Fin.Subset.html 07-Jul-2009 23:35 27K 
[TXT]Category.Applicative..>07-Jul-2009 23:34 28K 
[TXT]Data.Star.BoundedVec..>07-Jul-2009 23:35 28K 
[TXT]Data.Sum.html 07-Jul-2009 23:35 28K 
[TXT]Data.Bool.html 07-Jul-2009 23:35 29K 
[TXT]Data.Star.Vec.html 07-Jul-2009 23:35 30K 
[TXT]Relation.Nullary.html 07-Jul-2009 23:34 31K 
[TXT]Data.List1.html 07-Jul-2009 23:35 31K 
[TXT]Algebra.Operations.html07-Jul-2009 23:35 32K 
[TXT]Category.Monad.Index..>07-Jul-2009 23:35 32K 
[TXT]Data.DifferenceList...>07-Jul-2009 23:35 33K 
[TXT]Algebra.Props.Abelia..>07-Jul-2009 23:34 34K 
[TXT]README.html 07-Jul-2009 23:35 34K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:35 35K 
[TXT]Data.DifferenceVec.html07-Jul-2009 23:34 36K 
[TXT]Data.BoundedVec.html 07-Jul-2009 23:35 38K 
[TXT]Induction.Lexicograp..>07-Jul-2009 23:35 38K 
[TXT]Algebra.Props.Group...>07-Jul-2009 23:35 38K 
[TXT]Category.Monad.Conti..>07-Jul-2009 23:35 38K 
[TXT]Algebra.Props.Ring.html07-Jul-2009 23:34 42K 
[TXT]Data.List.NonEmpty.P..>07-Jul-2009 23:35 43K 
[TXT]Data.List.All.html 07-Jul-2009 23:35 43K 
[TXT]Data.List.Equality.html07-Jul-2009 23:34 44K 
[TXT]Relation.Binary.Refl..>07-Jul-2009 23:34 45K 
[TXT]Data.AVL.IndexedMap...>07-Jul-2009 23:34 45K 
[TXT]Data.Product.Record...>07-Jul-2009 23:35 45K 
[TXT]Data.List.All.Proper..>07-Jul-2009 23:34 45K 
[TXT]Induction.Nat.html 07-Jul-2009 23:35 46K 
[TXT]Algebra.RingSolver.A..>07-Jul-2009 23:35 46K 
[TXT]Algebra.Props.Distri..>07-Jul-2009 23:34 46K 
[TXT]Data.Fin.Subset.Prop..>07-Jul-2009 23:35 48K 
[TXT]Relation.Binary.NonS..>07-Jul-2009 23:34 48K 
[TXT]IO.html 07-Jul-2009 23:35 48K 
[TXT]Relation.Binary.Prop..>07-Jul-2009 23:35 49K 
[TXT]Relation.Binary.Func..>07-Jul-2009 23:34 49K 
[TXT]Category.Monad.Parti..>07-Jul-2009 23:35 49K 
[TXT]Relation.Unary.html 07-Jul-2009 23:35 51K 
[TXT]Data.Product1.html 07-Jul-2009 23:35 52K 
[TXT]Data.Sets.html 07-Jul-2009 23:35 56K 
[TXT]Data.Map.html 07-Jul-2009 23:35 57K 
[TXT]Algebra.FunctionProp..>07-Jul-2009 23:35 57K 
[TXT]Data.Digit.html 07-Jul-2009 23:35 61K 
[TXT]Data.Rational.html 07-Jul-2009 23:35 62K 
[TXT]Data.Product.html 07-Jul-2009 23:35 63K 
[TXT]Relation.Nullary.Neg..>07-Jul-2009 23:34 65K 
[TXT]Data.Vec.N-ary1.html 07-Jul-2009 23:34 67K 
[TXT]Relation.Binary.Stri..>07-Jul-2009 23:35 67K 
[TXT]Data.Vec.Equality.html 07-Jul-2009 23:35 68K 
[TXT]Data.Star.Pointer.html 07-Jul-2009 23:34 71K 
[TXT]Category.Monad.State..>07-Jul-2009 23:35 71K 
[TXT]Data.Star.Decoration..>07-Jul-2009 23:35 72K 
[TXT]Data.Fin.Substitutio..>07-Jul-2009 23:34 73K 
[TXT]Data.Maybe.html 07-Jul-2009 23:35 74K 
[TXT]Data.Stream.html 07-Jul-2009 23:35 75K 
[TXT]Data.Nat.DivMod.html 07-Jul-2009 23:35 77K 
[TXT]Data.Vec.N-ary.html 07-Jul-2009 23:35 78K 
[TXT]Data.Function.html 07-Jul-2009 23:35 79K 
[TXT]Data.Integer.Propert..>07-Jul-2009 23:35 80K 
[TXT]Data.Star.html 07-Jul-2009 23:35 82K 
[TXT]Data.Fin.Substitutio..>07-Jul-2009 23:34 83K 
[TXT]Relation.Binary.On.html07-Jul-2009 23:34 84K 
[TXT]Relation.Binary.Cons..>07-Jul-2009 23:34 84K 
[TXT]Relation.Binary.html 07-Jul-2009 23:35 85K 
[TXT]Everything.html 07-Jul-2009 23:35 85K 
[TXT]Data.Nat.LCM.html 07-Jul-2009 23:34 90K 
[TXT]Data.Star.Properties..>07-Jul-2009 23:35 92K 
[TXT]Data.Nat.Coprimality..>07-Jul-2009 23:35 96K 
[TXT]Relation.Binary.Core..>07-Jul-2009 23:35 98K 
[TXT]Data.Fin.html 07-Jul-2009 23:35 103K 
[TXT]Data.List.Any.html 07-Jul-2009 23:35 108K 
[TXT]Data.List.NonEmpty.html07-Jul-2009 23:35 108K 
[TXT]Data.Nat.html 07-Jul-2009 23:34 113K 
[TXT]Data.Fin.Props.html 07-Jul-2009 23:35 117K 
[TXT]Relation.Binary.Prod..>07-Jul-2009 23:35 118K 
[TXT]Relation.Nullary.Uni..>07-Jul-2009 23:34 118K 
[TXT]Relation.Binary.Hete..>07-Jul-2009 23:35 120K 
[TXT]Relation.Binary.Flip..>07-Jul-2009 23:35 120K 
[TXT]Data.Covec.html 07-Jul-2009 23:35 122K 
[TXT]Data.Colist.html 07-Jul-2009 23:35 122K 
[TXT]Data.Vec.Properties...>07-Jul-2009 23:35 122K 
[TXT]Data.Fin.Dec.html 07-Jul-2009 23:35 128K 
[TXT]Data.Nat.GCD.html 07-Jul-2009 23:35 131K 
[TXT]Algebra.html 07-Jul-2009 23:35 132K 
[TXT]Data.Nat.Divisibilit..>07-Jul-2009 23:34 134K 
[TXT]Algebra.RingSolver.L..>07-Jul-2009 23:35 144K 
[TXT]Data.Bool.Properties..>07-Jul-2009 23:34 149K 
[TXT]Relation.Binary.Prod..>07-Jul-2009 23:34 152K 
[TXT]Data.Integer.html 07-Jul-2009 23:35 157K 
[TXT]Algebra.Structures.html07-Jul-2009 23:35 157K 
[TXT]Data.Vec.html 07-Jul-2009 23:34 165K 
[TXT]Data.Bin.html 07-Jul-2009 23:34 172K 
[TXT]Data.List.html 07-Jul-2009 23:35 179K 
[TXT]Algebra.RingSolver.html07-Jul-2009 23:35 194K 
[TXT]Relation.Binary.Prod..>07-Jul-2009 23:35 195K 
[TXT]Data.List.Countdown...>07-Jul-2009 23:35 195K 
[TXT]Data.Graph.Acyclic.html07-Jul-2009 23:35 198K 
[TXT]Data.List.Properties..>07-Jul-2009 23:35 203K 
[TXT]Data.AVL.html 07-Jul-2009 23:34 215K 
[TXT]Data.Nat.GCD.Lemmas...>07-Jul-2009 23:34 225K 
[TXT]Relation.Binary.Sum...>07-Jul-2009 23:35 273K 
[TXT]Data.List.Any.Proper..>07-Jul-2009 23:35 401K 
[TXT]Data.Nat.Properties...>07-Jul-2009 23:35 429K 
[TXT]Algebra.Props.Boolea..>07-Jul-2009 23:35 494K 
[TXT]Data.Fin.Substitutio..>07-Jul-2009 23:35 497K 

README
module README where

------------------------------------------------------------------------
-- The Agda "standard" library, version 0.2
--
-- Author: Nils Anders Danielsson, with contributions from
-- Jean-Philippe Bernardy, Samuel Bronson, Liang-Ting Chen, Dan Doel,
-- Patrik Jansson, Shin-Cheng Mu, and Ulf Norell
------------------------------------------------------------------------

-- This version of the library has been tested using Agda 2.2.4.

-- Note that no guarantees are currently made about forwards or
-- backwards compatibility, the library is still at an experimental
-- stage.

-- To make use of the library, add the path to the library’s root
-- directory (src) to the Agda search path, either using the
-- --include-path flag or by customising the Emacs mode variable
-- agda2-include-dirs (M-x customize-group RET agda2 RET).

-- To compile programs using some of the IO functions you need to
-- install the Haskell package utf8-string (available from Hackage).

-- Contributions to this library are welcome. Please send
-- contributions in the form of darcs patches (run
-- darcs send --output <patch file> and attach the patch file to an
-- email), and include a statement saying that you agree to release
-- your library patches under the library's licence.

------------------------------------------------------------------------
-- Module hierarchy
------------------------------------------------------------------------

-- The top-level module names of the library are currently allocated
-- as follows:
--
-- • Algebra
--     Abstract algebra (monoids, groups, rings etc.), along with
--     properties needed to specify these structures (associativity,
--     commutativity, etc.), and operations on and proofs about the
--     structures.
-- • Category
--     Category theory-inspired idioms used to structure functional
--     programs (functors and monads, for instance).
-- • Coinduction
--     Support for coinduction.
-- • Data
--     Data types and properties about data types. (Also some
--     combinators working solely on and with functions; see
--     Data.Function.)
-- • Foreign
--     Related to the foreign function interface.
-- • Induction
--     A general framework for induction (includes lexicographic and
--     well-founded induction).
-- • IO
--     Input/output-related functions.
-- • Relation
--     Properties of and proofs about relations (mostly homogeneous
--     binary relations).
-- • Size
--     Sizes used by the sized types mechanism.

------------------------------------------------------------------------
-- A selection of useful library modules
------------------------------------------------------------------------

-- Note that module names in source code are often hyperlinked to the
-- corresponding module. In the Emacs mode you can follow these
-- hyperlinks by typing M-. or clicking with the middle mouse button.

-- • Some data types

import Data.Bool     -- Booleans.
import Data.Char     -- Characters.
import Data.Empty    -- The empty type.
import Data.Fin      -- Finite sets.
import Data.List     -- Lists.
import Data.Maybe    -- The maybe type.
import Data.Nat      -- Natural numbers.
import Data.Product  -- Products.
import Data.Stream   -- Streams.
import Data.String   -- Strings.
import Data.Sum      -- Disjoint sums.
import Data.Unit     -- The unit type.
import Data.Vec      -- Fixed-length vectors.

-- • Some types used to structure computations

import Category.Functor      -- Functors.
import Category.Applicative  -- Applicative functors.
import Category.Monad        -- Monads.

-- • Equality

-- Propositional equality:
import Relation.Binary.PropositionalEquality

-- Convenient syntax for "equational reasoning" using a preorder:
import Relation.Binary.PreorderReasoning

-- Solver for commutative ring or semiring equalities:
import Algebra.RingSolver

-- • Properties of functions, sets and relations

-- Monoids, rings and similar algebraic structures:
import Algebra

-- Negation, decidability, and similar operations on sets:
import Relation.Nullary

-- Properties of homogeneous binary relations:
import Relation.Binary

-- • Induction

-- An abstraction of various forms of recursion/induction:
import Induction

-- Well-founded induction:
import Induction.WellFounded

-- Various forms of induction for natural numbers:
import Induction.Nat

-- • Support for coinduction

import Coinduction

-- • IO

import IO

------------------------------------------------------------------------
-- Record hierarchies
------------------------------------------------------------------------

-- When an abstract hierarchy of some sort (for instance semigroup →
-- monoid → group) is included in the library the basic approach is to
-- specify the properties of every concept in terms of a record
-- containing just properties, parameterised on the underlying
-- operations, sets etc.:
--
--   record IsSemigroup {A} (≈ : Rel A) (∙ : Op₂ A) : Set where
--     open FunctionProperties ≈
--     field
--       isEquivalence : IsEquivalence ≈
--       assoc         : Associative ∙
--       ∙-pres-≈      : ∙ Preserves₂ ≈ ⟶ ≈ ⟶ ≈
--
-- More specific concepts are then specified in terms of the simpler
-- ones:
--
--     record IsMonoid {A} (≈ : Rel A) (∙ : Op₂ A) (ε : A) : Set where
--       open FunctionProperties ≈
--       field
--         isSemigroup : IsSemigroup ≈ ∙
--         identity    : Identity ε ∙
--
--     open IsSemigroup isSemigroup public
--
-- Note here that open IsSemigroup isSemigroup public ensures that the
-- fields of the isSemigroup record can be accessed directly; this
-- technique enables the user of an IsMonoid record to use underlying
-- records without having to manually open an entire record hierarchy.
-- This is not always possible, though. Consider the following definition
-- of preorders:
--
--   record IsPreorder {A : Set}
--                     (_≈_ : Rel A) -- The underlying equality.
--                     (_∼_ : Rel A) -- The relation.
--                     : Set where
--     field
--       isEquivalence : IsEquivalence _≈_
--       -- Reflexivity is expressed in terms of an underlying equality:
--       reflexive     : _≈_ ⇒ _∼_
--       trans         : Transitive _∼_
--       ∼-resp-≈      : _∼_ Respects₂ _≈_
--
--     module Eq = IsEquivalence isEquivalence
--
--     refl : Reflexive _∼_
--     refl = reflexive Eq.refl
--
-- The Eq module in IsPreorder is not opened publicly, because it
-- contains some fields which clash with fields or other definitions
-- in IsPreorder.

-- Records packing up properties with the corresponding operations,
-- sets, etc. are sometimes also defined:
--
--   record Semigroup : Set₁ where
--     infixl 7 _∙_
--     infix  4 _≈_
--     field
--       carrier     : Set
--       _≈_         : Rel carrier
--       _∙_         : Op₂ carrier
--       isSemigroup : IsSemigroup _≈_ _∙_
--
--     open IsSemigroup isSemigroup public
--
--     setoid : Setoid
--     setoid = record { isEquivalence = isEquivalence }
--
--   record Monoid : Set₁ where
--     infixl 7 _∙_
--     infix  4 _≈_
--     field
--       carrier  : Set
--       _≈_      : Rel carrier
--       _∙_      : Op₂ carrier
--       ε        : carrier
--       isMonoid : IsMonoid _≈_ _∙_ ε
--
--     open IsMonoid isMonoid public
--
--     semigroup : Semigroup
--     semigroup = record { isSemigroup = isSemigroup }
--
--     open Semigroup semigroup public using (setoid)
--
-- Note that the Monoid record does not include a Semigroup field.
-- Instead the Monoid /module/ includes a "repackaging function"
-- semigroup which converts a Monoid to a Semigroup.

-- The above setup may seem a bit complicated, but we think it makes the
-- library quite easy to work with, while also providing enough
-- flexibility.

------------------------------------------------------------------------
-- More documentation
------------------------------------------------------------------------

-- Some examples showing where the natural numbers and some related
-- operations and properties are defined, and how they can be used:

import README.Nat

------------------------------------------------------------------------
-- Core modules
------------------------------------------------------------------------

-- Some modules have names ending in ".Core". These modules are
-- internal, and have (mostly) been created to avoid mutual recursion
-- between modules. They should not be imported directly; their
-- contents are reexported by other modules.

------------------------------------------------------------------------
-- All library modules
------------------------------------------------------------------------

-- For short descriptions of every library module, see Everything:

import Everything