如何在Haskell中使用两个过滤器?

Question

我想写一个函数，打印所有排序后的子序列和另一个条件。

我已经实现了一个函数，它显示所有排序的子序列如下:

allSubseqs:: Ord a => [a] -> [[a]]
allSubseqs =  filter' isSorted . subsequences  

我想做进一步的筛选，只选择具有最大长度的列表。我知道如何用let来做，但我想直接将它添加到allSubseqs函数:

这是代码的结果，它是正确的:

[[3,5,7,8],[1,5,7,8],[1,2,7,8]]

Answer 1

好吧，其中一个let可以直接离开;你的let x2 = x1没有做什么，我们可以把x2替换成x1。

main :: IO ()
main = do
  let x1 = allSubseqs2 [6,3,1,5,2,7,8,1]
  print $ filter' ((==) (maximum (map' length x1)) . length) x1

从技术上讲，我们也可以用allSubseqs2 [...]替换x1的所有出现，但不幸的是，这将计算两次子序列。所以let必须留下来。

如果需要的话，我们仍然可以将对allSubseqs2和filter'的调用分离出来，将它们合并到一个函数中。它看起来几乎相同，只是替换print与…没有什么!

longSubseqs values = do
  let x1 = allSubseqs2 values
  filter' ((==) (maximum (map' length x1)) . length) x1

实际上，这有点欺骗性;大多数Haskellers在看到do块时会期望有一些一元的事情发生，而这里没有这样的事情发生。让我们把do/let改成let/in:

longSubseqs values = let x1 = allSubseqs2 values in
  filter' ((==) (maximum (map' length x1)) . length) x1

使用任意一个定义，我们现在可以写出更短的main:

main = print $ longSubseqs [6,3,1,5,2,7,8,1]
-- OR
main = do
  print $ longSubseqs [6,3,1,5,2,7,8,1]

Answer 2

听起来您在尝试使您的功能与点无关。也就是说，您希望将所有筛选器和列表操作定义为一系列函数应用程序，而不是使用变量和let绑定。这当然是可行的!

我喜欢的一种很好的方法是使用箭头组合子而不是(.)，因为它允许定义函数的从左到右的管道，而不是典型的(数学)从右到左的组合。我们将从导入开始:

import Control.Arrow ((>>>), (&&&))

>>>运算符只是翻转组合，我们稍后会回到&&&。

现在，让我们把allSubseqs函数写成这个箭头样式:

allSubseqs:: Ord a => [a] -> [[a]]
allSubseqs = subsequences >>> filter' isSorted

接下来，我们想要执行另一个过滤器，这次是针对列表的长度，但我们还需要知道列表的最大长度。通常，这里应该使用let语句或变量绑定(就像您所做的那样)，但是，我们可以使用&&&。&&&组合子接受两个函数，每个函数接受相同的输入，并产生一对函数的输出。我们可以用它来代替let，像这样:

allSubseqsAndLongestLength :: Ord a => [a] -> (Int, [[a]])
allSubseqsAndLongestLength = subsequences 
    >>> filter' isSorted 
    >>> (maximum . map' length) &&& id

到目前为止的输出现在是一对排序子序列的最大长度，以及所有排序子序列的列表。现在是时候将其导入最终过滤器:

allLongestSubseqs :: Ord a => [a] -> [[a]]
allLongestSubseqs = subsequences 
    >>> filter' isSorted 
    >>> (maximum . map' length) &&& id
    >>> uncurry (filter' . (. length) . (==))

我们可以把最后一行写成>>> ((maxLen, lst) -> filter' ((== maxLen) . length) lst)，但是我冒昧地把它写成像函数的其他部分一样没有点。

你知道了!您甚至可以根据需要添加更多的filter s或其他列表操作，只需将它们组合到链的末尾。

Answer 3

使用"范式，又称Schwartzian转换，就像在db2的答案中一样，让您在准备好要处理的数据之后，在链中拥有额外的过滤器。

但是最好在这里完全避免第二个过滤器，首先按顺序生成子列表，最长的第一个，然后只取head元素:

longestSorted :: Ord a => [a] -> [[a]]
longestSorted = rpowers >>>
   map (filter isSorted) >>>
   dropWhile null >>>
   concat . take 1
-- > longestSorted [1,4,3,5]
-- [[1,4,5],[1,3,5]]

使用rpowers从这个答案:

-- longest first:
rpowers :: [a] -> [ [[a]]]
rpowers []     =  [ [[]] ]
rpowers (x:xs) = 
     [ map (x:) b ++ a |  (a:b:_) <- tails ([[]] ++ rpowers xs) ] 
      ++          [ [[]] ] 
-- shortest first, for comparison:
powers :: [a] -> [ [[a]]]
powers []     =  [ [[]] ]
powers (x:xs) =  [ [[]] ] ++
     [ map (x:) a ++ b |  (a:b:_) <- tails (powers xs ++ [[]]) ]