Haskell中check函数类型定义与实现错误排查求助

问题分析 #

你的check函数存在两个核心问题：

1. 类型签名错误：你定义的check :: (Integral a) => a -> a -> Bool表示需要两个参数，但实际上只需要一个输入n，正确类型应该是(Integral a) => a -> Bool。
2. 逻辑实现错误：factorial (choose n)完全不符合需求——choose需要两个参数（n和r），而我们需要的是从r=0到n的所有C(n,r)的和，不是对组合数求阶乘。

修正后的代码 #

factorial :: (Integral a) => a -> a
factorial 0 = 1 
factorial n = n * factorial (n - 1)

choose :: (Integral a) => a -> a -> a
n `choose` r
    | r < 0     = 0
    | r > n     = 0
    | otherwise = factorial n `div` (factorial r * factorial (n-r))

-- 修正后的check函数
check :: (Integral a) => a -> Bool
check n = sum [n `choose` r | r <- [0..n]] == (2 ^ n)

细节解释 #

• 类型修正：check只接收一个Integral类型的参数n，返回Bool值，完全匹配需求。
• 求和逻辑：用列表推导[n choose r | r <- [0..n]]生成从r=0到n的所有组合数，再通过sum计算它们的总和。
• 整数幂运算优化：如果要避免类型歧义或提升效率，可改用位运算shiftL 1 n（因为2ⁿ等价于1左移n位），此时需要导入Data.Bits模块：

  import Data.Bits (shiftL)
  
  check :: (Integral a, Bits a) => a -> Bool
  check n = sum [n `choose` r | r <- [0..n]] == shiftL 1 n
  

测试示例 #

运行以下代码可验证正确性：

check 0  -- 输出True（C(0,0)=1，2^0=1）
check 1  -- 输出True（1+1=2，2^1=2）
check 3  -- 输出True（1+3+3+1=8，2^3=8）

内容的提问来源于stack exchange，提问作者user123