[Agda] Agda standard library tutorial?
Andreas Abel
andreas.abel at ifi.lmu.de
Thu Jan 13 15:03:46 CET 2011
Hi all,
is there a tutorial on how to use the standard library? I am having
(again) problems with the complexity of its organization. My problem is
rather simple. I want to use commutativity and associativity of the
boolean connectives. Looking at Data.Bool.Properties, I have them there
dangling right before my eyes:
------------------------------------------------------------------------
-- (Bool, ∨, ∧, false, true) forms a commutative semiring
private
∨-assoc : Associative _∨_
∨-assoc true y z = refl
∨-assoc false y z = refl
...
But, sigh, they are private. Ok, not too bad, there is a structure
embedding them:
isCommutativeSemiring-∨-∧
: IsCommutativeSemiring _≡_ _∨_ _∧_ false true
isCommutativeSemiring-∨-∧ = record
{ +-isCommutativeMonoid = record
{ isSemigroup = record
{ isEquivalence = isEquivalence
; assoc = ∨-assoc
; ∙-cong = cong₂ _∨_
}
; identityˡ = λ _ → refl
; comm = ∨-comm
}
; *-isCommutativeMonoid = record
...
Somehow the simple names ∨-assoc,... are gone and replaced by some
hierarchical structure of names. Ok, how do I get to them? I cannot
project out of a record directly because the projections are tied in
with the module associated to the record type, so let's find it in
Algebra.Structures.
record IsCommutativeSemiring
{a ℓ} {A : Set a} (≈ : Rel A ℓ)
(_+_ _*_ : Op₂ A) (0# 1# : A) : Set (a ⊔ ℓ) where
open FunctionProperties ≈
field
+-isCommutativeMonoid : IsCommutativeMonoid ≈ _+_ 0#
*-isCommutativeMonoid : IsCommutativeMonoid ≈ _*_ 1#
distribʳ : _*_ DistributesOverʳ _+_
zeroˡ : LeftZero 0# _*_
private
module +-CM = IsCommutativeMonoid +-isCommutativeMonoid
open module *-CM = IsCommutativeMonoid *-isCommutativeMonoid public
using () renaming (comm to *-comm)
open EqR (record { isEquivalence = +-CM.isEquivalence })
distrib : _*_ DistributesOver _+_
distrib = (distribˡ , distribʳ)
where
distribˡ : _*_ DistributesOverˡ _+_
distribˡ x y z = begin
(x * (y + z)) ≈⟨ *-comm x (y + z) ⟩
((y + z) * x) ≈⟨ distribʳ x y z ⟩
((y * x) + (z * x)) ≈⟨ *-comm y x ⟨ +-CM.∙-cong ⟩ *-comm z x ⟩
((x * y) + (x * z)) ∎
zero : Zero 0# _*_
zero = (zeroˡ , zeroʳ)
where
zeroʳ : RightZero 0# _*_
zeroʳ x = begin
(x * 0#) ≈⟨ *-comm x 0# ⟩
(0# * x) ≈⟨ zeroˡ x ⟩
0# ∎
isSemiring : IsSemiring ≈ _+_ _*_ 0# 1#
isSemiring = record
{ isSemiringWithoutAnnihilatingZero = record
{ +-isCommutativeMonoid = +-isCommutativeMonoid
; *-isMonoid = *-CM.isMonoid
; distrib = distrib
}
; zero = zero
}
open IsSemiring isSemiring public
hiding (distrib; zero; +-isCommutativeMonoid)
isCommutativeSemiringWithoutOne :
IsCommutativeSemiringWithoutOne ≈ _+_ _*_ 0#
isCommutativeSemiringWithoutOne = record
{ isSemiringWithoutOne = isSemiringWithoutOne
; *-comm = *-CM.comm
}
I must confess at this point I am lost. What the h... are all these
local modules and record and how on earth shall I quickly extract from
this heap what the names of the innocent lemmata are I want to use?? My
brain does not implement the Agda module system! My clumsy attempt to
open this structure fails:
open import Data.Bool using (Bool; true; false; if_then_else_)
open import Data.Bool.Properties using (isCommutativeSemiring-∨-∧)
import Algebra.Structures
open Algebra.Structures.IsCommutativeSemiring isCommutativeSemiring-∨-∧
hiding (zero)
open import Relation.Binary.PropositionalEquality
Because now "refl" is ambiguous!
Forgive me, but at this point my patience is spent. Before investing
more hours fighting with a complex structure that I do not understand
and which is documented by nothing than the source code, I give in to
the temptation and cut-and-paste, or reimplement myself.
I think I am not the only one having this problem with the standard
library. Others might have more patients wrestling with the correct
list of imports, module definitions, and opens.
What can be done about this? I have some ideas, but cannot implement
them myself (otherwise I would not have this problem...)
1. Write a tutorial for the standard library that shows how its
definitions can be used. I know that there are README files, but imho
they only show how definitions can be used in principle, but not concretely.
2. Supply (documented) example programs for each of the library modules
that explain how to use the stuff there. Would that not also have the
benefit to have some initial users and test cases?
3. Provide "preludes" that extract the most important definitions from a
package into a single file, such that definitions are available directly
without sophisticated module- or open-statements. For instance, one
could have a Data.Bool.Prelude, Data.Nat.Prelude, Data.List.Prelude etc.
Frustrated,
Andreas
More information about the Agda
mailing list