6

考虑以下命令式代码，它在 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

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

那么你有什么建议，处理这种情况的方法是什么？

4

9 回答 9

7

与丹尼尔和 sepp2k 的类似答案：

惰性函数式编程使您可以以比您在问题中的命令式控制流中看到的更加模块化的方式编写程序。例如，形成因子 999...100 的列表，然后是所有产品，然后过滤以仅保留回文，然后计算最大值。多亏了惰性，这些中间列表只会在需要时才出现，并且会逐渐被回收。

有关更多解释和示例，请参阅 John Hughes 的经典论文Why Functional Programming Matters。

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
于 2010-12-22T19:29:31.437 回答
5

如果我们取消所有优化，只将 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 ..])

这里的外循环与您的解决方案基本相同，但我们使用列表函数替换了内循环。

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

然后我们find用来查看该列表中的任何项目是否是回文。如果是，列表中的第一个回文数就是我们的新最大值。如果不是，我们保留旧的最大值。（find返回 aMaybe并fromMaybe采用默认值，如果 a 中没有值，则Maybe返回 a 中的值或默认值）MaybeMaybe

于 2010-12-22T19:28:00.693 回答
2

在我看来，一个范围对应一个列表。例如：

f = [999,998..100]

现在f定义为从 999 到 100 的数字序列。

for循环对应于不同的功能概念，具体取决于您在每次迭代中所做的事情。有时 amap是适当的类比，有时是 a fold，有时是别的东西。很多时候，它是事物的组合。在这种情况下，您有效地组合了两个列表。在 Haskell 中做到这一点的一种方法是列表理解：

g = [(x * y) | x <- f , y <- f]

这里g表示先前定义的序列的每个元素与其自身组合的乘积列表。换句话说，几乎是你在你的for循环中发生的事情。

从这里开始，您可能希望过滤结果序列以仅包含回文值，然后从该集合中计算最大值。

于 2010-12-22T19:19:56.730 回答
2

这里没有万能的答案。但是让我们看一下这个具体的例子：

首先，考虑外部循环：我们总是做完整的范围，我们只关心最终的最大值，所以这很容易：

outerLoop = foldl innerLoop 0 [999,998..100]

在内部循环中，我们有一些 i 的值和一个当前最大值。现在我们只关心 i*j 大于当前最大值的范围：

innerLoop curmax i = foldr checkMax curmax [999*i, 998*i .. curmax]

在核心逻辑中，我们得到一个 i*j 的值，我们知道它总是大于或等于当前最大值，所以只需检查下一个值是否是回文：如果是，我们就是完成，因为序列减少了。如果不是，请推迟决定：

checkMax ij defer = if pal ij then ij else defer
于 2010-12-22T19:47:20.523 回答
2

因此，从功能上思考，您应该寻找将问题分解为函数而不是循环和步骤的方法。

因此，如果我们有一个maxWhere f xs返回最大x为f x真的函数，我们可以这样写：

maxpal = maxWhere pal [x * y | x <- [999,998..100], y <- [999,998..100]]

maxWhere 的一个简单实现是

maxWhere f xs = maximum $ filter f xs

但是如果比比较更昂贵，这很糟糕，f因为我们将对 f 进行比原始调用更多的调用。我们可以使用 fold 将过滤器和最大值组合成一次传递，并获得与命令式代码相同的行为。

maxWhere f xs = foldl' r 0 xs
    where r a x
       | x > a     = if f x then x else a
       | otherwise = a

在这里使用零作为一个神奇的小数是可怕的，但在这种情况下是有效的。

（我真的很想拼写那个候选号码列表(*) <$> [999,998..100] <*> [999,998..100]，但这可能会在这里引入不必要的复杂性。）

于 2010-12-22T22:58:32.823 回答
1

嘎。被 sepp2k 打败，但我会回答你的一般问题：

临时变量也可以使用 state monad 或 ST monad 来表示，如果你有很多的话。FP 通常以简洁明了的方式取胜，但在某些情况下并非如此，例如当有多个局部变量需要处理时。

惰性可以模拟很多中断，但是在处理 IO 时，通常必须使用显式递归。然而，'List' 包（来自 Hackage）在允许您以函数式风格编写 IO 循环方面非常聪明。

于 2010-12-22T19:40:43.960 回答
1

这种循环很容易用于列表理解，如下所示：

maximum [x*y | x <- [999..100], y <- [999..100],isPalindrome (x*y)]

我们可以这样写回文：

isPalindrome x = xs == reverse xs
  where xs = show x

这真的足够快，虽然有点不聪明，所以首先我们会注意到我们检查了两次数字。假设 a*b 是最大的回文数，那么我们将检查 wherex == a, y==b和的情况x==b, y==a。因此，首先我们通过将搜索的数字限制为仅 x >= y 的情况来阻止这种情况，如下所示：

maximum [x*y | x <- [999..100], y <- [x..100],isPalindrome (x*y)]

这将要测试的数字减少了一半。

