插入排序使用尾遞歸與一次函數

Question

我想設計使用尾遞歸和插入第一順序編程哈斯克爾的算法排序

我想出了這個解決方案

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)是傳遞給spanOrd a => a -> Bool類型的函數。