Сортированный список в idris (сортировка вставки)

Я пишу магистерскую диссертацию о полезности зависимых типов. Я пытаюсь построить контейнер, который может быть создан только в отсортированном списке, так что он проверен по конструкции:

import Data.So

mutual
  data SortedList : (a : Type) -> {ord : Ord a) -> Type where
    SNil : SortedList a
    SMore : (ord : Ord a) => (el: a) -> (xs : SortedList a) -> So (canPrepend el xs) -> SortedList a

  canPrepend : Ord a => a -> SortedList a -> Bool
  canPrepend el SNil = True
  canPrepend el (SMore x xs prf) = el <= x

SMore требует проверки времени выполнения, что добавляемый элемент меньше или равен наименьшему (первому) элементу в отсортированном списке.

Чтобы отсортировать несортированный список, я создал функцию sinsert, которая принимает отсортированный список и вставляет элемент и возвращает отсортированный список:

sinsert : (ord : Ord a) => SortedList a {ord} -> a -> SortedList a {ord}
sinsert SNil el = SMore el SNil Oh
sinsert (SMore x xs prf) el = either 
  (\p => 
    -- if el <= x we can prepend it directly
    SMore el (SMore x xs prf) p
  ) 
  (\np =>  
    -- if not (el <= x) then we have to insert it in the tail somewhere
    -- does not (el <= x) imply el > x ???

    -- we construct a new tail by inserting el into xs
    let (SMore nx nxs nprf) = (sinsert xs el) in
    -- we get two cases:
    -- 1) el was prepended to xs and is now the 
    --    smalest element in the new tail
    --    we know that el == nx
    --    therefor we can substitute el with nx
    --    and we get nx > x and this also means 
    --    x < nx and also x <= nx and we can
    --    prepend x to the new tail
    -- 2) el was inserted somewhere deeper in the
    --    tail. The first element of the new tail
    --    nx is the same as it was in the original
    --    tail, therefor we can prepend x to the
    --    new tail based on the old proof `prf`
    either 
      (\pp => 
        SMore x (SMore nx nxs nprf) ?iins21
      )
      (\npp => 
        SMore x (SMore nx nxs nprf) ?iins22
      ) (choose (el == nx))
  ) (choose (el <= x))

У меня возникли проблемы с построением доказательств (?iins21, ?iins22), и я был бы признателен за некоторую помощь. Я могу полагаться на предположение, которое не выполняется, но я этого не вижу.

Я также хотел бы предложить вам создать лучшее решение для построения отсортированного списка (может быть, обычный список с доказательным значением, который он сортирует?)

Ответы

Ответ 1

Я думаю, что основная проблема с вашими доказательствами заключается в том, что, как заметил в комментарии Cactus, у вас нет свойств, таких как транзитивность и антисимметрия, которые необходимы для доказательства сортировки вставки. Тем не менее, вы все равно можете создать полиморфный контейнер: класс Poset из Decidable.Order в contrib содержит именно те свойства, которые вы хотите. Тем не менее, Decidable.Order.Order лучше в этом случае, поскольку он инкапсулирует совокупность отношения, гарантируя, что для любых двух элементов мы можем получить доказательство того, что один из них меньше.

У меня есть другой алгоритм сортировки вставки, в котором я работал в любом случае, который использует Order; он также явно разлагает распределение между списками Empty и NonEmpty и сохраняет max (наибольший элемент, который теперь может быть добавлен в список) в типе списков NonEmpty, что несколько упрощает доказательства.

Я также изучаю Идрис, поэтому этот код не может быть самым идиоматическим; также большое спасибо Melvar и {AS} на IRC-канале #idris Freenode за то, что помогли мне разобраться, почему предыдущие версии не работали.

Сильный синтаксис with (y) | <pattern matches on y> в sinsert существует, чтобы связать y для assert_smaller, так как по какой-то причине [email protected](NonEmpty xs) не работает.

Я надеюсь, что это будет полезно!

import Data.So
import Decidable.Order

%default total

data NonEmptySortedList :  (a : Type)
                        -> (po : a -> a -> Type)
                        -> (max : a)
                        -> Type where
  SOne   : (el : a) -> NonEmptySortedList a po el
  SMany  :  (el : a)
         -> po el max
         -> NonEmptySortedList a po max
         -> NonEmptySortedList a po el

data SortedList : (a : Type) -> (po : a -> a -> Type) -> Type where
  Empty : SortedList _ _
  NonEmpty : NonEmptySortedList a po _ -> SortedList a po

head : NonEmptySortedList a _ _ -> a
head (SOne a) = a
head (SMany a _ _) = a

tail : NonEmptySortedList a po _ -> SortedList a po
tail (SOne _) = Empty
tail (SMany _ _ xs) = NonEmpty xs

max : {m : a} -> NonEmptySortedList a _ m -> a
max {m} _ = m

newMax : (Ordered a po) => SortedList a po -> a -> a
newMax Empty x = x
newMax (NonEmpty xs) x = either (const x)
                                (const (max xs))
                                (order {to = po} x (max xs))

either' :  {P : Either a b -> Type}
        -> (f : (l : a) -> P (Left l))
        -> (g : (r : b) -> P (Right r))
        -> (e : Either a b) -> P e
either' f g (Left l) = f l
either' f g (Right r) = g r

sinsert :  (Ordered a po)
        => (x : a)
        -> (xs : SortedList a po)
        -> NonEmptySortedList a po (newMax xs x)
sinsert x y with (y)
  | Empty = SOne {po = po} x
  | (NonEmpty xs) = either' { P = NonEmptySortedList a po
                            . either (const x) (const (max xs))
                            }
                            insHead
                            insTail
                            (order {to = po} x (max xs))
  where insHead : po x (max xs) -> NonEmptySortedList a po x
        insHead p = SMany x p xs
        max_lt_newmax : po (max xs) x -> po (max xs) (newMax (tail xs) x)
        max_lt_newmax max_xs_lt_x with (xs)
          | (SOne _) = max_xs_lt_x
          | (SMany _ max_xs_lt_max_xxs xxs)
            = either' { P = po (max xs) . either (const x)
                                                 (const (max xxs))}
                      (const {a = po (max xs) x} max_xs_lt_x)
                      (const {a = po (max xs) (max xxs)} max_xs_lt_max_xxs)
                      (order {to = po} x (max xxs))
        insTail : po (max xs) x -> NonEmptySortedList a po (max xs)
        insTail p = SMany (max xs)
                          (max_lt_newmax p)
                          (sinsert x (assert_smaller y (tail xs)))

insSort :  (Ordered a po) => List a -> SortedList a po
insSort = foldl (\xs, x => NonEmpty (sinsert x xs)) Empty