在您的 python 解决方案中，您还将 y 限制为我们迄今为止发现的最大数字除以当前 x ( x*y => curmax)，而且您永远不会搜索超过找到的第一个 y （如果 curmax 更新，则打破内部循环）。如果我们检查的第一个元素（x 平方）小于我们当前的答案，我们可以通过不继续进一步减少搜索，因为所有后续检查都更小，但这超出了列表理解中看起来不错的范围，因此我们将搜索移至它自己的功能：

import Data.List(find)
import Data.Maybe(isNothing,fromJust)

search x curr 
   | x * x < curr                   = curr
   | isNothing maypal || pal < curr = search (x - 1) curr 
   | otherwise                      = search (x - 1) pal 
   where maypal = find isPalindrome [x * x, (x - 1) * x .. curr]
         pal    = fromJust maypal

值得注意的是，我们的限制，(x*x) < curr实际上只是意味着从现在开始，[x*x,(x-1)*x..curr]将是空的。正如您所看到的，所有由 python 代码中的中断强制执行的边界都适合 x 的一次迭代（使用递归）和 x*y 值列表的查找。它可能看起来不太好，但在我看来，更明确地说明了我们对 x 和 y 所做的限制。

运行它我们得到：

*Main> search 999 0
906609

事实证明，停止时间x * x < curr是一个非常好的主意，因为 906609 的平方根是 952...

于 2010-12-23T00:29:32.003 回答
0

正如stephen tetley在他的评论中所指出的，在 FP 中，您可以使用连续传递样式来处理复杂的控制流（Contmonad 加上它callCC在某种程度上类似于break......甚至goto- 滥用 CPS 会导致相当难以理解的代码 - 请参阅我的下面的例子）：

import Control.Monad.Cont

pal n = sn == reverse sn
    where sn = show n

range = [99999,99998..10000]

mfoldM a r f = foldM f a r  

curmaxm = (`runCont` id) $ mfoldM 0 range $ \m i ->
            callCC $ \break ->
                mfoldM m range $ \m j -> do
                  let ij = i*j
                  if ij < m
                     then break m
                     else return $
                          if pal ij then ij else m

两个 mfoldM（只是一个标准的 foldM，其参数重新排列）对应于原始样本中的两个循环，并且break函数参数用于“内部循环”以在违反条件时退出它（i*j > current max）（返回当前最大作为“内循环”的结果）。在这里我们只需要从一个“循环级别”中逃脱，所以这里的 callCC 绝对是矫枉过正。

同样的逻辑也可以用find（+ Haskell的懒惰）实现：

import Data.List
import Data.Maybe
import Control.Monad

curmax = fromJust $ foldM it 0 range
    where 
      it m i = (find pal . takeWhile (>m) . map (*i) $ range) `mplus` return m

find pal这里返回第一个回文数（也将满足 takeWhile 中的 (>m) 条件）或 Nothing（MonadPlus 的零）和之后mplus（或 Alternatice.<|>）it有效地返回一个新的最大回文数或前一个最大值（返回米）。由于一旦找到第一个令人满意的元素就停止搜索，因此该代码的行为与其命令式模拟find完全相同。curmax两个版本都在 0.5 秒内运行 [99999..10000] 范围。

更新： 只是为了好玩：相同的方法，但使用StateT Integer (Cont Integer) ()- Cont 从“循环”中逃脱，并使用 State 来传递最大回文（加上使用forM_and的能力when）。相同的效率：

import Control.Monad.Cont
import Control.Monad.State.Strict

solcs = runCont (execStateT comp 0) id
    where   
      comp = forM_ range $ \i -> callCC $ \break ->
                forM_ range $ \j -> do
                  let ij = i*j
                  m <- get
                  when (ij < m) (break ())
                  when (pal ij) (put ij)
于 2010-12-23T07:16:59.540 回答
0

我认为你可以使用两个相互递归的函数来做你想做的事。

这是一个更简单的示例（取自ATS 上的教程）：

implement main (argc, argv) = let
  fun loop1 (i: int): void =
    if i <= 9 then loop2 (i, i) else ()

  and loop2  (i: int, j: int): void =
    if j <= 9 then begin
      if i < j then begin
        print ", ";
        print "("; print i; print ", "; print j; print ")";
        loop2 (i, j+1)
      end
    end else begin
      print_newline ();
      loop1 (i+1)
    end
  in
    loop1 0
  end

上面写的代码很像你用 C 写的（取自同一页）：

int main (int argc, char *argv[]) { int i, j ;

for (i = 0; i <= 9; i += 1) {
  for (j = i; j <= 9; j += 1) {
    if (i < j) printf (", ") ; printf ("(%i, %i)", i, j) ;
  } /* for */
  printf ("\n") ;
} /* for */

return 0 ;

}

如您所见，嵌套循环成为相互递归的函数；可变变量 i 和 j 成为归纳变量。loop1 对应于外循环，而 loop2 对应于内循环。

于 2011-01-26T14:46:15.437 回答