Data.List中的延迟模式匹配

Question

在Data.List的分区中使用〜(延迟模式匹配)有什么性能优势.惰性模式匹配的受控示例表明,当从不使用元组构造函数内的值时(f(x,y)= 1),它很有用.在分区(选择,下面)中,始终使用列表ts,fs(如果应用于x的谓词p为True,或者不是).我确信这是一个非常明智的决定使用〜,但有什么意义呢？为什么不严格模式匹配？

partition               :: (a -> Bool) -> [a] -> ([a],[a])
{-# INLINE partition #-}
partition p xs = foldr (select p) ([],[]) xs

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

(注意:我已经看过这里了!它没有回答上面的问题)

Answer 1

关键在于,通过严格的模式匹配,结果的组合只能在已经到达要分区的列表的末尾时开始,特别是partition对于无限列表根本不起作用.

使用严格的模式匹配,必须将参数计算为WHNF.这意味着在foldr判断是否x放入第一个或第二个组件之前,必须完成整个尾部.

select p x (foldr (select p) ([],[]) (y:z:ws))
~> select p x (select p y (select p z (foldr (select p) ([],[]) ws)))

使用惰性模式匹配时,立即构造一对,x作为适当组件的第一个元素,并在需要时稍后评估两个列表中的其余部分.