将 Haskell 中的大列表处理成单个值

Question

我有 2 个大小相等的 Int 列表（大约 10,000 个元素）：比如 x 和 y。我需要为列表中的每对对应元素计算以下表达式的乘积：x_i/(x_i+y_i)，即 x_i 和 y_i 是列表的第一个元素，然后是第二个，依此类推

我的方法适用于小型测试用例，但 ghci 对于较大的列表会挂起。任何关于原因和解决方案的见解都将不胜感激。

我试着用折叠来做到这一点，首先压缩列表：

getP:: [Int] -> [Int] -> Double
getP zippedCounts = foldr (\(x,y) acc -> let intX = fromIntegral x
                                             intY = fromIntegral y
                                             intSum = intX + intY in
                                             (acc*(intX/intSum))) 
                          1.0
                          zippedCounts

我也试过回避：

getP lst [] = 1.0
getP [] lst = 1.0
getP (h1:t1) (h2:t2) = ((fromIntegral h1) / ((fromIntegral h1) + (fromIntegral h2))) * (getP t1 t2)

以及列表理解：

getP lst1 lst2 = (product [((fromIntegral x) / ((fromIntegral x) + (fromIntegral y)))|x <- lst1, y <- lst2])

Answer 1

你可以试试 zipWith followed by product:

getP :: [Int] -> [Int] -> Double
getP xs ys = product $ zipWith func xs ys
  where 
    func x y = let dx = fromIntegral x
                   dy = fromIntegral y
               in dx / (dx + dy)

我会避免使用显式递归并坚持使用库函数以提高速度。您还可以使用某些 ghc flags 来加速编译代码。

Answer 2

所有三个解决方案都有 space 泄漏，也许这就是导致无响应的原因。

在Haskell中，当将一个大列表缩减为单个汇总值时，如果我们从不"look into"计算的中间值，很容易无意中造成space泄漏.我们最终会得到一个隐藏在看似无害的单个 Double 值后面的巨大的未计算 thunk 树。

foldr 示例泄漏，因为 foldr 从不强制其累加器改为 weak head normal form. Use the strict left foldl'（您需要重新排序一些函数参数）。 foldl' 应确保中间 Double 值保持 "small" 并且 thunk 不会累积。

显式递归示例是危险的，因为它不是尾递归的，对于大列表可能会导致堆栈溢出（我们反复将值放入堆栈，等待下一次递归调用完成）。一个解决方案是通过 passing the intermediate result as an extra parameter, and putting a bang pattern 在该参数上使函数尾递归，以确保 thunk 不会累积。

product 示例泄漏是因为，不幸的是，sum 和 product 函数都不严格。对于大型列表，最好改用 foldl'。（还有一个错误，正如评论中提到的那样。）

将 Haskell 中的大列表处理成单个值

Process large lists in Haskell into a single value

haskell

large-data