Broad search for any `Foldable`

Lib.hs

-- Inspired by the level-monad package by Sebastian Fischer
module Lib
    ( search
    ) where

import Data.Foldable (fold)
import Data.Monoid (First(..))

newtype Levels m = Levels { levels :: [m] }

instance Monoid m => Semigroup (Levels m) where
    Levels xs <> Levels ys = Levels (mempty : merge xs ys)
instance Monoid m => Monoid (Levels m) where
    mempty = Levels []

merge :: Semigroup m => [m] -> [m] -> [m]
merge []      ys    = ys
merge xs      []    = xs
merge (x:xs) (y:ys) = x <> y : merge xs ys

search :: Foldable t => (a -> Bool) -> t a -> Maybe a
search f = getFirst . fold . levels . foldMap yield
    where yield x = Levels [First $ if f x then Just x else Nothing]

Lib2.hs

-- Bikeshedding. In a style that I love, but not clearer.
module Lib
    ( search
    ) where

import Data.Foldable (fold)
import Data.Monoid (First(..))
import Control.Monad (mfilter)
import Data.Coerce (Coercible, coerce)

newtype Levels m = Levels [m]

instance Monoid m => Semigroup (Levels m) where
    Levels xs <> Levels ys = Levels (mempty : merge xs ys)
instance Monoid m => Monoid (Levels m) where
    mempty = Levels []

merge :: Semigroup m => [m] -> [m] -> [m]
merge []      ys    = ys
merge xs      []    = xs
merge (x:xs) (y:ys) = x <> y : merge xs ys

bfs :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
bfs f = fold . ala Levels foldMap (pure . f)

search :: Foldable t => (a -> Bool) -> t a -> Maybe a
search f = ala First bfs (mfilter f . pure)

ala :: Coercible m n => (n -> m) -> ((a -> m) -> b -> m) -> (a -> n) -> b -> n
ala _ = coerce