list - haskell列表和功能

Question

这是过去几天让人抓狂的作业。

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

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

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 魔法来配合它，但目前我陷入了困境。

提前致谢

Answer 1

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

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

现在，如果您将项目插入到已排序的列表中，则插入项目只会返回已排序的列表。由于空列表已排序，这就是您在 dave4420 的答案中得到的 myList 函数的作用。那是一个"insertion" sort ，逐步将列表元素插入辅助列表(最初为空)。这就是您在 dave4420 答案中得到的第二个函数的作用:

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

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

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

您在评论中可能的意思，即比较(并可能交换)两个相邻元素“仅一次”，被称为 bubble sort 。当然，在一般情况下，仅遍历列表一次不会对其进行排序:

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] 是从相反方向(从左到右)应用折叠函数 g 得到的结果。正确的。 但是这里使用 Haskell 列表就不太自然了:

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's answer使用直接递归的等效但简单且漂亮的版本。它也比这里的 fodlr 和 foldl 版本更懒(不太严格)。