How to use tow filters in Haskell?

Question

I want to write a function that prints all the subsequences that are sorted and another condition.

I already implemented a function that shows all the sorted subsequences as this:

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

I want to do further filters to select only the list with the maximum length. I know how to do it with let, but I want to add it to allSubseqs function directly:

This is the results of the code and it is correct:

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

Answer 1

Using the "decorate-process-undecorate" paradigm a.k.a. Schwartzian transform as in DDub's answer lets you have the additional filter in the chain, after preparing the data for it to work on.

But it could be better to avoid that second filter entirely here, by generating the sublists in order in the first place, longest first, then just taking the head element:

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]]

This uses rpowers from this answer:

-- 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 ++ [[]]) ]

Answer 2

It sounds like you're trying to make your function point-free. That is, you want to define all of your filters and list manipulations as a sequence of function applications rather than with variable and let bindings. That's certainly doable!

One nice way to go about this that I like is to use the arrow combinators rather than (.), as it allows one to define a left-to-right pipeline of functions rather than the typical (mathematical) right-to-left composition. We'll start with the import:

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

The >>> operator is just flipped composition, and we'll come back to &&& in a bit.

Now, let's take your allSubseqs function and write it in this arrow style:

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

Next, we want to do another filter, this time on the length of the list, but we also need to know the maximum length of the list. Typically, this is where one would use a let statement or variable binding (as you did), but instead, we can use &&&. The &&& combinator takes two functions, each of which takes the same input, and produces a pair of the outputs of the functions. We can use it in place of the let like so:

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

The output so far is now a pair of the maximum length of a sorted subsequence along with the list of all sorted subsequences. It's time to pipe this into the final filter:

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

We could have written that last line as >>> (\(maxLen, lst) -> filter' ((== maxLen) . length) lst), but I took the liberty of making it point-free like the rest of the function.

There you have it! You can even add more filters or other list manipulations as you want by simply composing them onto the end of the chain.

Answer 3

Well, one of the lets can go straight off; your let x2 = x1 isn't really doing much, and we can just replace x2 with x1 everywhere.

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

Technically, we could also replace all occurrences of x1 with allSubseqs2 [...], but that would, unfortunately, compute the subsequences twice. So that let must stay.

Still, we can factor out the call to allSubseqs2 and filter', combining them in a single function, if that's desired. It looks almost identical, just replacing print with... nothing!

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

Actually, this is a bit deceptive; most Haskellers will expect there to be something monadic going on when they see a do block, and there isn't any such thing going on here. Let's just change that do/let to a let/in:

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

Using either definition, we can now write a shorter 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]