haskellmonadsfoldable

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


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?


Solution

  • 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