changePointIndexes.hs

import Data.Ord (comparing)
import Data.Function (on)
import Data.List (groupBy)

type Point = (Int, Int)

points :: [Point]
points = [ (0, 1)
         , (0, 2)
         , (0, 2)
         , (0, 2)
         , (0, 3)
         , (0, 2)
         , (0, 1)
         , (0, 0)
         , (0, 5)
         , (0, 3)
         , (0, 6)
         , (0, -3)
         ]

-- | compare each successive pair of (x,y) points
-- and output their ordering - LT, GT or EQ
-- ex: ySlope points = [GT,EQ,EQ,GT,LT,LT,LT,GT,LT,GT,LT]
ySlope :: [Point] -> [Ordering]
ySlope ps = zipWith (comparing snd) (drop 1 ps) ps

-- | given a list of points, output an (index, ordering) pair
-- each time the ySlope changes
-- ex: changes points = [(1,GT),(2,EQ),(4,GT),(5,LT),(8,GT),(9,LT),(10,GT),(11,LT)]
changes :: [Point] -> [(Int, Ordering)]
changes = map head . groupBy ((==) `on` snd) . zip [1..] . ySlope