Haskell 的 if 语句用于错误检查

Question

我为 Haar 小波变换编写了一个函数，假设输入是一个 2 的幂的列表。在执行转换之前，我试图通过确保列表的长度是 2 的幂来进行错误检查。我正在比较列表长度的以 2 为底的对数，看看它是否均匀(小数点右侧没有任何内容)。我认为 Haskell 中的 if 语句发生了一些我在其他语言中不习惯的事情。如果我不进行错误检查并仅使用正确的参数调用 haar ，它就会完美地工作。

haar :: (Fractional a) => [a] -> [a]
haar xs = if logBase 2 (fromIntegral (length xs)) /= truncate (logBase 2 (fromIntegral (length xs)))
             then error "The List must be a power of 2"
             else haarHelper xs (logBase 2 (fromIntegral (length xs)))

haarHelper xs 1 = haarAvgs xs ++ haarDiffs xs
haarHelper xs level = haarHelper (haarAvgs xs ++ haarDiffs xs) (level - 1)

haarAvgs [] = []
haarAvgs (x:y:xs) = ((x + y) / 2.0) : haarAvgs xs 

haarDiffs [] = []
haarDiffs (x:y:xs) = ((x - y) / 2.0) : haarDiffs xs

我收到以下错误消息:

functions.hs:52:13:
    Ambiguous type variable `t' in the constraints:
      `Floating t'
        arising from a use of `logBase' at functions.hs:52:13-48
      `Integral t'
        arising from a use of `truncate' at functions.hs:52:53-99
    Probable fix: add a type signature that fixes these type variable(s)
Failed, modules loaded: none.

Answer 1

有一个更简单、更快速的实现来检查正整数是否为 2 的幂:

import Data.Bits

powerOfTwo' n = n .&. (n-1) == 0

(注意:这省略了对 n 是否为正的检查，假设我们可以依赖它来自 length。)

为了好奇，解释一下:

该算法依赖于只有 2 的幂才有一个 1 位(根据定义)的独特属性，并且递减它们会反转所有较低位:

2^n      =  100000...
2^n - 1  =  011111...

这不会留下任何共同的位，使它们按位和为零。

对于所有非 2 的幂，递减将至少使最高 1 位保持不变，从而使按位与结果保持非零。

(维基百科:Fast algorithm to check if a positive number is a power of two)