функциональная нехвостовая рекурсивная версия сортировки в Haskell - PullRequest
Новая
       28

функциональная нехвостовая рекурсивная версия сортировки в Haskell

0 голосов
/ 13 мая 2019

Я ищу не хвостовую рекурсивную версию следующего выбора сортировки код в Haskell: 

import Data.List (minimum, delete)

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

Можете ли вы предоставить не хвостовую рекурсивную версию выбораsort?

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

Ответы [ 2 ]

5 голосов
/ 13 мая 2019

Краткий ответ : код не является рекурсивным .

Не могли бы вы предоставить нерекурсивную рекурсивную версию сортировки выбора?

Код , а не хвостовая рекурсия.Это " хвостовая рекурсия по модулю минусов " [wiki] , но не хвостовая рекурсия.

В Haskell wiki показано, как узнать,функция хвостовой рекурсии:

Вот формальное определение "хвостовой рекурсии".«f встречается в t» означает, что f является свободной переменной t.

Когда функция определена (в let или на верхнем уровне) как: 

f = t

, где f - это имя, а t - лямбда-термин, f - хвостовая рекурсивность, если f встречается в хвосте рекурсивно в t.f встречается рекурсивно в t, если * f встречается в t и выполняется любое из следующих условий:

  • t является переменным;
  • tравно \var -> t0 и f встречается в хвосте рекурсивно в t0;
  • t равно t0 t1, а f встречается в хвосте рекурсивно в t0 и не встречается в t1;
  • t равно let bs in t0 и f встречается рекурсивно в t0 и для каждого связующего var = t1 в bs, f не встречается в t1;
  • t - это case t0 of bs, а f не встречается в t0 и для каждой ветви b в bs, f не встречается или происходит рекурсивно в b;
    • когда мы говорим "встречаются в b", b имеет форму D vars -> t1 (где D - некоторый конструктор данных, а vars - последовательность имен), мы думаем олямбда-абстракция \vars -> t1 вместо b.

Выражение t равно \xs -> let x = minimum xs in x : ssort (delete x xs), поэтому мы можем взять второй элемент здесь,но тогда ssort должен быть хвост-рекурсивным в операторе let ... in ..., это четвертый случай.

Но этот четвертый случай требует, чтобы ssort был хвостовой рекурсивностью в "теле"let ... in ... выражение.Это выражение ((:) x) (ssort delete xs).Таким образом, это третий случай.

В третьем случае выражение имеет форму t0 t1, здесь с t0 = (:) x и t1 = ssort delete xs.Поскольку ssort не встречается в t0, здесь нет хвостовой рекурсии.

3 голосов
/ 13 мая 2019

Представленный код не является хвостово-рекурсивным, так как вы вызываете функцию : cons. Все рекурсивные вызовы будут удерживаться в стеке памяти в ожидании завершения оценки ssort (delete x xs). Хвосто-рекурсивная версия может выглядеть так: 

import Data.List (minimum, delete)

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