'signum' 在 Haskell 中用于有序数字类型的用例

Use cases of 'signum' for ordered numeric types in Haskell

signum 函数是通常的 mathematical definition of sign 的实现,它有条件地 return 是 {-1,0,1} 中的一个值。这是一个理论定义,因此,它没有考虑操作的计算成本或值的数据类型,因此乘以 (-1) 是改变符号的零成本理论方法。因此,它不是编程中最有用的符号处理方式。

案例 signum a == 0 并不是很有用,因为您总是可以直接测试 a == 0,而无需额外的计算成本 signum a。至于其他两个值,我认为它们仅以 3 种一般方式使用:

在所有情况下,符号的 Bool 值会更好。因此,我们只需要将 Num 分解为绝对值和布尔符号的函数,以及一个根据布尔条件(表示符号)更改值符号的反函数。该函数相当于1-1乘以一个数,所以我们将其定义为类似于(*)的运算符。 :

sgn  a      = a >= 0
(*.) a True = a
(*.) a _    = -a
abs  a      = a *. sgn a
signum1 a   = 1 *. sgn a

我添加了 signum 的二分变体,它只能 return ´{-1,1}´。请注意,在它前面加上 signum 0 = 0 我们会得到通常的 signum 函数,但我认为第三种情况通常用处不大。

我们可以用类似的方式编写一个加法运算符,因为根据某些东西的符号添加 1-1 是一种非常常见的情况(你可以看到这些运算符只处理 True 作为 1False 作为 -1):

(+.) a b    = a + 1 *. b
(-.) a b    = a - 1 *. b

我们甚至可以将声明包含在名为 Signed 的 class 中,以便于使用,包括适当的签名和固定性。

这样,上面的一般示例不仅会简化代码,还会简化执行时间和 space,因为我们避免了乘法(改为使用 (*.)),我们避免了额外的比较一旦我们有了 Bool,我们就可以从一种类型的数据中获取符号并将其用于另一种类型而无需类型转换,我们使用短类型 Bool 而不是潜在的长类型 class Num。但是我们获得了更大的灵活性,同时允许对代码和数据类型进行一些优化。

那么,我的问题是,是否存在与此处公开的三个一般用例不同的情况,即这种方法不易涵盖的情况,当前 signum 功能有优势的情况布尔符号方法。更准确地说,我能否在不损失效率或代码清晰度的情况下完全避免使用当前的 signum 函数?


编辑:我根据 Reid Barton 的评论将第一段修改为更 "neutral" 时尚。


进度更新:在当前答案和评论的大力帮助下,此方法的代码已大大改进,变得简单明了。

您假设 "positive" 和 "negative" 是仅有的两个可能的符号。但是例如Complex Double, signum 运算 returns 一个复数 "direction" 相同但量级为 1:

Data.Complex> signum (3 :+ 4)
0.6 :+ 0.8

我使用了这样的函数,通过一系列移动到(正交和对角)相邻单元格,将光标导航到方形网格中的目标偏移量。

move :: (Int, Int) -> [(Int, Int)]
move (0, 0) = []
move (x, y) = (dx, dy) : move (x - dx, y - dy)
  where dx = signum x
        dy = signum y

解决时间复杂度问题:

分支不是免费的,如果您必须(在概念上)将值乘以几个不同位置的相同值的符号的结果,那么 let s = signum x in ... 或在 where 子句中绑定。您不再需要每次都经过分支机构。还要记住 in some cases, code can slow down due to branching behavior that goes against what the branch predictor expects.

例如,假设您有这样的代码:

f x y z = (s * y) / (1 + (s * z))
  where
    s = signum x

效率分析通常并不像您预期​​的那样明确,并且可能 高度 取决于特定程序的非常具体的方面,如问题 I 中所示链接在上面,因此经常引用 "profile before optimizing" 的建议。在我链接到的问题中,执行更多指令的代码版本实际上比执行更少指令的版本运行更快(我可以验证这些结果在我的机器上,即使我在分析中包含额外的排序指令)!