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

Question

我无法发布让我烦恼的功能,但基本上,我在使用启发式实现A*Search时遇到了运行时问题,该启发式将天花板功能应用到两点之间的直线距离上.在整个函数中我指的是我在最后用"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.5GB驻留内存,然后返回到100MB.第二个没有明显的效果.