Haskell - 合并排序，对单词和数字进行排序

发布于 2024-12-06 06:52:59 字数 501 浏览 0 评论 0原文

我在 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

原文

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 => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs
    = merge (mergeSort top) (mergeSort bottom)
    where
    (top, bottom) = splitAt (length xs `div` 2) xs

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一页 2024-12-13 06:53:00

你是这样输入文字的吗？

[this,is,an,example,sentence]

语法不正确。如果您想输入文字字符串，则必须将其封装在双引号中（"）：

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

如果这不是您的错误，请随意忽略此答案。

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.

回复收藏 0 原文

花之痕靓丽 2024-12-13 06:53:00

你的代码工作正常。

不过，我建议一次性拆分列表，而不使用 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))

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 原文

~没有更多了~