时间戳

首页 > 解决方案 > 将 Haskell 中的大型列表处理为单个值

haskell - 将 Haskell 中的大型列表处理为单个值

问题描述

我有 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])

标签： haskelllarge-data

解决方案

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

在 Haskell 中，当将大列表缩减为单个汇总值时，如果我们从不“查看”计算的中间值，很容易无意中导致空间泄漏。我们最终会得到一棵巨大的未经评估的 thunk 树，隐藏在一个看似无害的单一Double值后面。

该foldr示例泄漏是因为foldr从不强制其累加器为弱头范式。改用严格的左键foldl'（您需要重新排序一些函数参数）。foldl'应该确保中间Double值保持“小”并且不会累积。

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

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

推荐阅读