Я новичок в Haskell и пытаюсь внедрить mergesort, но он не работает, и я не совсем понимаю, почему?
Мой код:
halve :: [a] -> ([a],[a])
halve xs = splitAt (length xs `div` 2) xs
merge :: [Int] -> [Int] -> [Int]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
if x < y
then x:(merge xs (y:ys))
else y:(merge (x:xs) ys)
msort :: [Int] -> [Int]
msort [] = []
msort xs
| length xs <= 1 = xs
| otherwise = merge (msort fst(halve xs)) (msort snd(halve xs))
В основном msort мое понимание того, как оно должно работать, заключается в том, что если длина xs меньше или равна 1 он возвращает список. В противном случае он mosrt список xs пополам и рекурсивно запускает mosrt снова, пока length станет равной или меньшей 1, после чего он применяет merge к нему.
Что мне не хватает / как это неправильно?
Любая помощь приветствуется :)
Всего 1 ответ
Вы забыли скобки в своих рекурсивных msort :
msort :: [Int] -> [Int]
msort xs
| length xs <= 1 = xs
| otherwise = merge (msort (fst (halve xs))) (msort (snd (halve xs))) Это, как говорится, использование length часто не очень хорошая идея, так как он работает в O (n) . Здесь лучше использовать сопоставление с образцом. Кроме того, вы можете использовать предложение where , чтобы избежать вычисления halve xs дважды:
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort la) (msort lb)
where (la, lb) = halve xs halve может быть построена так, что мы передаем каждый второй элемент одному из элементов 2-кортежа, например:
halve :: [a] -> ([a], [a])
halve [] = ([], [])
halve (x:xs) = (x:ya, yb)
where (yb, ya) = halve xs или с рисунком foldr :
halve :: [a] -> ([a], [a])
halve = foldr (x (yb, ya) -> (x:ya, yb)) ([], []) и merge может быть реализовано более элегантно с использованием as-шаблонов :
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