<div dir="ltr"><div>Hello Cafe,</div><div><br></div><div>I wanted to try and write a median filter with good complexity and performance. This is just an exercise, so there is no use looking for better performance algorithms (median of medians).</div><div><br></div><div>Below is the code I came up with:</div><div><br></div><div>import Control.Monad.State<br>import System.Random<br><br>type MyState s = State (Int, Int, [(Int, s)])<br><br>-- Inserts a value in its sorted place,<br>-- Removes all expired values encountered,<br>-- Returns the median value of the list.<br>insertSorted :: (Ord a) => a -> MyState a a<br>insertSorted v = do<br>  (size, index, list) <- get<br>  let flt = valid size index        -- Filter: If too old remove value<br>      cmp (_,x) = v < x             -- Compare: If v spot reached, add v<br>      ret = min index size `div` 2  -- The return value's index<br>  let (newList, med) = goThrough flt cmp ret (index, v) list<br>  put (size, index + 1, newList)<br>  return . snd $ med<br><br>-- Internal implementation<br>goThrough :: (a -> Bool) -> (a -> Bool) -> Int -> a -> [a] -> ([a], a)<br>goThrough _ _ _ v [] = ([v], v)<br>goThrough flt cmp idx v ls@(x:xs)<br>  | flt x && cmp x = if idx == 0 then (v:ls, v)<br>                                 else (v:ls, getTo idx (v:ls))<br>  | flt x = let (ys, y) = goThrough flt cmp (max 0 (idx-1)) v xs<br>            in if idx == 0 then (x:ys, x)<br>                           else (x:ys, y)<br>  | otherwise = goThrough flt cmp idx v xs<br><br>-- Continues going through the list until we get to the element we want, or we<br>-- run out of elements, in which case we take the last one<br>getTo :: Int -> [a] -> a<br>getTo _ [] = error "No value to return!"<br>getTo _ [x] = x<br>getTo 0 (x:_) = x<br>getTo i (_:xs) = getTo (i-1) xs<br><br>-- A value is valid if it still has a place in the list (hasn't expired)<br>valid :: Int -> Int -> (Int, a) -> Bool<br>valid size index (i,_) = index - i < size<br><br>-- Clean up all the old values in the list. This is costly, and should be<br>-- performed sparingly<br>clean :: MyState Double ()<br>clean = do<br>  (size, index, list) <- get<br>  put (size, index, filter (valid size index) list)<br><br>-- Insert n values with insertSorted<br>insertList :: [Double] -> MyState Double [Double]<br>insertList ls = sequence $ insertSorted <$> ls<br><br>-- Example<br>main :: IO ()<br>main = do<br>  values <- sequence $ replicate 10000 $ randomRIO (1,100::Double)<br>  print $ runState (insertList values <* clean) (10, 0, [])<br>  return ()</div><div><br></div><div>The code works, at least in the simple cases I've tried.</div><div>It seems, however, way too complex and not very composable.</div><div>So I was wondering if anyone could tell me where I went wrong, and how I can make the code simpler and smaller.</div><div><br></div><div>Of course, it is completely possible to divide my insertion function, but the goal is to do all of the steps in one iteration over the list. This allows me to later compare what I have with divided functions to discover if the compiler would optimize them into one traversal.</div><div><br></div><div>But even with its current logic, I believe the code can be better written. I just don't know how :p</div><div><br></div><div>So I really appreciate any advice on how to make it better (or fix a bug I missed, or maybe even the logic of the whole algorithm).</div><div><br></div><div>Cheers,</div><div>Michel :)<br></div></div>