do 块中看似无用的守卫可避免最大堆栈错误

Question

做 "PureScript by Example" 的练习我尝试对代码做一些修改。我有点不明白:

module Main where

import Prelude
import Data.Array ((..),(:))
import Control.MonadZero (guard)

factors n = do
  x <- 1 .. n
  guard $ (n `mod` x) == 0
  pure x

-- WORKS OK
factorizations n = [n] : do
  x <- factors n
  guard $ x > 1 && x < n
  xs <- factorizations $ n / x
  pure $ x : xs

factors' n = do
  x <- 2 .. (n - 1)
  guard $ (n `mod` x) == 0
  pure x

-- ALSO WORKS
factorizations' n = [n] : do
  x <- factors' n
  guard $ x > 1 && x < n -- LOOKS USELESS: x is never 1 or n, so guard never fails
  xs <- factorizations' $ n / x
  pure $ x : xs

-- RUNTIME ERROR: RangeError: Maximum call stack size exceeded
-- at ...\node_modules\Data.Array\foreign.js:8:19
factorizations'' n = [n] : do
  x <- factors' n
  -- no guard
  xs <- factorizations'' $ n / x
  pure $ x : xs

为什么 "useless" guard 从运行时错误中保存？ factorizations''真的没用吗？ PureScript 的设计难道不是几乎不可能出现运行时错误吗？

编辑 Ramda.js 版本做同样的事情

let factors = n => R.filter(i => n%i==0, R.range(1,n+1))

let factorizations = n => [[n], ...R.chain(
  x => R.map(
  xs => [x, ...xs], factorizations(n/x)
))(R.filter(x => x>1&&x<n, factors(n)))]

Answer 1

简短的回答是：你的守卫不是没用，它尽职尽责。

首先，请注意factorizations'和factorizations''实际上并没有递归地调用自己。相反，他们调用 factorizations （没有素数）。我现在假设这是问题中的一些奇怪的拼写错误，并且您的实际代码是正确递归的。

假设是这种情况，您看到的问题的发生是因为 a..b 没有按照您的想法去做。

在你的 REPL 中试试这个：

> 2..1
[2,1]

嗯？

这是 by design：运算符 .. 永远不会 return 一个空数组，即使给定一个 "flipped" 范围。对于 "flipped" 范围，它将 return 该范围内的所有数字，但向后排序。

事情是这样的：

1. factorizations'' n=4
  1.a. factors' n=4  =>  [2]
  1.b. n/x = 2
2. factorizations'' n=2
  2.a. factors' n=2  =>  [2]
  2.b. n/x = 1
3. factorizations'' 1
  3.a. factors' n=1  =>  [1]
  3.a. n/x = 1
4. factorizations'' 1
  -- and so on

请注意，这仅适用于 n。奇数在它们的因子中不会有 2，这意味着 factors' 永远不会用参数 2.

调用

do 块中看似无用的守卫可避免最大堆栈错误

Apears-to-be-useless guard in do block saves from maximum stack error

runtime-error

callstack

purescript