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

Question

Я новичок в 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, то он возвращает список. В противном случае он делит список пополам на xs и рекурсивно начинает mosrt снова, пока length не станет равным или меньшим 1, в этот момент он применяет слияние к нему.

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

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

Answer 1

Вы забыли скобки в своих рекурсивных msort вызовах:

msort :: [Int] -> [Int]
msort xs 
    | length xs <= 1 = xs
    | otherwise = merge (msort <b>(</b>fst (halve xs)<b>)</b>) (msort <b>(</b>snd (halve xs)<b>)</b>)

Как говорится, использование length часто не хорошая идея, так как оно работает в О (п) . Здесь лучше использовать сопоставление с образцом. Кроме того, вы можете использовать предложение 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-pattern :

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge <b>xa@</b>(x:xs) <b>ya@</b>(y:ys)
    | x <= y = x : merge xs ya
    | otherwise = y : merge xa ys