17

在 Data.List 的分区中使用 ~（惰性模式匹配）有哪些性能优势。惰性模式匹配的人为示例表明，当元组构造函数中的值从不使用时（f (x,y) = 1），它很有用。在分区（select，下面）中，总是使用列表 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)

（注意：我已经看过这里！它没有回答上述问题）

4

1 回答 1

17

关键是，通过严格的模式匹配，结果的组装只能在到达要分区的列表末尾时开始，特别是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作为适当组件的第一个元素，两个列表的其余部分稍后在需要时进行评估。

于 2012-09-14T18:01:39.443 回答