开发者

Haskell - Merge Sort, sorting words and numbers

开发者 https://www.devze.com 2023-04-08 06:50 出处:网络
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?

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)) 
0

精彩评论

暂无评论...
验证码 换一张
取 消