当我执行该代码时，为什么该代码悬挂？

发布于 2025-02-07 15:46:43 字数 1180 浏览 1 评论 0原文

我正在尝试

作为练习而实现的目标，我正在尝试编写一个“合并”功能，该功能列出了两个列表，并返回一个列表，其中两个列表中的所有元素都进行了排序。

例如：

合并[2,6,5] [3,4,1]应返回[1,2,3,4,5,6]
合格[] [] [4,1]应返回[4,1]

这是我写的：

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [a | a <- xs, a <= x]
    larger = [b | b <- xs, b > x]

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted listX [] = qsort listX
mergeSorted [] listY = qsort listY
mergeSorted listX listY   | x <= y      = x : mergeSorted xs (y:ys)
                          | otherwise   = y : mergeSorted (x:xs) ys
                          where
                            (y:ys) = sortedYs
                            (x:xs) = sortedXs
                            sortedYs = qsort ys
                            sortedXs = qsort xs

问题

QSort代码似乎运行良好。但是我的合并不起作用。如果我执行合并后的使用两个在GHCI中没有空的列表，则执行将永远悬挂。（即我永远不会得到结果）。

我的问题

请告诉我我的合并代码有什么问题？

原文

What I'm trying to achieve

As an exercise, I'm trying to write a 'mergeSorted' function which takes two lists, and returns a single list, in which all the elements from the two lists are sorted.

For example:

mergeSorted [2,6,5] [3,4,1] should return [1,2,3,4,5,6]
mergeSorted [] [4,1] should return [4,1]

Here's what I wrote:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [a | a <- xs, a <= x]
    larger = [b | b <- xs, b > x]

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted listX [] = qsort listX
mergeSorted [] listY = qsort listY
mergeSorted listX listY   | x <= y      = x : mergeSorted xs (y:ys)
                          | otherwise   = y : mergeSorted (x:xs) ys
                          where
                            (y:ys) = sortedYs
                            (x:xs) = sortedXs
                            sortedYs = qsort ys
                            sortedXs = qsort xs

The issue

The qsort code seems to be working well. But my mergeSorted isn't working.
If I execute mergeSorted with two lists which are not empty in GHCi, execution hangs forever. (i.e. I never get a result).

My question

Please can you tell me what's wrong with my mergeSorted code?

分享到QQ

分享到微博

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

发布评论

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

梦与时光遇 2025-02-14 15:46:43

您写（y：ys）= sortedys，sortedys = qsort ys，因此您对排序的结果进行排序，从而被卡在无限的循环中。但是，即使您设法解决了这一点，它也不是很有效的，因为对于每个项目，您都会再次对剩余项目的列表进行排序。

我认为最好将其简化为合并的辅助功能，而另一个调用QSort（或其他）作为预处理步骤：

import Data.Function(on)

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

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted = merge `on` qsort

You write (y:ys) = sortedYs, and sortedYs = qsort ys, hence you sort the result of the sort, and thus get stuck in an infinite loop. But even if you manage to solve that, it would not be very efficient, since for each item, you will sort the list of remaining items again.

I think it is better to simplify this in a helper function for merging, and another one that calls qsort (or something else) as pre-processing step:

import Data.Function(on)

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

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted = merge `on` qsort

回复收藏 0 原文

~没有更多了~