我应该避免在Haskell中构建吗？

Question

在阅读Haskell for the Good的剪辑时,我发现了以下情况:

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
  | x == a = Node x left right  
  | x < a  = Node a (treeInsert x left) right  
  | x > a  = Node a left (treeInsert x right)

如果我们只是重用给定的Tree,那对性能不是更好x == a吗？

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x all@(Node a left right)   
  | x == a = all  
  | x < a  = Node a (treeInsert x left) right  
  | otherwise  = Node a left (treeInsert x right)

在现实生活中编码,我该怎么办？返回同样的东西有什么缺点吗？

Answer 1

让我们来看看核心!(这里没有优化)

$ ghc-7.8.2 -ddump-simpl wtmpf-file13495.hs

相关的区别是第一个版本(没有all@(...))有

                case GHC.Classes.> @ a_aUH $dOrd_aUV eta_B2 a1_aBQ
                of _ [Occ=Dead] {
                  GHC.Types.False ->
                    Control.Exception.Base.patError
                      @ (TreeInsert.Tree a_aUH)
                      "wtmpf-file13495.hs:(9,1)-(13,45)|function treeInsert"#;
                  GHC.Types.True ->
                    TreeInsert.Node
                      @ a_aUH
                      a1_aBQ
                      left_aBR
                      (TreeInsert.treeInsert @ a_aUH $dOrd_aUV eta_B2 right_aBS)

将节点重新用于as-pattern的地方就是这样

                TreeInsert.Node
                  @ a_aUI
                  a1_aBR
                  left_aBS
                  (TreeInsert.treeInsert @ a_aUI $dOrd_aUW eta_B2 right_aBT);

这是一种避免检查,可能会产生显着的性能差异.

但是,这种差异实际上与as-pattern无关.这只是因为你的第一个片段使用了一个x > a保护,这不是一件容易的事.第二种用途otherwise,已经过优化.

如果您将第一个代码段更改为

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
  | x == a     = Node x left right  
  | x < a      = Node a (treeInsert x left) right  
  | otherwise  = Node a left (treeInsert x right)

然后差异归结为

      GHC.Types.True -> TreeInsert.Node @ a_aUH a1_aBQ left_aBR right_aBS

VS

      GHC.Types.True -> wild_Xa

这确实只是Node x left rightvs 的区别all.

......没有优化,就是这样.当我打开时,版本会进一步分散-O2.但我无法弄清楚性能如何不同.