Haskell - Merge Sort, sorting words and numbers
I've written a merge sort in Haskell, it works when using numbers but not with words, and I thought it would. I just get "Not in scope" when using words and letters. What am I doing wrong?
Here's my code:
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 => [开发者_Go百科a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs
= merge (mergeSort top) (mergeSort bottom)
where
(top, bottom) = splitAt (length xs `div` 2) xs
Are you entering your words like this?
[this,is,an,example,sentence]
The syntax is not correct. If you want to input a literal string, you have to encapsulte it in double quotes ("
):
["this","is","an","example","sentence"]
If that is not your error, feel free to ignore this answer.
Your code works fine.
However I'd suggest to split the list in one pass, without using length
. Of course, the order isn't important here, just that we have two lists of about the same size. You could do it that way:
splitList [] = ([],[])
splitList [x] = ([x],[])
splitList (x:y:zs) = let (xs,ys) = splitList zs in (x:xs, y:ys)
... or tail recursive ...
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)
... or using indexes ...
splitList xs = (go even, go odd) where
go f = map snd $ filter (f.fst) $ indexed
indexed = zip [0..] xs
... or using a fold ...
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))
精彩评论