如果按升序或降序排序或未在haskell中排序,请检查列表？

Question

我是Haskell的新手.我刚刚研究了Haskell两个星期.我真的不明白if else语句和haskell的列表理解是如何工作的.所以我想创建可以找出排序类型的函数,例如列表按升序或降序排序或根本不排序.我知道如何检查列表是按升序还是降序排序但我不知道如何检查列表是否完全没有排序.

data SortType = Ascending | Descending | NotSorted deriving (Show)

sorted :: (Ord a) => [a] -> TypeOfSort 
sorted [] = Ascending
sorted [x] = Ascending
sorted (x:y:xs) | x < y = sorted (y:xs) 
            | otherwise = Descending
sorted_  = Ascending

如果有人能告诉我该怎么做,那将是一个很大的帮助.谢谢.P/s:这不是作业/工作的东西,而是我想要学习的东西.

Answer 1

你的功能有问题的部分是| otherwise = Descending.根据你的函数定义,如果列表中有两个连续的例子x >= y,那么函数就是降序.这不是True:如果所有两个连续元素x > y(或者x >= y如果您不要求它严格下降),则函数正在下降.

此外,另一个问题是具有一个元素(或没有元素)的列表可以看作是Ascending和Descending.所以我认为我们要做的第一件事就是定义一些语义.我们可以决定将输出作为TypeOfSort项目列表,或者我们可以决定扩展选项的数量TypeOfSort.

在这个答案中,我将选择最后一个选项.我们可以扩展TypeOfSort到:

data TypeOfSort = Ascending | Descending | Both | NotSorted
    deriving (Show)

现在我们可以处理函数本身.这里的基本情况当然是空列表[]和带有一个元素的列表[_]:

sorted [] = Both
sorted [_] = Both

现在我们需要定义归纳案例.什么时候列表是按升序排序的？如果所有元素都(严格地)大于前一个元素.模拟如果所有元素(严格地)小于前一元素,则列表按降序排序.现在让我们假设严格.以后很容易改变函数定义.

所以,如果我们有两个或多个元素的列表,列表是Ascending如果有第二个元素开始的列表Ascending或Both和x < y,或者换句话说:

sorted (x:y:xs) | Both <- sort_yxs, x < y = Ascending
                | Ascending <- sort_yxs, x < y = Ascending
    where sort_yxs = sorted (y:xs)

同样适用于降序:如果列表的其余部分按降序排列,并且第一个元素大于第二个,则列表按降序排列:

                | Both <- sort_yxs, x > y = Descending
                | Ascending <- sort_yxs, > y = Descending
    where sort_yxs = sorted (y:xs)

在所有剩余的情况下,这意味着列表的Ascending某些部分是,而某些部分是Descending,所以列表是NotSorted.

                | otherwise = NotSorted

或者把这些放在一起:

sorted [] = Both
sorted [_] = Both
sorted (x:y:xs) | Both <- sort_yxs, x < y = Ascending
                | Ascending <- sort_yxs, x < y = Ascending
                | Both <- sort_yxs, x > y = Descending
                | Ascending <- sort_yxs, x > y = Descending
                | otherwise = NotSorted
    where sort_yxs = sorted (y:xs)

重构:制作TypeOfSort一个Monoid

上面的定义包含很多边缘情况,这使得编写简单程序变得困难.通过引入一些实用功能,我们可以更容易.例如,这可以通过定义一个需要两个TypeOfSorts然后返回交集的函数来完成.这样的功能看起来像:

intersect Both x = x
intersect x Both = x
intersect Ascending Ascending = Ascending
intersect Descending Descending = Descending
intersect _ _ = NotSorted

这实际上形成了一个带有身份元素的幺半群Both:

instance Monoid where
    mappend Both x = x
    mappend x Both = x
    mappend Ascending Ascending = Ascending
    mappend Descending Descending = Descending
    mappend _ _ = NotSorted

    mempty = Both

现在我们可以将我们的定义重写为:

sorted [] = Both
sorted [_] = Both
sorted (x:y:ys) | x > y = mappend rec Ascending
                | x < y = mappend rec Descending
                | otherwise = NotSorted
    where rec = sorted (y:ys)