A function determining intervals of values greater than threshold

Question

I wonder if there exists a shorter/more elegant functional programming way than listing all the possible cases. Here, a function that determines positions of beginning/end of subintervals greater than threshold is coded. The idea behind the listed code is to mark and retain the beginning of such an interval, then to push a tuple of (beginning,ending) as soon as the interval ends. Feel free to choose any other approach if needed.

-- | Determines the intervals greater than threshold.
--
-- Examples:
-- >>> intervals 0.5 [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0]
-- [(3,4),(8,10)]
-- >>> intervals 0.5 [1,0,0,0,1,1,0,0,0,1,1,1,0]
-- [(0,0),(4,5),(9,11)]
-- >>> intervals 0.5 [1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,1]
-- [(0,0),(4,5),(9,11),(13,15)]
intervals :: Ord a => a -> [a] -> [(Int, Int)]
intervals threshold ys = f False 0 p
  where p = zip [0..] . map (> threshold) $ ys
        f :: Bool -> Int -> [(Int, Bool)] -> [(Int, Int)]
        f _ _ [] = []
        f True startPos ((bPos,b):[]) | b = [(startPos, bPos)]
                                      | otherwise = [(startPos, startPos)]
        f False _ ((bPos,b):[]) | b = [(bPos, bPos)]
                                | otherwise = []
        f True startPos ((aPos,a):(bPos,b):as) | a && b = f True startPos ((bPos,b):as)
                                               | a && (not b) = ((startPos, aPos)) : (f False 0 as)
                                               | otherwise = (startPos, startPos) : (f False 0 ((bPos,b):as))
        f False _ ((aPos,a):as) | a = f True aPos as
                                | otherwise = f False 0 as

Answer 1

(You can skip right to TL;DR for a simpler approach)

Your function actually determines the indices of list elements that are above a threshold. In Haskell, when you have a list, an index is not the idiomatic way to represent its items. What do you want with those indices?

Agreed, your version is hard to read. For another approach, I start with

intervalsT :: [Bool] -> [(Int, Int]

and notice that the group function might come in handy to collect subsequent equal elements.

*Main> group [True,True,False,False,True]
[[True,True],[False,False],[True]]

mapping length will result in [2,2,1], which is a step closer to the indices. To turn [a,b,c] into [0,a ,a+b, a+b+c], the function scanl' is perfect:

*Main> scanl' (+) 0 [2,2,1]
[0,2,4,5]

which we can zip with its own tail. But wait! We lost information whether something is above or below threshold. zip it again with the grouped Bools, filter based on the bools, throw away the bools. This yields:

TL;DR

intervals p = intervalsT . map (>p)
intervalsT :: [Bool] -> [(Int,Int)]
intervalsT xs = let grouped = group xs
                    idx = scanl' (+) 0 . map length $ grouped
                    ivs = zip idx (map (subtract 1) $ tail idx)
                 in map snd $ filter fst $ zip (map head grouped) ivs

Answer 2

An alternative answer to "shorter functional programming way" would be using State monad. A possible plus of this method is preserving the same approach as in the original code while easier to comprehend. Downside of this version is its imperative/overcomplicated style.

import Control.Monad.State


type Result = [(Int, Int)]

check :: [Bool] -> State (Bool, Int, Int, Result) Result
check [] = do
    (started, startPos, pos, intervs) <- get
    return $ if started
      then (startPos, pos - 1) : intervs
      else intervs

check (x:xs) = do
    (started, startPos, pos, intervs) <- get
    let startPos' | x && started = startPos
                  | x = pos
                  | otherwise = -1
        intervs' | not x && started = (startPos, pos - 1) : intervs
                 | otherwise = intervs
        started' = x
    put (started', startPos', pos + 1, intervs')
    check xs

intervals :: Ord a => a -> [a] -> [(Int, Int)]
intervals threshold ys = reverse $ evalState (check ps) (False, 0, 0, [])
  where ps = map (> threshold) $ ys

main = do
  print $ intervals 0.5 [0,0,0,1,1,0,0,0,1,1,1,0]
  print $ intervals 0.5 [1,0,0,0,1,1,0,0,0,1,1,1,0]
  print $ intervals 0.5 [1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,1]