это реализация слияния сортировать хорошо?

Question

Я только начал изучать Haskell прошлой ночью, и я никогда раньше не использовал функциональный язык программирования. Я просто хочу знать, является ли моя реализация сортировки слиянием хорошей или плохой и что именно хорошо или плохо. Возможно, это даже неправильно. Ну, это похоже на сортировку, но, возможно, Алгоритм - это не то, что я думаю, что такое сортировка слияния.

Просто скажите мне все, что я мог бы улучшить здесь. Я сам считаю его довольно четкой и простой реализацией. Спасибо за ваши советы, вот код :)

merge [] ys = ys 
merge xs [] = xs 
merge xs ys = sorted : merge left right 
       where 
        sorted = if head(xs) < head(ys) then head(xs) else head(ys) 
        left = if head(xs) <= head(ys) then tail(xs) else xs 
        right = if head(xs) > head(ys) then tail(ys) else ys 

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort left) (msort right) 
      where 
       left = take (div (length xs) 2) xs 
       right = drop (div (length xs) 2) xs 

Answer 1

Ну, во-первых, мы можем переписать слияние, чтобы быть немного более элегантно, используя шаблон, соответствующий

merge [] ys = ys 
merge xs [] = xs 
merge xs@(x:xs1) ys@(y:ys1) 
    | x <= y = x : merge xs1 ys 
    | otherwise = y : merge xs ys1 

В целом следует избегать использования head и tail, так как они немного небезопасны (они порождают ошибку для пустого списка) и используют совпадение по шаблону, когда это возможно.

Реализация msort в значительной степени зависит от того, что мы можем разделить список более эффективным способом. Это потому, что length xs - забирает O (N). Компилятор может сохранить вас и кэшировать результат вызова length, чтобы второй вызов length не переместил список снова. Но take и drop в значительной степени вызовут еще два обхода, таким образом разбив список, используя 3 обхода, которые могут оказаться дорогими. Мы можем сделать лучше, разбивая список в двух списках - первый, содержащие элементы на нечетных позициях, а второй список с элементами, размещенных на четных позициях, например, так:

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort first) (msort second) 
    where 
     (first, second) = splitInHalves xs 
     splitInHalves [] = ([], []) 
     splitInHalves [x] = ([x], []) 
     splitInHalves (x:y:xs) = 
      let (xs1, ys1) = splitInHalves xs 
      in (x:xs1, y:ys1) 

Это получает вам то же самое Объединить сортировку по времени O (NlogN). Это кажется другим, потому что вы, вероятно, внедрили его на месте (путем изменения исходного списка) на императивном языке, таком как C. Эта версия немного дороже в памяти, но у нее есть свои преимущества - легче рассуждать о ней , поэтому он более удобен в обслуживании, а также очень легко parallelize, не заботясь ни о чем другом, кроме самого алгоритма - именно это должен обеспечить хороший язык программирования для разработчиков, которые его используют.

EDIT 1:

Если синтаксис многовато, вот некоторые ресурсы:

• Pattern Matching - бит с @ символом называется , как -образца. Вы найдете его там
• let - это ключевое слово, используемое для объявления переменной, которая будет использоваться в последующем выражении (тогда как where связывает переменную в предшествующем ей выражении).Еще на Haskell синтаксис, включая охранник (вещи с | condition = value) можно найти здесь, в этой главе Learn You a Haskell

EDIT 2:

@ is7s предложил гораздо более краткую версию splitInHalves с помощью foldrfunction:

splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[]) 

РЕДАКТИРОВАТЬ 3:

Вот еще один ответ, который предусматривает альтернативную реализацию сортировки слиянием, которая также имеет свойство быть stable:

Lazy Evaluation and Time Complexity

Надежда это помогает и добро пожаловать в удивительный мир функционального программирования!