Can you determine the min or max of a list using only the list monad?

user_4740467 0
Viewed 290

Trying to understand the relation between Monad and Foldable. I am aware that that part of the value of the Monad, Applicative and Functor typeclasses is their ability to lift functions over structure, but what if I wanted to generate a summary value (e.g. min or max) for the values contained in a Monad?

This would be impossible without an accumulator right (like in foldable)? And to have an accumulator you have to inject or destroy structure?

min :: Ord a => a -> a -> a

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin t = foldr go Nothing t
  where
    go x Nothing = Just x
    go x (Just y) = Just (min x y)

Here, the Nothing value is the accumulator. So it would not be possible to do an operation that produces a summary value like this within the confines of a do block?

foldable monads haskell
3 Answers

I'm not entirely sure I understand the question, so forgive me if this isn't a useful answer, but as I understand it, the core of the question is this:

So it would not be possible to do an operation that produces a summary value like this within the confines of a do block?

Correct, that would not be possible. Haskell's do notation is syntactic sugar over Monad, so basically syntactic sugar over >>= and return.

return, as you know, doesn't let you 'access' the contents of the Monad, so the only access to the contents you have is via >>=, and in the case of the list monad, for instance, that only gives you one value at a time.

Notice that Foldable doesn't even require that the data container is a Functor (much less a Monad). Famously, Set isn't a Functor instance, but it is a Foldable instance.

You can, for example, find the minimum value in a set:

Prelude Data.Foldable Set> foldr (\x -> Just . maybe x (min x)) Nothing $ Set.fromList [42, 1337, 90125, 2112]
Just 42
user_1260140

The contrived and inefficient code below is the closest I can get to "using only the list monad". This is probably not what the OP is looking for, but here it is.

I also exploit head (which you can replace with listToMaybe, if we want totality), and null. I also use empty (which you can replace with []).

The code works by non deterministically picking an element m and then checking that no greater elements exist. This has a quadratic complexity.

import Control.Applicative

maximum :: Ord a => [a] -> a
maximum xs = head maxima
   where
   isMax m = null $ do
      x <- xs
      if x > m
         then return x
         else empty
   maxima = do
      m <- xs   -- non deterministically pick a maximum
      if isMax m
         then return m
         else empty
user_32349590

I'm also not sure, what the actual question ist, but the need for an accumulator can be hidden with a Monoid instance. Then - for your minimum example - you can use use foldMap from Data.Foldable to map and merge all values of your Foldable. E.g.:

data Min a = Min { getMin :: Maybe a } deriving Show

instance Ord a => Monoid (Min a) where
  mempty                                = Min Nothing
  mappend a (Min Nothing)               = a
  mappend (Min Nothing) b               = b
  mappend (Min (Just a)) (Min (Just b)) = Min (Just (min a b))

foldMin :: (Foldable t, Ord a) => t a -> Maybe a
foldMin = getMin . foldMap (Min . Just)
user_41422660
Related