Как заметил @that другой парень, вы можете использовать iterate для применения sort' к списку n раз, что является прекрасным примером использования высокоуровневых комбинаторов в Haskell (в отличие от примитивной рекурсии) , Другим хорошим комбинатором, который полезен для такого рода вещей, является until: until примет предикат :: a -> Bool, функцию :: a -> a и значение :: a и будет применять функцию к значению до тех пор, пока Предикат остается верным. Поэтому, когда вы сталкиваетесь с подобной ситуацией, но не знаете точно, сколько проходов вы хотите сделать на входе, вы можете сделать что-то вроде until isSorted sort' xs, что может быть неплохо.
Многие другие однопроходные алгоритмы сортировки также хороши в Haskell, включая слияния сверху вниз и (особенно) снизу вверх.
Рискуя бросить вас в глубокий конец теории, я хотел бы упомянуть еще один довольно хороший высокоуровневый комбинаторный подход к итерации n раз. Это основано на идее «рекурсивных схем», где основная идея заключается в том, что структура рекурсивного типа данных предоставляет полезные шаблоны для его обработки / преобразования. Как это бывает, Haskell достаточно силен, чтобы выразить многие из этих идей. Один из самых простых примеров схемы рекурсии основан на натуральных числах:
data Nat = Zero | Succ Nat
Это рекурсивный тип данных, поскольку второй конструктор данных ссылается на сам Nat. Есть действительно естественный способ обработки Nat с, то есть, когда у меня есть Zero, я должен вернуть некоторое значение; в противном случае я должен рекурсивно обработать Nat и затем использовать эти значения, чтобы придумать новое значение. Как это бывает, мы можем написать Nat по-другому, что обычно делает это очень просто:
data NatF a = Zero | Succ a
type Nat = Mu NatF
Теперь тип данных NatF может содержать значение любого типа внутри своего «рекурсивного» компонента, а не только другой Nat. Конструктор типа Mu во второй строке в основном похож на функцию fix, но для типов: он создает экземпляр NatF (NatF (NatF (NatF ...))), так что Nat = NatF Nat, что совпадает с нашим предыдущим определением.
Однако из-за возросшей универсальности теперь мы можем записать тип a, который описывает функции, которые обрабатывают Nat s, как описано выше: NatF a -> a. Если дано Zero, функция этого типа просто возвращает some a; когда ему дано Succ, у него есть доступ к a, который он возвратил, когда он был рекурсивно вызван "изнутри" Nat. Оказывается, можно обобщить инфраструктуру, необходимую для этого, чтобы она могла работать с любым типом, написанным в стиле выше (то есть как фиксированная точка типа, обобщенного над рекурсивным компонентом). Это означает, что вы можете просто записать уравнения для вашей функции с учетом результатов рекурсивных вызовов, а затем вызвать cata для этой структуры данных, не заботясь о том, чтобы записывать повторяющиеся скучные рекурсивные вызовы!
Это также означает, что другой способ записать ваши времена "применения сортировки" (длина xs) к xs`:
sort xs = cata phi (toNat $ length xs)
where phi Zero = xs
phi (Succ xs) = sort' xs