Combining Sorted Lists with Dimensions

Suppose we have a data type of sorted lists with evidence not related to sorting. We will use the Agda experimental dimension function so that we can hope to get some recursive functions on the data type to pass the Agda end check.

{-# OPTIONS --sized-types #-}

open import Relation.Binary
open import Relation.Binary.PropositionalEquality as P

module ListMerge
   {𝒂 ℓ}
   (A : Set 𝒂)
   {_<_ : Rel A ℓ}
   (isStrictTotalOrder : IsStrictTotalOrder _≡_ _<_) where

   open import Level
   open import Size

   data SortedList (l u : A) : {ι : _} → Set (𝒂 ⊔ ℓ) where
      [] : {ι : _} → .(l < u) → SortedList l u {↑ ι}
      _∷[_]_ : {ι : _} (x : A) → .(l < x) → (xs : SortedList x u {ι}) → 
               SortedList l u {↑ ι}

Now, the classic function that needs to be defined over such a data structure is that it mergetakes two sorted lists and displays a sorted list containing exactly the elements of the input lists.

   open IsStrictTotalOrder isStrictTotalOrder

   merge : ∀ {l u} → SortedList l u → SortedList l u → SortedList l u
   merge xs ([] _) = xs
   merge ([] _) ys = ys
   merge (x ∷[ l<x ] xs) (y ∷[ l<y ] ys) with compare x y
   ... | tri< _ _ _ = x ∷[ l<x ] (merge xs (y ∷[ _ ] ys))
   merge (x ∷[ l<x ] xs) (.x ∷[ _ ] ys) | tri≈ _ P.refl _ = 
      x ∷[ l<x ] (merge xs ys)
   ... | tri> _ _ _ = y ∷[ l<y ] (merge (x ∷[ _ ] xs) ys)

, , , Agda , . , - . - . , , .

, , merge , Agda. mergesort ; , , , :

   merge′ : ∀ {l u} → {ι : _} → SortedList l u {ι} → 
                      {ι′ : _} → SortedList l u {ι′} → SortedList l u
   merge′ xs ([] _) = xs
   merge′ ([] _) ys = ys
   merge′ (x ∷[ l<x ] xs) (y ∷[ l<y ] ys) with compare x y
   ... | tri< _ _ _ = x ∷[ l<x ] (merge′ xs (y ∷[ _ ] ys))
   merge′ (x ∷[ l<x ] xs) (.x ∷[ _ ] ys) | tri≈ _ P.refl _ = 
      x ∷[ l<x ] (merge′ xs ys)
   ... | tri> _ _ _ = y ∷[ l<y ] (merge' (x ∷[ _ ] xs) ys)

, , ( ) , ∞.

, Agda , .ι != ∞ of type Size, xs . , , , ι ∞. , , .

, , ? , ? , merge , :

open import Data.Nat
open import Data.List
open import Relation.Nullary

merge : List ℕ → List ℕ → List ℕ
merge (x ∷ xs) (y ∷ ys) with x ≤? y
... | yes p = x ∷ merge xs (y ∷ ys)
... | _     = y ∷ merge (x ∷ xs) ys 
merge xs ys = xs ++ ys