haskell - 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 运行它。 .这是我得到的返回:

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

完美的!有用。为了进一步测试它，我使用参数 3333 运行它。 .这是我得到的返回:

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

让我们定义一个中间 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 返回:

4810290.040910754

浮点

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

370222244442963/16 

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

关于浮点数和数学函数的相关部分是 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 转换功能。可选的第二个参数是一个浮点原型(prototype)，即。目标类型的值。上面是 0d0 , 双浮点数。您也可以使用 0l0对于长 double 或 0s0简而言之。如果您希望与输入浮点数具有相同的精度，则此参数很有用，但也可以与文字一起使用，如示例中所示。短、​​单、双或长浮点类型的确切含义是实现定义的，但它们应尊重 some rules .当前的实现通常提供比最低要求更高的精度。

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

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

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