haskell - Data.List 中的惰性模式匹配

Question

在 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)

(注:我已经看过 here !它没有回答上述问题)

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作为适当组件的第一个元素，两个列表的其余部分稍后在需要时进行评估。