常见LISP和堆栈中的数字类型边界在GHCI中流过

Question

这里的第一个问题,以及普通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的公式来计算三角形的面积,给定三边的大小,并确定它是否是比较天花板和地板的整数.我们被告知等边三角形的面积永远不是整数.因此,为了测试函数是否正常工作,我使用参数运行它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浮点数可替代性规则.长话短说,结果转换为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转换函数.可选的第二个参数是float原型,即.目标类型的值.上面是0d0双浮.你也可以使用0l0长双打或0s0简称双打.如果要与输入float具有相同的精度,则此参数很有用,但也可以与文字一起使用,如示例中所示.short,single,double或long float类型的确切含义是实现定义的,但它们应遵守一些规则.当前的实现通常提供所需最小值的更高精度.

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

Answer 2

我会回答你的第二个问题,我不确定第一个问题.在Haskell中,因为它是一种惰性语言,当你使用带有累加器参数的尾递归时,可能会发生"累积的thunk".thunk是一个暂停但尚未评估的表达式.举一个更简单的例子,将从0到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             

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

解决方案是尽快进行tri评估accum.这通常使用a BangPattern来完成(但seq如果您不喜欢扩展,则可以完成).

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

该!前accum指(即使模式不技术上需要知道它的价值)"的模式匹配的时刻评估此参数".然后我们得到这个评估痕迹:

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

我希望这有帮助.