Sub Sort

In [1]:

    

import Data.List
import Data.Function
import Data.Maybe


    

In [2]:

    

subSort :: (Ord a) => [a] -> (Int, Int)
subSort xs =
    let
        indexedList :: (Ord a) => [a] -> [(Bool, (a, Int))]
        indexedList xs = 
            let
                computeState :: (Ord a) => Maybe (Bool, (a, Int)) -> (a, Int) -> Maybe (Bool, (a, Int))
                computeState Nothing (x, i) = Just (False, (x, i))
                computeState (Just (f, (x', i'))) (x, i) = Just (x' <= x, (x, i)) 
            in
                catMaybes $ scanl computeState Nothing $ zip xs [0..]
    
        sortedGroups = map (map snd) $ groupBy ((/=) `on` fst) $ indexedList xs
    
        -- Think about special cases, i.e. empty list

        minValue = minimum $ map head $ tail sortedGroups
        maxValue = maximum $ map last $ init sortedGroups

        leftIndex = snd $ head $ dropWhile (< minValue) $ head sortedGroups
        rightIndex = snd $ last $ takeWhile (< maxValue) $ last sortedGroups

    in (leftIndex, rightIndex)


    

In [3]:

    

subSort [1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19]


    

    






(3,9)