1

I'm sure I am missing something very obvious here. Here's what I'm trying to achieve at a conceptual level:

action1 :: (MonadIO m) => m [a]
action1 = pure []

action2 :: (MonadIO m) => m [a]
action2 = pure [1, 2, 3]

action3 :: (MonadIO m) => m [a]
action3 = error "should not get evaluated"

someCombinator [action1, action2, action3] == m [1, 2, 3]

Does this hypothetical someCombinator exist? I have tried playing round with <|> and msum but couldn't get what I want.

I guess, this could be generalised in two ways:

-- Will return the first monadic value that is NOT an mempty 
-- (should NOT blindly execute all monadic actions)
-- This is something like the msum function

someCombinator :: (Monoid a, Monad m, Traversable t, Eq a) => t m a -> m a

-- OR

-- this is something like the <|> operator

someCombinator :: (Monad m, Alternative f) => m f a -> m f a -> m f a
duplode
  • 33,731
  • 7
  • 79
  • 150
Saurabh Nanda
  • 6,373
  • 5
  • 31
  • 60

2 Answers2

3

I'm not aware of a library that provides this, but it's not hard to implement:

someCombinator :: (Monoid a, Monad m, Foldable t, Eq a) => t (m a) -> m a 
someCombinator = foldr f (pure mempty)
    where
        f item next = do
            a <- item
            if a == mempty then next else pure a

Note that you don't even need Traversable: Foldable is enough.

Fyodor Soikin
  • 78,590
  • 9
  • 125
  • 172
  • Just ended up writing something similar at https://stackoverflow.com/questions/59798509/filter-for-first-matching-monadic-action-without-evaluating-all-actions -- I'm surprised something like `filterFirstM` doesn't already exist in the standard library. – Saurabh Nanda Jan 18 '20 at 07:40
  • Actually, I'm unable to wrap my head around your `foldlr`-based implementation. Is this going to give me the first "non-empty" value from L-to-R or R-to-L? – Saurabh Nanda Jan 18 '20 at 07:41
  • Left to right. Keep in mind that `foldr f z [x1, x2, x3] == f x1 (f x2 (f x3 z))` – Fyodor Soikin Jan 18 '20 at 07:42
  • The foldr based implementation is better than my foldl based implementation. I'll keep this question open for a few days, to see if someone comes up with an in-build/standard combinator. – Saurabh Nanda Jan 18 '20 at 07:49
  • btw, doesn't this need to be be `foldrM` instead of simply `foldr`? – Saurabh Nanda Jan 18 '20 at 10:08
  • I'm still stuck with `foldl` vs `foldr`. In `foldl` the initial value is the very first value of the accumulator/memo. In `foldr` is the initial value actually the LAST value (or terminal) value of the accumulator? It has to be, otherwise this is going to evaluate every single action, right? – Saurabh Nanda Jan 18 '20 at 10:16
  • 1
    @SaurabhNanda Keep in mind that `foldr f z [x1, x2, x3 ...] == f x1 (foldr f z [x2, x3 ...])`. so the rest of list `[x2, x3 ...]` is still unexplored when `f` is called with its two arguments -- `x1` and `(foldr f z [x2, x3 ...])`. and *if* `f` is lazy enough and won't demand the value of its second argument before returning a result, then, the rest of list `[x2, x3 ...]` will remain unexplored when the result is returned. this means the input list is explored left-to-right when `f` is non-strict in its second argument. – Will Ness Jan 18 '20 at 12:49
  • @SaurabhNanda see if the equivalent rewrite `f item next = do { a <- item ; if a == mempty then do { r <- next ; return r } else return a }` is clearer for you. --- and no, `foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b` so it uses the `a -> b -> m b` combining function to turn `t a` into `m b`, but `f :: m a -> m a -> m a` and `foldr f (pure mempty)` turns `t (m a)` into `m a`. – Will Ness Jan 18 '20 at 13:00
  • and if it were `a ~ m b`, we'd have `foldrM :: (Foldable t, Monad m) => (m b -> b -> m b) -> b -> t (m b) -> m b` which is still not the same. – Will Ness Jan 18 '20 at 13:03
2

On an abstract level, the first non-empty value is a Monoid called First. It turns out, however, that if you just naively lift your IO values into First, you'll have a problem with action3, since the default monoidal append operation is strict under IO.

You can get lazy monoidal computation using the FirstIO type from this answer. It's not going to be better than Fyodor Soikin's answer, but it highlights (I hope) how you can compose behaviour from universal abstractions.

Apart from the above-mentioned FirstIO wrapper, you may find this function useful:

guarded :: Alternative f => (a -> Bool) -> a -> f a
guarded p x = if p x then pure x else empty

I basically just copied it from Protolude since I couldn't find one in base that has the desired functionality. You can use it to wrap your lists in Maybe so that they'll fit with FirstIO:

> guarded (not . null) [] :: Maybe [Int]
Nothing
> guarded (not . null) [1, 2, 3] :: Maybe [Int]
Just [1,2,3]

Do this for each action in your list of actions and wrap them in FirstIO.

> :t (firstIO . fmap (guarded (not . null))) <$> [action1, action2, action3]
(firstIO . fmap (guarded (not . null))) <$> [action1, action2, action3]
  :: Num a => [FirstIO [a]]

In the above GHCi snippet, I'm only showing the type with :t. I can't show the value, since FirstIO has no Show instance. The point, however, is that you now have a list of FirstIO values from which mconcat will pick the first non-empty value:

> getFirstIO $ mconcat $ (firstIO . fmap (guarded (not . null))) <$> [action1, action2, action3]
Just [1,2,3]

If you want to unpack the Maybe, you can use fromMaybe from Data.Maybe:

answer :: IO [Integer]
answer =
  fromMaybe [] <$>
  (getFirstIO $ mconcat $ (firstIO . fmap (guarded (not . null))) <$> [action1, action2, action3])

This is clearly more complex than Fyodor Soikin's answer, but I'm fascinated by how Haskell enables you to assembling desired functionality by sort of 'clicking together' existing things, almost like Lego bricks.

So, to the question of does this combinator already exist? the answer is that it sort of does, but some assembly is required.

Mark Seemann
  • 225,310
  • 48
  • 427
  • 736
  • Thank you, for the detailed answer, Mark. I learnt about `First` and `FirstIO` from your answer. However, as you have noted, Fyodor's answer has lesser moving parts and is simpler to implement/understand. – Saurabh Nanda Jan 20 '20 at 07:00