3

这是过去几天一直在疯狂的家庭作业。

我有一个列表，我正在应用一个函数 - 如果它旁边的元素小于前一个元素，则将每个元素向右推。

我的函数将列表传递一次并对列表的头部进行排序：

sortEm lis@(x:y:xs) = if x > y then y: sortEm (x:xs) else lis
sortEm [x] = [x]
sortEm [] = []

myList (x:y:xs) = if x > y then sortEm lis else x:myList(y:xs)
myList [] = []
myList [x] = [x]

但我的问题是，一旦该排序完成它返回一个空列表或包含一个元素的列表，我将如何设计这种功能方式？

我正在考虑使用 foldl 和一些 haskell 魔法来配合它，但目前我被卡住了。

提前致谢

4

3 回答 3

4

首先，您的sortEm函数名称具有误导性，它不会对其参数列表进行排序，而是将其头部元素插入其尾部。碰巧的是，模块insert中已经有一个函数将其第一个参数插入到第二个参数中，因此存在等效性Data.List

sortEm (x:xs) === Data.List.insert x xs

现在，如果您将一个项目插入到一个已经排序的列表中，插入一个项目只会让您返回一个排序列表。由于空列表已排序，这myList就是您在 dave4420 的答案中得到的功能。那是一种“插入”排序，将列表的元素逐步插入到辅助列表中，最初为空。这就是你在 dave4420 答案中得到的第二个函数的作用：

insertionSort xs = foldr Data.List.insert [] xs

这确实“应用排序”，即仅插入“每个元素”一次。对于列表[a,b,c,...,z]，它相当于

insert a (insert b (insert c (... (insert z []) ...)))

您在评论中可能的意思，即“仅一次”比较（并可能交换）两个相邻元素，称为冒泡排序。当然，在一般情况下，只通过列表一次不会对其进行排序：

bubbleOnce xs = foldr g [] xs  where
  g x [] = [x]
  g x xs@(y:ys) | x>y       = y:x:ys  -- swap x and y in the output
                | otherwise = x:xs    -- keep x before y in the output

现在，bubbleOnce [4,2,6,1,8] ==> [1,4,2,6,8]. 您期望的值 ,将由从左到右的相反方向[2,4,1,6,8]应用折叠函数产生。但这在 Haskell 列表中就不那么自然了：g

bubbleOnce' [] = []
bubbleOnce' (x:xs) = let (z,h)=foldl g (x,id) xs in (h [z])  where
  g (x,f) y | x>y       = (x, f.(y:))   -- swap x and y in the output
            | otherwise = (y, f.(x:))   -- keep x before y in the output

（编辑 :)使用直接递归查看jimmyt 的答案以获得等效但简单且漂亮的版本。它也比这里的fodlr和foldl版本更懒惰（不那么严格）。

于 2012-06-12T09:07:15.787 回答
2 
myList []       = []
myList (x : xs) = sortEm (x : myList xs)

（未经测试）

或者就折叠而言：

myList = foldr cons []
  where cons x xs = sortEm (x : xs)

（也未经测试）

于 2012-06-11T22:25:27.630 回答
2 
-- if..then..else version
sortEM      ::  Ord a => [a] -> [a]

sortEM (x:y:xs)     =   if x < y
                        then x : sortEM (y:xs)
                        else y : sortEM (x:xs)
sortEM b            =   b   


-- guard version
sortEM_G    ::  Ord a => [a] -> [a]

sortEM_G (x:y:xs)
     | x < y        =   x : sortEM_G (y:xs)
     | otherwise    =   y : sortEM_G (x:xs)
sortEM_G b          =   b
于 2012-06-12T12:57:56.757 回答