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

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

我想出了這個解決方案

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

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

回答

相關問題