Я запутался, почему эта реализация mergesort не работает?

Я новичок в 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 к нему.

Что мне не хватает / как это неправильно?

Любая помощь приветствуется :)

haskell functional-programming

Всего 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