如何使用foldr編寫insertionSort？

Question

我寫了下面的Haskell函數：

myInsert :: Ord a => a -> [a] -> [a] 
myInsert x [] = [x] 
myInsert x (y:ys) = if x < y then x:y:ys else y:myInsert x ys 

insertionSort :: Ord a => [a] -> [a] 
insertionSort [] = [] 
insertionSort [x] = [x] 
insertionSort (x:xs) = myInsert x (insertionSort xs) 

正如你所看到的，「插入排序」依賴「myInsert」，和他們很好地工作。現在我被要求在「insertioSort」中使用「foldr」，但是我一直無法獲得成功的結果。

我會感謝您的反饋。

Answer 1

這裏是definition of foldr used in GHC：

foldr k z = go 
      where 
      go []  = z 
      go (y:ys) = y `k` go ys 

只是爲了簡單起見，我們內嵌go，並用少了幾分花哨的語法：

foldr k z [] = z 
foldr k z (x:xs) = k x (foldr k z xs) 

爲了便於比較，這裏是你的函數：

insertionSort [] = [] 
insertionSort (x:xs) = myInsert x (insertionSort xs) 

注意他們有多相似！你能想出k和z需要在foldr方程中等於你的實現insertionSort？