do 块中看似无用的守卫可避免最大堆栈错误
Apears-to-be-useless guard in do block saves from maximum stack error
做 "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)))]
简短的回答是:你的守卫不是没用,它尽职尽责。
首先,请注意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
.
调用
做 "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)))]
简短的回答是:你的守卫不是没用,它尽职尽责。
首先,请注意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
.