[Agda] `with' in standard functions
Sergei Meshveliani
mechvel at botik.ru
Thu Sep 28 13:16:16 CEST 2017
On Wed, 2017-09-27 at 15:33 +0200, Nils Anders Danielsson wrote:
> On 2017-09-26 21:47, Sergei Meshveliani wrote:
> > I meant: how will it look the intended parsing result, for a simple
> > example.
>
> Consider the following code:
>
> f : {A : Set} → List A → List A
> f [] = []
> f (x ∷ xs) with xs
> ... | [] = xs
> ... | y ∷ ys = x ∷ ys
>
> This is expanded into something like the following:
>
> .f-aux : {A : Set} → A → List A → List A → List A
> .f-aux x xs [] = xs
> .f-aux x xs (y ∷ ys) = x ∷ ys
>
> f : {A : Set} → List A → List A
> f [] = []
> f (x ∷ xs) = .f-aux x xs xs
>
> The idea is that the expression f (x ∷ xs) | ys would stand for
> .f-aux x xs ys.
>
For example, Data.Bin has
fromBits : List Bit → Bin
fromBits [] = 0#
fromBits (b ∷ bs) with fromBits bs
fromBits (b ∷ bs) | bs′ 1# = (b ∷ bs′) 1#
fromBits (0b ∷ bs) | 0# = 0#
fromBits (1b ∷ bs) | 0# = [] 1#
fromBits (⊥b ∷ bs) | _
And a proof for
fromBits-bs++1 : fromBits ∘ (_∷ʳ 1b) ≗ _1#
will be possible as
-------------------------------
fromBits-bs++1 [] = refl
fromBits-bs++1 (b ∷ bs) =
begin
fromBits ((b ∷ bs) ∷ʳ 1b) ≡⟨ refl ⟩
fromBits (b ∷ (bs ∷ʳ 1b)) ≡⟨ refl ⟩
fromBits (b ∷ (bs ∷ʳ 1b)) | fromBits (bs ∷ʳ 1b) --
≡⟨ cong prefix0 (fromBits-bs++1 bs)
)
fromBits (b ∷ (bs ∷ʳ 1b)) | bs 1# ≡⟨ refl ⟩ --
(b ∷ bs) 1#
∎
where
prefix0 = (fromBits (b ∷ (bs ∷ʳ 1b)) |_) --
-------------------------------
Right?
If so, than this looks good. Because less helper functions will appear
on the top level.
Can this "_|_" be implemented?
As to 'where', any algorithm can be rewritten with eliminating `where'
by introducing top level helpers. I do not know, may be, these helpers
can be somehow rewritten to the `with' construct ...
?
Thanks,
------
Sergei
More information about the Agda
mailing list