Haskell 中选择排序的功能性非尾递归版本

Question

我正在 Haskell 中寻找以下 selection sort 代码的非尾递归版本：

import Data.List (minimum, delete)

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

能否提供选择排序的非尾递归版本？

我知道更改原始代码不是一个好主意，但我需要那个版本来进行实验。

Answer 1

显示的代码不是 tail-recursive，因为您调用了 : cons 函数。所有递归调用都将保留在内存堆栈中，等待 ssort (delete x xs) 的计算完成。 tail-recursive 版本可能如下所示：

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)

Answer 2

简答：代码是而不是tail-recursive。

Can you please provide with a non-tail recursive version of selection sort?

代码不是尾递归。它是"tail recursive modulo cons" [wiki]，但不是尾递归。

Haskell wiki 展示了如何判断函数是否为 tail-recursive:

Here is formal definition of "tail recursive". "f occurs in t" means f is a free variable of t.

When a function is defined (in let or at the top level) as:
f = t
where f is a name and t is a lambda-term, f is tail recursive iff f occurs tail recursively in t. f occurs tail recursively in t iff f occurs in t and any of the following holds:

t is variable;

t is \var -> t0 and f occurs tail recursively in t0;

t is t0 t1 and f occurs tail recursively in t0 and does not occur in t1;

t is let bs in t0 and f occurs tail recursively in t0 and for each binder var = t1 in bs, f does not occur in t1;

t is case t0 of bs and f does not occur in t0 and for each branch b in bs, f does not occur or occurs tail recursively in b;

when we are saying "occur in b", b has form D vars -> t1 (where D is some data constructor and vars is a sequence of names), we are thinking of the lambda-abstraction \vars -> t1 instead of b.

表达式t是\xs -> let x = minimum xs in x : ssort (delete x xs)，所以我们可以在这里取第二项，但是ssort需要在let ... in ...中是tail-recursive声明，这是第四种情况。

但是这第四种情况要求 ssort 在 let ... in ... 表达式的 "body" 中是尾递归的。这个表达式是((:) x) (ssort delete xs)。这是第三种情况。

在第三种情况下，表达式的形状为 t0 t1，此处为 t0 = (:) x 和 t1 = ssort delete xs。由于ssort没有出现在t0中，所以这里没有尾递归。

Haskell 中选择排序的功能性非尾递归版本

functional non-tail recursive version of selection sort in Haskell

haskell

selection-sort