Break with traverse / traverse_?

Learn
#41

I feel like both of those points could be addressed by doing something more complicated than that list comprehension. However, I haven’t tried my hand at it yet so maybe I’m wrong.

Edit: wait, the sort doesn’t add a log(n) factor because we only look at the first result. Laziness FTW.

3 Likes
#42

Ah yes, great! I think the early bail out issue remains though.

#43

ah sure. something like

maximumSafe . concat . takeWhile (not . null) $
  [ filter isPalindrome [ i * j | j <- [i + 1 .. end]
  | i <- [start .. end]
  ]
#44

@brandonchinn178 Correct me if I’m reading this wrong, but I’m afraid this algo is incorrect.

  1. Given the range [1,9], all of the numbers contained in it are palindromes but your code would miss the factor (3,3).
  2. The Python code doesn’t quit whenever the inner loop breaks. It quits if the last iteration of the inner loop didn’t produce any palindromes that’s better than the one found so far. I don’t think this behavior can be encoded by takeWhile, because it’ll stop as soon as there’s a single mismatch.

@tomjaguarpaw I’ve yet to try it, but I think the break and the continue can be expressed in terms of a scanl nested in a foldl. The inner one would stop when it sees a palindrome that’s no better than the one seen so far, indicated by returning a Nothing. The outer one would stop when the inner one has produced all Nothing.

#45

Ah yes, my ranges aren’t completely correct. And yes, my current algo only stops if the inner loop produces zero palindrones, not if all palindrones are worse than the current one.

I think your last point makes sense. I would highly recommend trying normal list operations instead of trying to replicate imperative continue/break instructions with monads/effects.

#46

It’s actually not their solution. it’s just something they could do in theory. in reality it works different.

#47

Just to close the loop, I ended up with the following:

{-# LANGUAGE TupleSections #-}

module Palindromes
  ( largestPalindrome,
    smallestPalindrome,
  )
where

import qualified Control.Monad as M
import qualified Data.Either as E
import qualified Data.Maybe as Mb

type Palindrome = Maybe (Integer, [(Integer, Integer)])

largestPalindrome :: Integer -> Integer -> Palindrome
largestPalindrome minFactor maxFactor = outer (>=) Nothing rng
  where
    rng = [maxFactor, maxFactor - 1 .. minFactor]

smallestPalindrome :: Integer -> Integer -> Palindrome
smallestPalindrome minFactor maxFactor = outer (<=) Nothing rng
  where
    rng = [minFactor .. maxFactor]

-- outer loop
outer ::
  (Integer -> Integer -> Bool) ->
  Palindrome ->
  [Integer] ->
  Palindrome
outer _ pal [] = pal
outer op pal rng@(l : xs)
  | null inner = pal
  | otherwise = outer op (E.fromRight Nothing (last inner)) xs
  where
    -- inner loop
    inner = takeWhile E.isRight $ scanl go (Right pal) rng
    go = flip (palindrome op l) . either id id

palindrome ::
  (Integer -> Integer -> Bool) ->
  Integer ->
  Integer ->
  Palindrome ->
  Either Palindrome Palindrome
palindrome op left right pal
  | Mb.isJust $ M.mfilter (not . op pdt . fst) pal = Left Nothing
  | isPal (show pdt) = Right justPal
  | otherwise = Right pal
  where
    pdt = left * right
    isPal = M.ap (==) reverse
    {-
    If the newly found palindrome is not the same as the one found
    before, we need to reset the factors. One palindrome may have
    multiple factors, like 9 has [1, 9] and [3, 3].
    -}
    newFact (p, fact) = if p == pdt then fact else []
    newPal = fmap ((pdt,) . ((left, right) :) . newFact) pal
    justPal = M.msum [newPal, Just (pdt, [(left, right)])]
2 Likes
#48

I’m surprised the continuation monad wasn’t mentioned here. callCC allows this kind of “early exit”, but making the examples on this page work with recursion on a list seems like a challenge.

1 Like