使用break-s/continue-s将命令控制流转换为haskell

Question

考虑以下命令性代码,它找到3位数字产品中最大的回文(是的,它是"18世纪优秀数学家的项目"网站的首批任务之一):

curmax = 0
for i in range(999,100):
for j in range(999,100):
    if ((i*j) < curmax): break
    if (pal(i*j)):
        curmax = i*j
        break
print curmax

当我正在学习Haskell时,我的问题是,你如何将这个(以及基本上任何包含比简单迭代更复杂的命令式构造,例如中断,继续,临时变量和所有这些)转换为Haskell？

我的版本是

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) (innerloop 999)
    where 
        innerloop j
            | (j < 100) || (p < curmax) = curmax
            | pal p = p
            | otherwise = innerloop (j-1)
            where p = i*j
main = print $ maxpal 999 0

但这看起来我们仍然处于势在必行的丑陋城市.

那么你能提出什么建议,处理FP风格的案件有哪些方法？

Answer 1

Daniel's和sepp2k的类似答案:

懒惰的函数式编程使您能够以比您在问题中的命令式控制流程中看到的更加模块化的方式编写程序.例如,形成因子列表999 ... 100,然后是所有产品,然后过滤以仅保留回文,然后计算最大值.由于懒惰,这些中间列表将仅在需要时生成并将逐步回收.

有关更多解释和示例,请参阅John Hughes的经典论文"功能编程为何重要".

maxpal :: Int
maxpal = maximum [i*j | i <- factors, j <- factors, pal (i*j) ]

factors :: [Int]
factors = [999,998..100]

pal :: Show a => a -> Bool
pal = palL . show

palL :: (Eq a) => [a] -> Bool
palL xs = xs == reverse xs

Answer 2

如果我们取消所有的优化并将所有数字组合乘以100和999之间,过滤掉非回文并取其最大值,我们可以非常简洁地编写函数:

maximum $ filter pal [x*y | x <- [100..999], y <- [100..999]]

当然,这基本上是效率最低的方法,但由于数字相对较小,我的机器上仍然会在不到半秒的时间内完成.

但是,如果我们想要在算法上更符合python解决方案的内容,我们可以这样做:

import Data.Maybe
import Data.List

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) newmax
    where newmax = fromMaybe curmax (find pal bigger)
          bigger = takeWhile (> curmax) (map (*i) [999, 998 ..])

这里的外部循环与解决方案基本相同,但我们使用list函数替换了内部循环.

我们正在使用为每次倒计时map (*i) [999, 998, ...]创建产品.使用我们说一旦值不大于该列表就应该停止.i*jj999takeWhilecurmax

然后我们find用来查看该列表中的任何项目是否是回文.如果是,列表中的第一个回文是我们新的最大值.如果不是我们保持旧的最大值.(如果没有值,则find返回a Maybe并fromMaybe取一个默认值和a Maybe并返回Maybe默认值中的值Maybe)