Common LISP 中的数字类型边界和 GHCI 中的 Stack 溢出

Question

这里的第一个问题，Common LISP 和 Haskell 的新手，请多多关照。我在 Common LISP 中有一个函数 - 下面的代码 - 用于判断三角形的面积是否为整数（整数？）。

(defun area-int-p (a b c)
  (let* ((s (/ (+ a b c) 2))
         (area (sqrt (* s (- s a) (- s b) (- s c)))))
    (if (equal (ceiling area) (floor area))
        t
        nil)))

这里应该是用Heron's formula计算三角形的面积，给定三边的大小，比较天花板和地板，判断是否是整数。我们被告知等边三角形的面积永远不是整数。因此，为了测试函数是否正常工作，我运行它带有参数 333。这是我在 return:

中得到的

CL-USER> (area-int-p 333 333 333)
NIL

完美！有用。为了进一步测试它，我运行它带有参数 3333。这是我在 return:

中得到的

CL-USER> (area-int-p 3333 3333 3333)
T

出了点问题，这不应该发生！所以，我尝试了以下，希望等效的 Haskell 函数，看看会发生什么：

areaIntP :: (Integral a) => a -> a -> a -> Bool
areaIntP a b c =
  let aa = fromIntegral a
      bb = fromIntegral b
      cc = fromIntegral c
      perimeter = aa + bb + cc
      s = perimeter/2
      area = sqrt(s * (s - aa) * (s - bb) * (s - cc))
  in  if ceiling area == floor area
      then True
      else False

这是我得到的：

*Main> areaIntP 3333 3333 3333
False
*Main> areaIntP 333 333 333
False

看起来很完美。受此鼓舞，我在Haskell中使用下面的函数求出第三边与另一边相差一个单位的等腰三角形的周长，一个整数面积，周长在1,000,000,000以下。

toplamArtilar :: Integral a => a -> a -> a -> a
toplamArtilar altSinir ustSinir toplam =
  if ustSinir == altSinir
  then toplam
  else if areaIntP ustSinir ustSinir (ustSinir + 1) == True
       then toplamArtilar altSinir (ustSinir - 1) (toplam + (3 * ustSinir + 1))
       else toplamArtilar altSinir (ustSinir - 1) toplam

toplamEksiler :: Integral a => a -> a -> a -> a
toplamEksiler altSinir ustSinir toplam =
  if ustSinir == altSinir
  then toplam
  else if areaIntP ustSinir ustSinir (ustSinir - 1) == True
       then toplamEksiler altSinir (ustSinir - 1) (toplam + (3 * ustSinir - 1))
       else toplamEksiler altSinir (ustSinir - 1) toplam

sonuc altSinir ustSinir =
  toplamEksiler altSinir ustSinir (toplamArtilar altSinir ustSinir 0)

（ustSinir表示上限，altSinir顺便下限。）运行 sonuc 参数 2 和 333333333 但是，我的堆栈溢出了。在 Common LISP 堆栈中运行等效函数是可以的，但是 area-int-p 函数不可靠，可能是因为解释器推导的数字类型的边界。毕竟，我的问题有两个：

1) 如何解决 Common LISP 函数中的问题 area-int-p?

2) 如何使用上述 Haskell 函数防止堆栈溢出，无论是在 Emacs 中还是在终端中使用 GHCi 运行？

那些弄清楚我在这里想要实现的目标的人请注意：请不要告诉我使用 Java BigDecimal 和 BigInteger。

在得到非常好的答复后进行编辑：我一并提出了两个问题，并从非常乐于助人的人那里得到了非常令人满意的、新手友好的答案和关于风格的注释。谢谢。

Answer 1

我会回答你的第二个问题，我不确定第一个问题。在 Haskell 中，因为它是一种惰性语言，所以当您使用带累加器参数的尾递归时，可能会发生 "accumulation of thunks"。 thunk 是一个暂停且尚未计算的表达式。举一个更简单的例子，将 0 到 n:

的所有数字相加

tri :: Int -> Int -> Int
tri 0 accum = accum
tri n accum = tri (n-1) (accum + n)

如果我们跟踪评估，我们可以看到发生了什么：

tri 3 0
  = tri (3-1) (0+3)
  = tri 2 (0+3)
  = tri (2-1) ((0+3)+2)
  = tri 1 ((0+3)+2)
  = tri (1-1) (((0+3)+2)+1)
  = tri 0 (((0+3)+2)+1)
  = ((0+3)+2)+1     -- here is where ghc uses the C stack
  = (0+3)+2        (+1) on stack
  = 0+3            (+2) (+1) on stack
  = 0              (+3) (+2) (+1) on stack
  = 3              (+2) (+1) on stack
  = 5              (+1) on stack
  = 6

