插入排序使用尾递归与一次函数

我想设计使用尾递归和插入第一顺序编程哈斯克尔的算法排序插入排序使用尾递归与一次函数

我想出了这个解决方案

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

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

有人能想出了使用的替代解决方案

尾递归
第一顺序编程

感谢，

来源

2017-05-24 Pierre P.

这不使用尾递归。 'insert'的'otherwise'子句是'y：insert ys'（更清楚地写成'（:) y（insert ys）'），对'insert'的调用作为参数显示为'（：）'，而不是在尾部位置 –

你能解释一下“一阶编程”是什么意思吗？这只是一些没有把功能当作论据的东西。 – Lazersmoke

@Lazersmoke确实如此。 –

这是一个简单的版本，没有使用尾递归也不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)是传递给spanOrd a => a -> Bool类型的函数。

来源

2017-05-24 21:35:00 Nykros

插入排序使用尾递归与一次函数

回答

相关问题