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