这当然是一种简化，但它是一种直觉，可以帮助您理解堆栈溢出和 space 由 thunk 累积引起的泄漏。 GHC 仅在需要时评估 thunk。我们通过 tri 每次都询问 n 的值是否为 0，因此该参数中没有 thunk 累积，但是直到最后没有人需要知道 accum 的值，这从示例中可以看出，这可能是一个非常大的 thunk。在评估那个巨大的 thunk 时，堆栈可能会溢出。

解决方案是让 tri 更快地评估 accum。这通常使用 BangPattern 完成（但如果您不喜欢扩展名，也可以使用 seq 完成）。

{-# LANGUAGE BangPatterns #-}
tri :: Int -> Int -> Int
tri 0 !accum = accum
tri n !accum = tri (n-1) (accum + n)

accum 之前的 ! 表示 "evaluate this parameter at the moment of pattern matching"（即使模式在技术上不需要知道它的值）。然后我们得到这个评估轨迹：

tri 3 0
  = tri (3-1) (0+3)
  = tri 2 3          -- we evaluate 0+3 because of the bang pattern
  = tri (2-1) (3+2)
  = tri 1 5
  = tri (1-1) (5+1)
  = tri 0 6
  = 6

希望对您有所帮助。

Answer 2

让我们定义一个中间 Common Lisp 函数：

(defun area (a b c)
  (let ((s (/ (+ a b c) 2)))
    (sqrt (* s (- s a) (- s b) (- s c)))))

您的测试给出：

CL-USER> (area 333 333 333)
48016.344

CL-USER> (area 3333 3333 3333)
4810290.0

第二种情况应该清楚，天花板和地板是相等的。在 Haskell 中不是这种情况，第二次测试是 3333，returns:

4810290.040910754

浮点数

在 Common Lisp 中，我们取平方根的值是：

370222244442963/16

这是因为计算是用有理数进行的。到目前为止，精度是最大的。但是，SQRT 可以自由 return 一个有理数（如果可能）或一个近似结果。作为一种特殊情况，结果在某些实现中可以是整数，正如 Rainer Joswig 在评论中指出的那样。这是有道理的，因为 integer 和 ratio 都是 rational 类型的不相交子类型。但是正如您的问题所示，一些平方根是无理数（例如√2），在这种情况下，CL 可以 return 一个近似值的浮点数（或复数浮点数）。

有关浮点数和数学函数的相关部分是 12.1.3.3 Rule of Float Substitutability。长话短说，当您计算平方根时，结果会转换为 single-float，这恰好会降低一些精度。为了有双，你必须更明确：

(defun area (a b c)
   (let ((s (/ (+ a b c) 2)))
     (sqrt (float (* s (- s a) (- s b) (- s c)) 0d0))))

我也可以使用 (coerce ... 'double-float)，但这里我选择调用FLOAT conversion function. The optional second argument is a float prototype, ie. a value of the target type. Above, it is 0d0, a double float. You could also use 0l0 for long doubles or 0s0 for short. This parameter is useful if you want to have the same precision as an input float, but can be used with literals too, like in the example. The exact meaning of short, single, double or long float types is implementation-defined, but they shall respect some rules。当前的实施通常提供比最低要求更高的精度。

CL-USER> (area 3333 3333 3333)
4810290.040910754d0

现在，如果我想测试结果是否为整数，我会截断浮点数并查看第二个 returned 值（余数）是否为零。

CL-USER> (zerop (nth-value 1 (truncate 4810290.040910754d0)))
NIL

任意精度

请注意，无论使用何种实现语言（Haskell、CL 或其他语言），考虑到浮点数的表示方式，该方法都会为某些输入提供不正确的结果。事实上，对于某些具有更精确浮点数的输入，可能会出现您在 CL 中遇到的相同问题，其中结果将非常接近整数。您可能需要另一种数学方法或类似 MPFR 的方法来进行任意精度浮点计算。 SBCL 附带 sb-mpfr:

CL-USER> (require :sb-mpfr)
("SB-MPFR" "SB-GMP")

CL-USER> (in-package :sb-mpfr)
#<PACKAGE "SB-MPFR">

然后：

SB-MPFR> (with-precision 256
           (sqrt (coerce 370222244442963/16 'mpfr-float)))
.4810290040910754427104204965311207243133723228299086361205561385039201180068712e+7
-1

Answer 3

关于风格：

(if (predicate? ...) t nil)

只是

(predicate? ...)

您正在检查您的 IF，如果 T 是 T，然后 return T。但是 T 已经是 T，所以你可以 return 它。

Common LISP 中的数字类型边界和 GHCI 中的 Stack 溢出

Number type boundaries in Common LISP and Stack flowing over in GHCI

haskell

common-lisp

arbitrary-precision

浮点数

任意精度