рекурсивный выбор, сортировка, проверка правильности

Мне нужно доказать, что следующий код сортировки выбора (в Haskell) всегда выполняет сортировку:

import Data.List (minimum, delete)

ssort :: Ord t => [t] -> [t]
ssort [] = []
ssort xs = let { x = minimum xs } in  x : ssort (delete x xs)

Мы можем предположить, что у нас есть функция под названием «sorted», которая проверяет, когда список отсортирован.

Утверждение, доказываемое структурной индукцией: отсортировано (ssort xs)

Я пробовал следующее, но не смог завершить доказательство. Не могли бы вы помочь мне завершить доказательство?

Базовый случай: xs = []

отсортировано (ssort xs) =

отсортировано (ssort []]) =

отсортировано ([]])

правильно, так как sorted ([]) всегда отсортирован

Индуктивный шаг

IH (индуктивная гипотеза) = отсортировано (ssort xs)

показать: отсортировано (сортировка y # xs)

случай I: x = y = минимум

отсортировано (ssort y # xs) =

отсортировано (let {x = minimum (y # xs)} in x: ssort (delete x (y # xs))) = (по определению)

sorted (let {y = minimum (y # xs)} in y: ssort (delete y (y # xs))) = (путем подстановки)

отсортировано (y: ssort (delete y (y # xs))) =

sorted (y: ssort (xs)) = (по определению удаления)

отсортировано (y: ssort (xs))

по IH мы знаем, что ssort (xs) сортируется, также y - минимальное значение, поэтому оно идет первым

случай II: y не минимально

отсортировано (ssort y # xs) =

отсортировано (let {x = minimum (y # xs)} in x: ssort (delete x (y # xs))) = (по определению)

.....

без понятия


haskell induction proof-of-correctness
person P. Ez    schedule 12.05.2019    source источник
comment
Боковое примечание: чтобы доказать правильность функции сортировки, вам необходимо продемонстрировать еще две вещи: 1. То, что вычисление в конечном итоге завершается, и 2. То, что результатом функции является перестановка ее аргумента (ни один элемент не был удален, удвоен , или добавлено).   -  person dfeuer    schedule 13.05.2019
comment
Кроме того, как бы то ни было, я подозреваю, что вам будет легче доказать правильность реализации сортировки вставкой, что приведет вас более или менее непосредственно к доказательству правильности сортировки слиянием. Доказательство правильности сортировки при выборе кажется тупиком; некоторые похожие идеи появляются в куче, но в существенно разной одежде.   -  person dfeuer    schedule 13.05.2019
comment
@dfeuer Я допускаю, что приведенные случаи опускают некоторые детали, но разве и завершение, и перестановка по существу не покрываются той же индукцией, что и представленная? Считайте индукцию по n как ssort, завершающуюся правильным выводом (т. Е. Отсортированной перестановкой) любого ввода длины n. Да, мы предполагаем, что существуют некоторые законы классов типов, связывающие экземпляры eq, ord, некоторые свойства delete и, возможно, пару других вещей, но основная структура доказательства не нуждается в изменении для учета этих деталей?   -  person moonGoose    schedule 13.05.2019
comment
@moonGoose, возможно, ты прав. Я знаю, что может быть довольно сложно получить правильный бит перестановки в формальных доказательствах, но, вероятно, это неплохо в неформальных.   -  person dfeuer    schedule 14.05.2019

Ответы (1)


arrow_upward
6
arrow_downward

Ваша индуктивная гипотеза слишком слаба. Вы должны предполагать, что ssort правильно работает с любым списком длины k, а не с некоторым конкретным списком xs длины k.

Итак, вместо этого, предполагая, что ssort является правильным для любого списка длины k и позволяя xs быть любым списком длины k+1,

ssort xs 
= let x = minimum xs in x : ssort (delete x xs) -- by definition of `ssort`
= let x = minimum xs in x : sorted (delete x xs) -- `delete x xs` has length `k` so `ssort` sorts it correctly by IH
= sorted xs -- by definition of sorted, minimum, delete
person moonGoose    schedule 12.05.2019