← Back to branch summary

~ubuntu-branches/ubuntu/wily/agda/wily-proposed

« back to all changes in this revision

Viewing changes to examples/Termination/StreamEating.agda

  • Committer: Package Import Robot
  • Author(s): Iain Lane
  • Date: 2014-08-05 06:38:12 UTC
  • mfrom: (1.1.6)
  • Revision ID: package-import@ubuntu.com-20140805063812-io8e77niomivhd49
Tags: 2.4.0.2-1
* [6e140ac] Imported Upstream version 2.4.0.2
* [2049fc8] Update Build-Depends to match control
* [93dc4d4] Install the new primitives
* [e48f40f] Fix typo dev→doc

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/Termination/StreamEating.agda
1
 
{-
2
 
Stream transducers have been described in:
3
 
 
4
 
  N. Ghani, P. Hancock, and D. Pattinson,
5
 
  Continuous functions on final coalgebras.
6
 
  In Proc. CMCS 2006, Electr. Notes in Theoret. Comp. Sci., 2006.
7
 
 
8
 
They have been modelled by mixed equi-(co)inductive sized types in
9
 
 
10
 
  A. Abel,
11
 
  Mixed Inductive/Coinductive Types and Strong Normalization.
12
 
  In APLAS 2007, LNCS 4807.
13
 
 
14
 
Here we model them by mutual data/codata and mixed recursion/corecursion.
15
 
Cf. examples/Termination/StreamProc.agda
16
 
 -}
17
 
 
18
 
module StreamEating where
19
 
 
20
 
open import Common.Coinduction
21
 
 
22
 
 
23
 
data Stream (A : Set) : Set where
24
 
  _∷_ : (x : A) (xs : ∞ (Stream A)) → Stream A
25
 
 
26
 
 
27
 
data SP (A B : Set) : Set where
28
 
  get : (f : A → SP A B) → SP A B
29
 
  put : (b : B) (sp : ∞ (SP A B)) → SP A B
30
 
 
31
 
eat : ∀ {A B} → SP A B → Stream A → Stream B
32
 
eat (get f)    (a ∷ as) = eat (f a) (♭ as)
33
 
eat (put b sp) as       = b ∷ ♯ eat (♭ sp) as
34
 
 
35
 
_∘_ : ∀ {A B C} → SP B C → SP A B → SP A C
36
 
get f₁    ∘ put x sp₂ = f₁ x ∘ ♭ sp₂
37
 
put x sp₁ ∘ sp₂       = put x (♯ (♭ sp₁ ∘ sp₂))
38
 
sp₁       ∘ get f₂    = get (λ x → sp₁ ∘ f₂ x)