Как перечислить элементы списка по 'Fin`s в линейное время?

Мы можем перечислить элементы списка следующим образом:

-- enumerate-ℕ = zip [0..]
enumerate-ℕ : ∀ {α} {A : Set α} -> List A -> List (ℕ × A)
enumerate-ℕ = go 0 where
  go : ∀ {α} {A : Set α} -> ℕ -> List A -> List (ℕ × A)
  go n  []      = []
  go n (x ∷ xs) = (n , x) ∷ go (ℕ.suc n) xs

Например.enumerate-ℕ (1 ∷ 3 ∷ 2 ∷ 5 ∷ []) равно(0 , 1) ∷ (1 , 3) ∷ (2 , 2) ∷ (3 , 5) ∷ [], Предполагая, что в Agda есть разделение, функция является линейной.

Однако если мы попытаемся перечислить элементы списка поFinскорее, чемs, функция становится квадратичной:

enumerate-Fin : ∀ {α} {A : Set α} -> (xs : List A) -> List (Fin (length xs) × A)
enumerate-Fin  []      = []
enumerate-Fin (x ∷ xs) = (zero , x) ∷ map (pmap suc id) (enumerate-Fin xs)

Можно ли перечислить поFinс линейным временем?

Ответы на вопрос(1)

Ваш ответ на вопрос