# Break with traverse / traverse\_?

**URL:** <https://discourse.haskell.org/t/break-with-traverse-traverse/9152>\
**Category:** Learn\
**Created:** [March 24, 2024, 1:32pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152 "2024-03-24T13:32:07Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Liamzy](https://avatars.discourse-cdn.com/v4/letter/l/50afbb/32.png) [@Liamzy](https://discourse.haskell.org/u/Liamzy)\
**Post date:** [March 27, 2024, 2:29pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/21 "2024-03-27T14:29:18Z")

</div>

I’m actually partial to where clauses, and given the choice, I’d prefer more specialized functions to abusing foldr all day.

But it’s in the idea of a “what’s the simplest possible dialect of Haskell”? Right now, I think it comes down to Foldable, Traversable, Functor, Applicative, Monad, which is actually the standard right now, isn’t it?

With the most “accessible” dialect in mind, then foldr abuse becomes warranted, using let instead of where becomes more warranted, and so on.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [March 27, 2024, 2:41pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/22 "2024-03-27T14:41:02Z")

</div>

Thanks! Those examples help me understand a lot more clearly what’s going on. Since I was playing around with the code anyway, here are the definitions of `foo` and `bar` with some sample outputs:

```haskell
import Control.Monad.IO.Class
import Control.Monad.Trans.Except
import Data.Traversable

foo :: [Int] -> IO [Int]
foo count = (either id pure =<<) . runExceptT . for count $ \u ->
    if even u
        then throwE $ [u] <$ putStrLn (show u <> " is Even!")
        else liftIO $ u <$ print u
-- ghci> foo [1,3,5,7]
-- 1
-- 3
-- 5
-- 7
-- [1,3,5,7]
-- ghci> foo [1,3,4,5,7]
-- 1
-- 3
-- 4 is Even!
-- [4]

bar :: [Int] -> IO [Int]
bar count =
    let act a k = if even a
            then [a] <$ putStrLn (show a <> " is even!")
            else const (a :) <$> print a <*> k in
    foldr act (pure []) count
-- ghci> bar [1,3,5,7]
-- 1
-- 3
-- 5
-- 7
-- [1,3,5,7]
-- ghci> bar [1,3,4,5,7]
-- 1
-- 3
-- 4 is even!
-- [1,3,4]

```

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [March 27, 2024, 4:50pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/23 "2024-03-27T16:50:55Z")

</div>

I would suggest using `ExceptT` and `either` in `foo` as follows:

```haskell
import Control.Monad.IO.Class
import Control.Monad.Trans.Except
import Data.Traversable

foo :: [Int] -> IO [Int]
foo count = runEarlyReturn $ for count $ \u ->
  if even u
    then do
      liftIO (putStrLn (show u <> " is Even!"))
      earlyReturn [u]
    else do
      liftIO (print u)
      pure u
-- ghci> foo [1,3,5,7]
-- 1
-- 3
-- 5
-- 7
-- [1,3,5,7]
-- ghci> foo [1,3,4,5,7]
-- 1
-- 3
-- 4 is Even!
-- [4]

runEarlyReturn :: Monad m => ExceptT b m b -> m b
runEarlyReturn m = (pure . either id id) =<< runExceptT m

earlyReturn :: Monad m => a -> ExceptT a m r
earlyReturn = throwE

```

However, `bar` is more subtle. It demonstrates well the need for lightweight streams/iterators. Luckily Bluefin (package: `bluefin`) has them! This is what `foo` and `bar` look like in Bluefin:

```haskell
import Bluefin.EarlyReturn (returnEarly, withEarlyReturn)
import Bluefin.IO (effIO, runEff)
import Bluefin.Jump (jumpTo, withJump)
import Bluefin.Stream (yield, yieldToList)
import Data.Foldable (for_)

foo :: [Int] -> IO [Int]
foo count = runEff $ \io -> do
  withEarlyReturn $ \early -> do
    (as, ()) <- yieldToList $ \y -> do
      for_ count $ \u -> do
        if even u
          then do
            effIO io (putStrLn (show u <> " is Even!"))
            returnEarly early [u]
          else do
            effIO io (print u)
            yield y u

    pure as
-- ghci> foo [1,3,5,7]
-- 1
-- 3
-- 5
-- 7
-- [1,3,5,7]
-- ghci> foo [1,3,4,5,7]
-- 1
-- 3
-- 4 is Even!
-- [4]

bar :: [Int] -> IO [Int]
bar count = runEff $ \io -> do
  (as, ()) <- yieldToList $ \y -> do
    withJump $ \break -> do
      for_ count $ \a -> do
        yield y a
        if even a
          then do
            effIO io (putStrLn (show a <> " is even!"))
            jumpTo break
          else
            effIO io (print a)

  pure as
-- ghci> bar [1,3,5,7]
-- 1
-- 3
-- 5
-- 7
-- [1,3,5,7]
-- ghci> bar [1,3,4,5,7]
-- 1
-- 3
-- 4 is even!
-- [1,3,4]

```

---

<div class="post-metadata">

**Author:** ![sullyj3](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sullyj3/32/2639_2.png) [@sullyj3](https://discourse.haskell.org/u/sullyj3)\
**Post date:** [April 2, 2024, 10:13am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/24 "2024-04-02T10:13:33Z")

</div>

> [@tomjaguarpaw](#):
>
> particular why you want to avoid `ExceptT`

For me, it’s a bit galling to have to reconfigure type signatures and add `run*` for a change that would be a one word statement in a Blub language. It feels like a lot of ceremony. It’s very surprising to me that others don’t relate to the experience of finding monad transformers a bit cumbersome in comparison to equivalent features in other languages.

---

<div class="post-metadata">

**Author:** ![sullyj3](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sullyj3/32/2639_2.png) [@sullyj3](https://discourse.haskell.org/u/sullyj3)\
**Post date:** [April 2, 2024, 10:19am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/25 "2024-04-02T10:19:52Z")

</div>

I really love Lean 4’s [solution to this](https://lean-lang.org/papers/do.pdf) (see section 4), where they soup up do notation with a desugaring of imperative looking loops to monad transformers, complete with `break`/`continue`.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [April 2, 2024, 10:48am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/26 "2024-04-02T10:48:43Z")

</div>

> [@sullyj3](#):
>
> […] a change that would be a one word statement in a Blub language.

To make this a more fair comparison, try to implement an algorithm which relies on laziness in a Blub-like language…

* * *

> [@sullyj3](#):
>
> I really love Lean 4’s solution […] where they soup up `do` notation with a desugaring of imperative looking loops to monad transformers, complete with `break`/`continue`.

…so they implemented their own miniature (version of a) Blub-like language - but will it be _“forwards compatible”_ with e.g. implicit parallelism? Or will much of that _“mini-Blub”_ have to be replaced with ordinary Lean?

---

<div class="post-metadata">

**Author:** ![sullyj3](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sullyj3/32/2639_2.png) [@sullyj3](https://discourse.haskell.org/u/sullyj3)\
**Post date:** [April 2, 2024, 11:03am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/27 "2024-04-02T11:03:25Z")

</div>

I’m not trying to advocate for imperative style per-se here, I’d be thrilled to see a solution in a more functional style with comparable ergonomics to `break`.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [April 2, 2024, 11:11am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/28 "2024-04-02T11:11:57Z")

</div>

When this thread first appeared, I remembered seeing a variant of one of the `mapAccum{L,R}` functions - the parameter function used `Either a b` to indicate whether to conclude early or keep processing the rest of the list. But so far my searches have been futile.

Perhaps someone else may recall seeing this function…

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [April 2, 2024, 11:17am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/29 "2024-04-02T11:17:34Z")

</div>

> [@sullyj3](#):
>
> it’s a bit galling to have to reconfigure type signatures and add `run*` for a change that would be a one word statement in a Blub language

I sympathise.

> [@sullyj3](#):
>
> It feels like a lot of ceremony

It is.

> [@sullyj3](#):
>
> It’s very surprising to me that others don’t relate to the experience of finding monad transformers a bit cumbersome in comparison to equivalent features in other languages.

I absolutely relate. That’s why I developed [Bluefin](https://hackage.haskell.org/package/bluefin).

> [@sullyj3](#):
>
> they soup up do notation with a desugaring of imperative looking loops to monad transformers, complete with `break`/`continue`.

Bluefin supports `break`/`continue` and it doesn’t even need a new desugaring.

> [@sullyj3](#):
>
> I’m not trying to advocate for imperative style per-se here, I’d be thrilled to see a solution in a more functional style with comparable ergonomics to `break`.

I _am_ trying to advocate for a more imperative style, and I believe Bluefin hits the spot perfectly. I’d love anyone interested to try it out and give me their feedback.

Do you have a particular example in mind? I’ll implement it in Bluefin. Here’s an example I just came up with. It reads `Int`s and adds all the positive ones, until it reads something that’s not an `Int`.

```haskell
addReadLinePositives :: IO Int
addReadLinePositives = runEff $ \io ->
  evalState 0 $ \state -> do
    -- Set break, a point we can jump to to exit the loop
    withJump $ \break -> forever $
      -- Set continue, a point we can jump to to continue the loop
      withJump $ \continue -> do
        -- Read the line
        line <- effIO io getLine
        i <- case readMaybe line of
          Nothing ->
            -- If it's not an Int, break
            jumpTo break
          Just i ->
            pure i

        -- If it's negative, ignore
        when (i < 0) $
          jumpTo continue

        -- Otherwise, accumulate it
        modify state (+ i)

    get state

```

```haskell
ghci> addReadLinePositives 
1
2
3
-100
STOP
6

```

---

<div class="post-metadata">

**Author:** ![sullyj3](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sullyj3/32/2639_2.png) [@sullyj3](https://discourse.haskell.org/u/sullyj3)\
**Post date:** [April 2, 2024, 11:32am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/30 "2024-04-02T11:32:35Z")

</div>

Looks cool! I love the idea of a “StateRef” so to speak, it makes so much sense in retrospect.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [April 2, 2024, 4:39pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/31 "2024-04-02T16:39:59Z")

</div>

> [@sullyj3](#):
>
> I love the idea of a “StateRef” so to speak, it makes so much sense in retrospect.

Yes, and just wait until you start using “ExceptionRefs”!

---

<div class="post-metadata">

**Author:** ![danidiaz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/danidiaz/32/92_2.png) [@danidiaz](https://discourse.haskell.org/u/danidiaz)\
**Post date:** [April 2, 2024, 9:50pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/32 "2024-04-02T21:50:28Z")

</div>

Is there some library that provides early return using the [delimited continuation primops](https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-Exts.html#v:control0-35-) recently added to GHC?

I suppose the outward interface would be similar to that of libraries that use exceptions for the same purpose.

---

<div class="post-metadata">

**Author:** ![bruce-wayne](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/bruce-wayne/32/4652_2.png) [@bruce-wayne](https://discourse.haskell.org/u/bruce-wayne)\
**Post date:** [September 24, 2024, 10:37am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/33 "2024-09-24T10:37:21Z")

</div>

@tomjaguarpaw I like your solution [here](http://discourse.haskell.org/t/break-with-traverse-traverse/9152/23), but my use case needs the last returned value in the current iteration. Does this early exit work with `foldM` also, used in a nested loop as shown below (I didn’t compile this code)

```haskell
runExceptT $ forM_ [maxFactor, maxFactor -1..minFactor] $ \left ->
  runExceptT $ foldM (go left) Nothing [maxFactor, maxFactor -1..minFactor]
where
  go l pal r = case palindrome (>=) l pal r of
    Left p -> ME.throwError p
    Right p -> return p

```

The intent is to break out of the two loops when a `Left` is returned by the function `palindrome`.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [September 24, 2024, 11:08am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/34 "2024-09-24T11:08:02Z")

</div>

Hi @bruce-wayne

> [@bruce-wayne](#):
>
> my use case needs the last returned value in the current iteration

Do you mean like this? If not, could you say more about what you mean?

```haskell
import Bluefin.EarlyReturn (returnEarly, withEarlyReturn)
import Bluefin.IO (effIO, runEff)
import Bluefin.Stream (yield, yieldToList)
import Data.Foldable (for_)

baz :: [Int] -> IO ([Int], Maybe Int)
baz count = runEff $ \io -> do
  (as, ma) <- yieldToList $ \y -> do
    withEarlyReturn $ \ret -> do
      for_ count $ \a -> do
        yield y a
        if even a
          then do
            returnEarly ret (Just a)
          else
            effIO io (print a)

      pure Nothing

  let message = case ma of
        Just a -> show a <> " is even!"
        Nothing -> "There was no even element"

  effIO io (putStrLn message)

  pure (as, ma)
-- ghci> baz [1, 3, 5, 7]
-- 1
-- 3
-- 5
-- 7
-- There was no even element
-- ([1,3,5,7],Nothing)
-- ghci> baz [1, 3, 4, 5, 7]
-- 1
-- 3
-- 4 is even!
-- ([1,3,4],Just 4)

```

> [@bruce-wayne](#):
>
> Does this early exit work with `foldM` also?

I take it this is a separate question? If so, yes, it works with `foldM`, but there’s no real need for `foldM` if you’re using Bluefin. It’s probably easier just to use `for_` and `evalState`:

```haskell
import Control.Monad (foldM, when)
import Bluefin.EarlyReturn (returnEarly, withEarlyReturn)
import Bluefin.IO (effIO, runEff)
import Bluefin.Jump (jumpTo, withJump)
import Bluefin.State (evalState, get, put)
import Bluefin.Stream (yield, yieldToList)
import Data.Foldable (for_)

runningSumUntilNegativeFoldM l = runEff $ \io -> do
  withJump $ \done -> do
    (\f -> foldM f 0 l) $ \soFar i -> do
      when (i < 0) $
        jumpTo done
      let next = soFar + i
      effIO io (print next)
      pure next

    pure ()
-- ghci> runningSumUntilNegativeFoldM [1, 2, 3, 4, -1, 5]
-- 1
-- 3
-- 6
-- 10

runningSumUntilNegativeFor l = runEff $ \io -> do
  withJump $ \done -> do
    evalState 0 $ \total -> do
      for_ l $ \i -> do
        when (i < 0) $
          jumpTo done
        soFar <- get total
        let next = soFar + i
        effIO io (print next)
        put total next
-- ghci> runningSumUntilNegativeFor [1, 2, 3, 4, -1, 5]
-- 1
-- 3
-- 6
-- 10

```

---

<div class="post-metadata">

**Author:** ![bruce-wayne](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/bruce-wayne/32/4652_2.png) [@bruce-wayne](https://discourse.haskell.org/u/bruce-wayne)\
**Post date:** [September 24, 2024, 11:23am UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/35 "2024-09-24T11:23:47Z")

</div>

@tomjaguarpaw I’m not using Bluefin, the set of packages that’re available are predefined, and Bluefin isn’t in there. Basically, I’ve two nested loops, and the inner loop calls a function that returns an `Either`. If it’s a `Left`, the code should break out of both loops and return the value wrapped in the `Either`. If it’s a `Right`, the wrapped value should be passed into the next function call. Please see a crude attempt below.

```haskell
run :: (Monad m) => ExceptT a m a -> m a
run = (pure . either id id =<<) . ME.runExceptT

largestPalindrome :: Integer -> Integer -> Palindrome
largestPalindrome minFactor maxFactor =
  run $ forM [maxFactor, maxFactor -1..minFactor] $ \left ->
    runExceptT $ foldM (go left) Nothing [maxFactor, maxFactor -1..minFactor]

```

If you’d prefer a separate question, I can certainly create one.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [September 24, 2024, 12:00pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/36 "2024-09-24T12:00:45Z")

</div>

Well, how about this? But it’s quite hard to know exactly what you want without more details.

```haskell
import Data.Foldable (for_)
import Control.Monad (foldM)
import Control.Monad.Identity (runIdentity)
import Control.Monad.Trans.Except (ExceptT, runExceptT, throwE)

runEarlyReturn :: (Monad m) => ExceptT a m a -> m a
runEarlyReturn m = (pure . either id id) =<< runExceptT m

data Palindrome

palindrome :: (b -> b -> Bool) -> b -> Maybe b -> b -> (Either Palindrome (Maybe b))
palindrome _ _ _ _ = undefined

largestPalindrome :: Integer -> Integer -> Maybe Palindrome
largestPalindrome minFactor maxFactor =
  runIdentity $ runEarlyReturn $ do
    for_ [maxFactor, maxFactor -1..minFactor] $ \left -> do
      foldM (go left) Nothing [maxFactor, maxFactor -1..minFactor]
    pure Nothing
  where
    go l pal r = case palindrome (>=) l pal r of
      Left p -> throwE (Just p)
      Right p -> return p

```

> [@bruce-wayne](#):
>
> If you’d prefer a separate question, I can certainly create one.

No, that’s OK. I was just trying to understand if you were asking two separate things, or just mentioning two aspects of the same thing.

---

<div class="post-metadata">

**Author:** ![bruce-wayne](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/bruce-wayne/32/4652_2.png) [@bruce-wayne](https://discourse.haskell.org/u/bruce-wayne)\
**Post date:** [September 24, 2024, 1:49pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/37 "2024-09-24T13:49:37Z")

</div>

Unfortunately, this didn’t produce the intended result, certainly not due to your code, but my inept attempt at describing the problem. I’m actually trying to come up with Haskell code for the following Python program, which is also my writing.

> <https://github.com/asarkar/exercism-python/blob/main/palindrome-products/palindrome_products.py>

I’ve to do something else now, but I’ll come back to it this weekend.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [September 24, 2024, 3:02pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/38 "2024-09-24T15:02:55Z")

</div>

I see. You can indeed encode this logic in either Bluefin or transformers, but the transformers encoding will probably be too painful to be worth it. Not only do you have `break` you also have `continue`, and those would have to be encoded as two levels of early return. Bluefin will handle that easily. transformers, well, it’s a matter of taste but I wouldn’t bother, personally.

---

<div class="post-metadata">

**Author:** ![brandonchinn178](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/brandonchinn178/32/5103_2.png) [@brandonchinn178](https://discourse.haskell.org/u/brandonchinn178)\
**Post date:** [September 24, 2024, 3:45pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/39 "2024-09-24T15:45:46Z")

</div>

FWIW I would write this as just

```haskell
largestPalindrome start end =
  listToMaybe . sortOn Down . filter isPalindrome $
    [ i * j
    | i <- [start .. end]
    , j <- [i + 1 .. end]
    ]

```

No need for traverses or effects

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [September 24, 2024, 4:51pm UTC](https://discourse.haskell.org/t/break-with-traverse-traverse/9152/40 "2024-09-24T16:51:58Z")

</div>

That’s nice and simple, but I believe @bruce-wayne wants to avoid picking up the extra `log(n)` for the sort, and also wants to increase efficiency by bailing out when nothing else in the last can possibly work.

[Previous page](https://discourse.haskell.org/t/break-with-traverse-traverse/9152.md?page=1)

[Next page](https://discourse.haskell.org/t/break-with-traverse-traverse/9152.md?page=3)