我想要達到的目標
作為一個練習，我正在嘗試撰寫一個“mergeSorted”函式，它接受兩個串列，并回傳一個串列，其中兩個串列中的所有元素都被排序。
例如：
mergeSorted [2,6,5] [3,4,1]應該回傳[1,2,3,4,5,6]mergeSorted [] [4,1]應該回傳[4,1]
這是我寫的：
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller [x] qsort larger
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]
mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted listX [] = qsort listX
mergeSorted [] listY = qsort listY
mergeSorted listX listY | x <= y = x : mergeSorted xs (y:ys)
| otherwise = y : mergeSorted (x:xs) ys
where
(y:ys) = sortedYs
(x:xs) = sortedXs
sortedYs = qsort ys
sortedXs = qsort xs
問題
該qsort代碼似乎運行良好。但我mergeSorted的不作業。如果我mergeSorted使用 GHCi 中不為空的兩個串列執行，則執行將永遠掛起。（即我從來沒有得到結果）。
我的問題
請你能告訴我我的mergeSorted代碼有什么問題嗎？
uj5u.com熱心網友回復：
您撰寫(y:ys) = sortedYs, 和sortedYs = qsort ys，因此您對排序結果進行排序，從而陷入無限回圈。但即使你設法解決了這個問題，它也不會很有效，因為對于每個專案，你都會再次對剩余專案串列進行排序。
我認為最好在一個用于合并的輔助函式中簡化這一點，另一個呼叫qsort（或其他）作為預處理步驟的函式：
import Data.Function(on)
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
| x <= y = x : merge xs ya
| otherwise = y : merge xa ys
mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted = merge `on` qsort
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/490456.html
標籤：哈斯克尔