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

Question

Мне нужно доказать, что следующий выбор сортировки код (в 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 []]) =

* * +1025 сортируются ([]]) * 1 026 *

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

---

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

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

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

вариант I: x = y = минимум

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

отсортировано (пусть {x = минимум (y # xs)} в x: ssort (удалить x (y # xs))) = (по определению)

отсортировано (пусть {y = минимум (y # xs)} по y: ssort (удалить y (y # xs))) = (по замене)

отсортировано (y: ssort (удалить y (y # xs))) =

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

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

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

вариант II: у не минимум

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

отсортировано (пусть {x = минимум (y # xs)} в x: ssort (удалить x (y # xs))) = (по определению)

.....

не знаю

Answer 1

Ваша индуктивная гипотеза слишком слаба. Вы должны предположить, что 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