find a predicessor and succesor in an ordered list with haskell

find_ps.hs

-- GHCi, version 8.8.4
-- explain video - https://www.youtube.com/watch?v=oCiR3Rk7H_Y&t=1390s
import Data.Maybe
-- https://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/
-- predecessor and succesor of an element in a sorted list (no duplicates)

--staightforward solution - get lower elements and extract maximum
-- find predecessor
fp :: Ord a => [a] -> a -> Maybe a
fp [] _ = Nothing
fp xs e
   | not $ elem e xs = Nothing
   | length lt > 0 = Just $ maximum lt
   | otherwise = Nothing
      where lt = [x | x <-xs, x<e]

fs :: Ord a => [a] -> a -> Maybe a
fs [] _ = Nothing
fs xs e
   | not $ elem e xs = Nothing
   | length gt > 0 = Just $ minimum gt
   | otherwise = Nothing
      where gt = [x | x <-xs, x>e]


-- binary search find predecssor, list sorted, no duplicates
-- log N time (in theory)
bfp :: Ord a => [a] -> a -> Maybe a
bfp xs e = go Nothing False xs where
                              go bc f [] = if f then bc else Nothing
                              go bc f xs | e > me = go bc' f r
                                         | e < me = go bc f l
                                         | e == me = go bc True l
                                            where bc' = if isNothing bc then Just me else (max me) <$> bc
                                                  (l,(me:r)) = splitAt mi xs
                                                  mi = (length xs) `div` 2

bfs :: Ord a => [a] -> a -> Maybe a
bfs xs e = go Nothing False xs where
                              go bc f [] = if f then bc else Nothing
                              go bc f xs | e > me = go bc f r
                                         | e < me = go bc' f l
                                         | e == me = go bc True r
                                            where bc' = if isNothing bc then Just me else (min me) <$> bc
                                                  (l,(me:r)) = splitAt mi xs
                                                  mi = (length xs) `div` 2


bf :: Ord a => [a] -> a -> (Maybe a, Maybe a)
bf xs e = (bfp xs e, bfs xs e)

-- find pred despite element in a list


bfp_ :: Ord a => [a] -> a -> Maybe a
bfp_ xs e = go Nothing xs where
                              go bc [] = bc
                              go bc xs | e > me = go bc' r
                                         | e < me = go bc l
                                         | e == me = go bc l
                                            where bc' = if isNothing bc then Just me else (max me) <$> bc
                                                  (l,(me:r)) = splitAt mi xs
                                                  mi = (length xs) `div` 2


bfs_ :: Ord a => [a] -> a -> Maybe a
bfs_ xs e = go Nothing xs where
                              go bc [] = bc
                              go bc xs | e > me = go bc r
                                         | e < me = go bc' l
                                         | e == me = go bc r
                                            where bc' = if isNothing bc then Just me else (min me) <$> bc
                                                  (l,(me:r)) = splitAt mi xs
                                                  mi = (length xs) `div` 2


bf_ :: Ord a => [a] -> a -> (Maybe a, Maybe a)
bf_ xs e = (bfp_ xs e, bfs_ xs e)

explain video - https://www.youtube.com/watch?v=oCiR3Rk7H_Y&t=1390s