Haskell - Merge Sort, сортировка слов и цифр - PullRequest
Новая
       17

Haskell - Merge Sort, сортировка слов и цифр

2 голосов
/ 26 сентября 2011

Я написал сортировку слиянием в Haskell, она работает при использовании чисел, но не со словами, и я думал, что так и будет. Я просто получаю «Не в рамках» при использовании слов и букв. Что я делаю не так?

Вот мой код: 

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

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs
    = merge (mergeSort top) (mergeSort bottom)
    where
    (top, bottom) = splitAt (length xs `div` 2) xs

Ответы [ 2 ]

4 голосов
/ 26 сентября 2011

Вы вводите свои слова, как это? 

[this,is,an,example,sentence]

Синтаксис неверен. Если вы хотите ввести буквенную строку, вы должны заключить ее в двойные кавычки ("): 

["this","is","an","example","sentence"]

Если это не ваша ошибка, не стесняйтесь игнорировать этот ответ.

3 голосов
/ 26 сентября 2011

Ваш код работает нормально.

Однако я бы предложил разделить список за один проход, не используя length. Конечно, порядок здесь не важен, просто у нас есть два списка примерно одинакового размера. Вы можете сделать это так: 

splitList [] = ([],[])
splitList [x] = ([x],[])
splitList (x:y:zs) = let (xs,ys) = splitList zs in (x:xs, y:ys)

... или рекурсивный хвост ... 

splitList zs = go zs [] [] where
   go [] xs ys = (xs, ys)
   go [x] xs ys = (x:xs, ys)
   go (x:y:zs) xs ys = go zs (x:xs) (y:ys)

... или используя индексы ... 

splitList xs = (go even, go odd) where
   go f = map snd $ filter (f.fst) $ indexed
   indexed = zip [0..] xs

... или используя складку ... 

import Data.List

splitList zs = snd $ foldl' go (True,([],[])) zs where
   go (True,(xs,ys)) x = (False,(x:xs,ys))   
   go (False,(xs,ys)) x = (True,(xs,x:ys))
...