使用尾递归和一阶函数的插入排序

Question

我想在 Haskell 中使用 尾递归 和 一阶编程 为 [=21] 设计一个算法=]插入排序

我想到了这个解决方案

isort :: Ord a => [a] -> [a]
isort [] = []
isort [x] = [x]
isort ( x:xs ) = insert ( isort xs )
    where insert [] = [x]
          insert ( y:ys )
            | x < y = x : y : ys
            | otherwise = y : insert ys

但我不确定它是否使用一阶和尾递归。

有人可以使用

提出替代解决方案吗

尾递归
一阶编程

谢谢，

Answer 1

这是简单版本，不使用尾递归和 HOF

sort :: Ord a => [a] -> [a]
sort   []   = []
sort  [x]   = [x]
sort (x:xs) = insert x (sort xs)

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x < y     = x:y:ys
                | otherwise = y:insert x ys

您可以添加一个累加器，它允许我们使用尾递归重写排序：

sort' :: Ord a => [a] -> [a]
sort' xs = sortAcc xs []

sortAcc :: Ord a => [a] -> [a] -> [a]
sortAcc   []   acc = acc
sortAcc (x:xs) acc = sortAcc xs (insert x acc)

insert 的定义非常好；但只是为了目的使用高阶函数，我们可以这样定义它：

insert' :: Ord a => a -> [a] -> [a]
insert' x xs = menores ++ x:mayores
  where (menores,mayores) = span (<x) xs

其中 (<x) 部分是传递给 span 的类型 Ord a => a -> Bool 的函数。

使用尾递归和一阶函数的插入排序

Insertion sort using tail recursion & first order function

haskell

functional-programming

tail-recursion

insertion-sort