CODEWITHSUNDEEP
haskell
Andrey
Andrey

Reputation: 15

How can I find the longest increasing section of numbers at list in Haskell?

For example list [1,3,4,3,6,7,3] gives result [1,3,4] or [3,6,7]. I can find only subsequence but not a section.

Edit

By Naive implementation I find subsequence

increasing :: Ord a => [a] -> [a]
increasing = maximumBy (comparing length) . map nub 
                                          . filter isSorted
                                          . subsequences

Upvotes: 1

Views: 1092

Answers (2)

user6428287
user6428287

Reputation:

Binary-predicate cut of a sequence; the cut occurs at the first pair (x1, x2) for which x1 <> x2 doesn’t hold:

biCut :: (a -> a -> Bool) -> [a] -> ([a], [a])
biCut (<>) (x1 : xs@(x2 : _)) | x1 <> x2  = let (tk, dp) = biCut (<>) xs
                                            in  (x1 : tk, dp)
                              | otherwise = ([x1], xs)
biCut _    xs                             = (xs, [])

(analogous to splitAt) or in terms of

biFst :: (a -> a -> Bool) -> [a] -> [a]
biFst (<>) (x1 : xs@(x2 : _)) | x1 <> x2  = x1 : biFst (<>) xs
                              | otherwise = [x1]
biFst _    xs                             = xs

biSnd :: (a -> a -> Bool) -> [a] -> [a]
biSnd (<>) (x1 : xs@(x2 : _)) | x1 <> x2  = biSnd (<>) xs
                              | otherwise = xs
biSnd _    _                              = []

(take and drop) such that forall (<>) xs.

biFst (<>) xs ++ biSnd (<>) xs  =  xs
                 biCut (<>) xs  =  (biFst (<>) xs, biSnd (<>) xs)    [CUT]

then

sections :: (a -> a -> Bool) -> [a] -> [[a]]
sections _    [] = []
sections (<>) xs = let (tk, dp) = biCut (<>) xs
                   in  tk : sections (<>) dp

such that

        concat . sections (<>)  =  id

“Sections” are non-empty subsequences for which the binary predicate <> holds between successors. Reformulating the standard maximumBy as a total function:

maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> Maybe a
maximumBy cmp xs | null xs   = Nothing
                 | otherwise = Just (foldl1 max' xs)
   where
      max' x y = case x `cmp` y of
                    LT -> y            -- Leftmost-biased
                    _  -> x

Then

longestAsc :: Ord a => [a] -> Maybe [a]
longestAsc = maximumBy (compare `on` length) . sections (<)

is the function.

      longestAsc [2,3,2,1,2,3]  =  Just [1,2,3]
              longestAsc [2,1]  =  Just [2]
                 longestAsc []  =  Nothing

Upvotes: 2

epsilonhalbe
epsilonhalbe

Reputation: 15967

It seems you are on a good way - and you already seem to know a lot - so I won't spoil the result for you.

At first I think you should change the type signature of your function

increasingSequences :: Ord a => [a] -> [[a]]

There is already one function that promises to be a solution to that problem from Data.List namely - groupBy, in the form of groupBy (<=).

But groupBy does not work as expected, it compares with the first element of each group - which is ok for groupBy (==) - but not for your case.

> ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/epsilonhalbe/.ghc/ghci.conf
Prelude> import Data.List
Prelude Data.List> groupBy (<=) [10,9..6]
[[10],[9],[8],[7],[6]]
Prelude Data.List> groupBy (<=) (1:[10,9..6])
[[1,10,9,8,7,6]]

so you need to implement that one yourself - the easiest version IMHO would be to use pattern matching and recursion - I would strongly suggest writing it and posting it here as an answer (I will check in the next few days and vote that one up if you do!)

If you really want a spoiler there is actually a wiki page that gives a solution to your problem.

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy rel [] = [] groupBy rel (x:xs) = (x:ys) : groupBy rel zs where (ys,zs) = groupByAux x xs groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) where (ys,zs) = groupByAux x xs groupByAux y xs = ([], xs)

Upvotes: 1

Related Questions