什么时候应该使用as-patterns来识别常见的子表达式？

Question

我想知道我在多大程度上担心微优化Haskell中的公共子表达式(使用GHC),特别是在数据解构方面.

例如,请考虑使用此代码合并两个有序列表:

merge :: Ord a => [a] -> [a] -> [a]
merge [] bs = bs
merge as [] = as
merge (a:as) (b:bs) =
  case compare a b of
    LT -> a : merge as (b:bs)  -- (1)
    EQ -> a : merge as bs
    GT -> b : merge (a:as) bs  -- (2)

GHC会认识到(a:as)at(2)和(b:bs)at(1)与输入参数相同吗？或者,我应该使用"as"模式,例如:

merge a'@(a:as) b'@(b:bs) =
  ...
  LT -> a : merge as b'
  ...
  GT -> b : merge a' bs

一般情况下,GHC能否识别数据结构中的常见子表达式,何时需要帮助它？

Answer 1

这取决于.如果您在没有优化的情况下进行编译,那么不使用as-patterns肯定会受到惩罚,但是如果您编译以下代码

module Test where


merge1 :: Ord a => [a] -> [a] -> [a]
merge1 [] bs = bs
merge1 as [] = as
merge1 (a:as) (b:bs) = case compare a b of
    LT -> a : merge1 as (b:bs)
    EQ -> a : merge1 as bs
    GT -> b : merge1 (a:as) bs


merge2 :: Ord a => [a] -> [a] -> [a]
merge2 [] bs = bs
merge2 as [] = as
merge2 xs@(a:as) ys@(b:bs) = case compare a b of
    LT -> a : merge2 as ys
    EQ -> a : merge2 as bs
    GT -> b : merge2 xs bs

使用-O2和-ddump-simpl,经过大量明智的编辑,重命名变量,剥离元数据和注释,以及各种其他技巧,你可以得到像

merge2_2 :: Ord a => a -> [a] -> [a] -> [a]
merge2_2 = \ ordInst x y z -> case z of _ {
      [] -> (x:y);
      (w:v) -> case compare ordInst x w of _ {
          LT -> x : merge2_1 ordInst y w v;
          EQ -> x : merge2   ordInst y   v;
          GT -> w : merge2_2 ordInst x y v
        }
    }

merge2_1 :: Ord a => [a] -> a -> [a] -> [a]
merge2_1 = \ ordInst x y z -> case x of _ {
      [] -> (y:z);
      (w:v) -> case compare ordInst w y of _ {
          LT -> w : merge2_1 ordInst v y z;
          EQ -> w : merge2   ordInst v   z;
          GT -> y : merge2_2 ordInst w v z
        }
    }

merge2 :: Ord a => [a] -> [a] -> [a]
merge2 = \ ordInst x y -> case x of wild {
      [] -> y;
      (w:v) -> case y of _ {
          [] -> wild;
          (z:zs) -> case compare ordInst w z of _ {
              LT -> w : merge2_1 ordInst v z zs;
              EQ -> w : merge2   ordInst v   zs;
              GT -> z : merge2_2 ordInst w v zs
            }
        }
    }


merge1_2 :: Ord a => a -> [a] -> [a] -> [a]
merge1_2 = \ ordInst x y z -> case z of _ {
      [] -> (x:y);
      (w:v) -> case compare ordInst x w of _ {
          LT -> x : merge1_1 ordInst y w v;
          EQ -> x : merge1   ordInst y   v;
          GT -> w : merge1_2 ordInst x y v
        }
    }

merge1_1 :: Ord a => [a] -> a -> [a] -> [a]
merge1_1 = \ ordInst x y z -> case x of _ {
      [] -> (y:z);
      (w:v) -> case compare ordInst w y of _ {
          LT -> w : merge1_1 ordInst v y z;
          EQ -> w : merge1   ordInst v   z;
          GT -> y : merge1_2 ordInst w v z
        }
    }

merge1 :: Ord a => [a] -> [a] -> [a]
merge1 = \ ordInst x y -> case x of wild {
      [] -> y;
      (w:v) -> case y of _ {
          [] -> wild;
          (z:zs) -> case compare ordInst w z of _ {
              LT -> w : merge1_1 ordInst v z zs;
              EQ -> w : merge1   ordInst v   zs;
              GT -> z : merge1_2 ordInst w v zs
            }
        }
    }

与diffing工具相比,它告诉我这两个定义之间的唯一区别是merge函数名末尾的数字.所以是的,在应用优化之后,GHC可以为您找出这些模式,至少在列表的情况下.但是,我仍然建议使用它们,因为总有边缘情况,如果你确实使用它们,那么你不必相信编译器做一些复杂的事情.这也意味着即使没有启用优化,您的代码仍然会在那里进行优化.这似乎是一个微小的变化,但是如果这个函数最终在内部循环中或者你正在处理的结构非常大,那么它可能会对性能产生重大影响.另外,我发现对于具有大量字段的构造函数,使用名称来引用"构造"形式通常更方便.

如果您有兴趣,这是完整的核心转储.基本上,我开始通过连接线一起占用更少的空间,然后在类型签名去掉不必要的噪音,去除合格的模块名称,所有的[Something]注释,改名之类的东西merge2_$smerge2来merge2_2,去掉所有的本地类型签名,然后开始使用重命名崇高文字的精彩的多个游标功能.我开始与类型名,他们都重命名为刚a,然后重命名变量名x,y,z,w,v,和zs(我的创意,不是吗？),作出的所有应用程序:操作中缀,取出Rec地区,再过几次造型,我得到了你上面看到的输出.