Haskell -引用使用where定义的列表，是只创建一次列表，还是每次引用都创建列表？

Question

我不能发布给我带来麻烦的my函数，但基本上，我在使用启发式方法实现A*搜索时遇到了运行时问题，启发式方法将上限函数应用于两点之间的直线距离。在整个函数中，我引用了我在末尾使用"where“定义的一个列表，我相信它是这个列表中的一个函数，导致了运行时问题(因为当我删除它时，它运行得很快)，但我不明白为什么，因为它根本不是一个复杂的函数。这让我相信，函数可能在每次引用它时都试图重新创建列表，而不是只引用一次，每次都使用已经形成的列表，这可能会减慢它的速度，并导致运行时间呈指数级增加。

也就是说，作为一个基本示例，我在函数中引用了3次"myList“。

function :: Int -> [Int]
function x = head (myList) : (maximum (myList) : minimum (myList))
           where myList = [snd pair | pair <- (zip [0..] [sortBy compare [5*x,3-x,99*x]])]

这花费的计算时间是否与...

function 5 = head ([snd pair | pair <- (zip [0..] [sortBy compare [5*5,3-5,99*5]])]) 
             : (maximum ([snd pair | pair <- (zip [0..] [sortBy compare [5*5,3-5,99*5]])]) 
             : minimum ([snd pair | pair <- (zip [0..] [sortBy compare [5*5,3-5,99*5]])]))

也就是说，它在整个函数中从头开始形成列表三次，即使结果总是相同的。

或者它只计算一次，并在调用函数时使用该值？

我不知道如果不是这样，它会是什么样子，但作为一个有点混乱的伪代码和Haskell，我想它会是这样的。

function 5...
-- First step, Calculate myList
MyList = [snd pair | pair <- (zip [0..] [sortBy compare [5*5,3-5,99*5]])]
       = [-2,25,495]

--Second step, calculate function using myList = [-2,25,495]
function 5 = head (myList) : (maximum (myList) : minimum (myList))
           = head [-2,25,495] : maximum [-2,25,495] : minimum [-2,25,495]
           = -2 : (495 : -2)
           = [-2,495,-2]

我希望我在这里要问的问题不会太难理解。

任何帮助都将不胜感激，谢谢！

Answer 1

Haskell的报告没有说明它是如何评估的:它只是说明了结果是什么。

但是，GHC只会计算一次这样的列表。如果列表的生成成本很高，这会对性能产生积极的影响，因为它只会生成一次。记住，在某些情况下，它也可能对性能产生负面影响:例如，(愚蠢的例子)

let bigList = [1..1000000]
in  foldl' (+) 0 bigList + foldl' (-) 0 bigList

将在内存中保留较大的列表，直到计算完两个折叠。相反，

foldl' (+) 0 [1..1000000] + foldl' (-) 0 [1..1000000]

可以在恒定的空间中运行，因为一旦产生列表元素，它们就可以被垃圾收集。

例如，使用50M的列表，首先使GHCi达到2.5 to的驻留内存，然后返回到100MB。第二个没有明显的影响。