haskellfunctional-programminglis

How can I use isSrderd and subsequences?


The goal is to find the Longest Increasing Subsequence (LIS) of a list in Haskell. I tried to run the following code, but the error of couldn't find modules appeared. I saw answers to This question and I understand that the ordered package is old and not used anymore.

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]

Therefore, I tried to use only:

import Data.List

but I got the following error :

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

Solution

  • nub is now in Data.List. If an isSorted function is available in any normal library, Hoogle doesn't show it. You can easily write one yourself, though I haven't given much thought to whether the following suggestion is the most efficient implementation - and it probably doesn't work with infinite lists (I think that the answer to both questions is no):

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

    (Using sort from Data.List.)

    With these imports:

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

    the lis function now compiles.