如何使用 isSrderd 和子序列？

Question

目标是在 Haskell 中找到列表的最长递增子序列 (LIS)。我尝试运行下面的代码，但是出现找不到模块的错误。我看到了 This question 的答案，我知道订购的包裹已经旧了，不再使用了。

import Data.Ord          ( comparing )
import Data.List         ( maximumBy, subsequences )
import Data.List.Ordered ( isSorted, nub )
lis :: Ord a => [a] -> [a]
lis = maximumBy (comparing length) . map nub  . filter isSorted . subsequences                 
--    longest                    <-- unique <-- increasing    <-- all      

main = do
print $ lis [3,2,6,4,5,1]
print $ lis [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
print $ lis [1,1,1,1]

因此，我尝试只使用：

import Data.List

但我收到以下错误：

main.hs:3:18: error:
    Variable not in scope:
       comparing :: (t0 a0 -> Int) -> [a] -> [a] -> Ordering
  |
3 | lis = maximumBy (comparing length) . map nub  . filter isSorted . subsequences                 
  |                  ^^^^^^^^^

main.hs:3:56: error: Variable not in scope: isSorted :: [a] -> Bool
  |
3 | lis = maximumBy (comparing length) . map nub  . filter isSorted . subsequences                 
  |                                                        ^^^^^^^^
exit status 1

Answer 1

nub 现在在 Data.List。如果 isSorted 函数在任何普通库中可用，Hoogle doesn't show it。你可以很容易地自己写一个，尽管我没有考虑以下建议是否是最有效的实现——它可能不适用于无限列表（我认为这两个问题的答案都是没有):

isSorted :: Ord a => [a] -> Bool
isSorted l = sort l == l

（使用 Data.List 中的 sort。）

使用这些导入：

import Data.Ord (comparing)
import Data.List (maximumBy, subsequences, nub, sort)

lis 函数现在可以编译。

如何使用 isSrderd 和子序列？

How can I use isSrderd and subsequences?

haskell

functional-programming

lis