0

こんにちは皆さん、私は Haskel でマージソートを再現しようとしています。これが私のコードです:

-- merge
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
  | x <= y = x:(merge xs (y:ys))
  | otherwise = y:(merge (x:xs) ys)

-- split
splitIn2 :: (Ord a) => [a] -> ([a],[a])
splitIn2 [] = ([],[])
splitIn2 xs = splitAt ((length xs `div` 2)+1) xs

-- msort
msort :: (Ord a) => [a] -> [a]
msort [] = []
msort [x] = [x]
msort (xs) = merge (msort as) (msort bs)
    where (as,bs) = splitIn2 xs

ghc でコンパイルされ、以下で動作します。

*Main> msort([])
[]
*Main> msort([1])
[1]

ただし、無限ループを開始し（少なくともこれは私が考えていたことです）、何も出力しないため、適切に機能しません。

他の再帰実験で行ったように、リストから要素を削除しないためだと思いますが、何か提案はありますか?

4

2 に答える 2

8

問題はlength xs == 2、

(length xs `div` 2) + 1
= (2 `div` 2) + 1
= 1 + 1
= 2

とsplitAt 2 xs戻ります(xs, [])。最初のリストはまだ長さ2で あるため、無限ループで再度下にmsort移動しようとします。splitIn2

+1これを解決するには、単純に;を取り除くことができます。それは完全に不要です。空のリストの特殊なケースを排除することもできますsplitAt 0 [] = ([], [])。

splitIn2 xs = splitAt (length xs `div` 2) xs
于 2012-11-25T22:52:15.433 に答える
2 
*Main> splitIn2 [1, 2, 3, 0, 5, 6]
([1,2,3,0],[5,6])

そして、小さな変更後（削除+1）：

splitIn2 xs = splitAt ((length xs `div` 2)) xs

できます：

*Main> splitIn2 [1, 2, 3, 0, 5, 6]
([1,2,3],[0,5,6])
*Main> msort [1, 2, 3, 0, 5, 6]
[0,1,2,3,5,6]
于 2012-11-25T22:42:51.663 に答える