CODEWITHSUNDEEP
haskellmonads
sevo
sevo

Reputation: 4609

What would an idiomatic, monadic version of maximumBy look like?

How can I get a maximum element of an effectful container where computing attribute to compare against also triggers an effect?

There has to be more readable way of doing things like:

latest dir = Turtle.fold (z (ls dir)) Fold.maximum

z :: MonadIO m => m Turtle.FilePath -> m (UTCTime, Turtle.FilePath)
z mx = do
    x <- mx
    d <- datefile x
    return (d, x)

I used overloaded version rather than non-overloaded maximumBy but the latter seems better suite for ad-hoc attribute selection.

How can I be more methodic in solving similar problems?

Upvotes: 1

Views: 177

Answers (3)

dfeuer
dfeuer

Reputation: 48611

Since you're already familiar with Fold, you might want to get to know FoldM, which is similar.

data FoldM m a b =
  -- FoldM step initial extract
  forall x . FoldM (x -> a -> m x) (m x) (x -> m b)

You can write:

maximumOnM ::
  (Ord b, Monad m)
  => (a -> m b) -> FoldM m a (Maybe a)
maximumOnM f = FoldM combine (pure Nothing) (fmap snd)
  where
    combine Nothing a = do
      f_a <- f a
      pure (Just (f_a, a))
    combine o@(Just (f_old, old)) new = do
      f_new <- f new
      if f_new > f_old
        then pure $ Just (f_new, new)
        else pure o

Now you can use Foldl.foldM to run the fold on a list (or other Foldable container). Like Fold, FoldM has an Applicative instance, so you can combine multiple effectful folds into one that interleaves the effects of each of them and combines their results.

Upvotes: 1

sevo
sevo

Reputation: 4609

It's possible to run effects on foldables using reducers package.

I'm not sure if it's correct, but it leverages existing combinators and instances (except for Bounded (Maybe a)).

import Data.Semigroup.Applicative (Ap(..))
import Data.Semigroup.Reducer (foldReduce)
import Data.Semigroup (Max(..))
import System.IO (withFile, hFileSize, IOMode(..))

-- | maxLength
--
-- >>> getMax $ maxLength ["abc","a","hello",""]
-- 5
maxLength :: [String] -> (Max Int)
maxLength = foldReduce . map (length)

-- | maxLengthIO
--
-- Note, this runs IO...
--
-- >>> (getAp $ maxLengthIO ["package.yaml", "src/Lib.hs"]) >>= return . getMax
-- Just 1212
--
-- >>> (getAp $ maxLengthIO []) >>= return . getMax
-- Nothing
maxLengthIO :: [String] -> Ap IO (Max (Maybe Integer))
maxLengthIO xs = foldReduce (map (fmap Just . f) xs) where
    f :: String -> IO Integer
    f s = withFile s ReadMode hFileSize

instance Ord a => Bounded (Maybe a) where
    maxBound = Nothing
    minBound = Nothing

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 153152

So I know nothing about Turtle; no idea whether this fits well with the rest of the Turtle ecosystem. But since you convinced me in the comments that maximumByM is worth writing by hand, here's how I would do it:

maximumOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m a
maximumOnM cmp [x] = return x -- skip the effects if there's no need for comparison
maximumOnM cmp (x:xs) = cmp x >>= \b -> go x b xs where
    go x b [] = return x
    go x b (x':xs) = do
        b' <- cmp x'
        if b < b' then go x' b' xs else go x b xs

I generally prefer the *On versions of things -- which take a function that maps to an Orderable element -- to the *By versions -- which take a function that does the comparison directly. A maximumByM would be similar but have a type like Monad m => (a -> a -> m Ordering) -> [a] -> m a, but this would likely force you to redo effects for each a, and I'm guessing it's not what you want. I find *On more often matches with the thing I want to do and the performance characteristics I want.

Upvotes: 5

Related Questions