将 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

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

在 Haskell 中，当将一个大列表简化为单个汇总值时，如果我们从不"研究"计算的中间值，很容易无意中导致空间泄漏。我们最终可能会得到一棵巨大的未经评估的笨蛋树，隐藏在一个看似无懈可击的单一Double价值后面。

---

foldr的例子泄漏foldr因为它从不强制其蓄能器恢复到弱头正常形式。请改用严格的左foldl'(您需要对某些函数参数重新排序(。foldl'应确保中间Double值保持"小"，并且不会累积。

显式递归

---

示例很危险，因为它不是尾递归的，并且对于大型列表可能会导致堆栈溢出(我们反复将值放入堆栈中，等待下一次递归调用完成(。一种解决方案涉及通过将中间结果作为额外参数传递来使函数尾递归，并在该参数上放置一个 bang 模式以确保不会累积 thunk。

---

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

Answer 2

你可以尝试zipWith后跟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 标志来加速编译的代码。