是冗余计算的列表理解中的表达式

Question

let strings = ["foo", "bar", "baz"]
in  [filter (== char) (concat strings) | char <- "oa"]

全康在char == 'o'时评估concat strings，然后在char == 'a'时再次评估？还是它记得concat strings == "foobarbaz"供以后使用？

我

意识到我可以通过重构这段代码来避免这种不确定性，但我对代码的编译方式很感兴趣。

Answer 1

GHC可能评估它的次数远远少于9次。 事实上，它确实如此，我们可以证明使用Debug.Trace.trace

module Main (main) where 
import Debug.Trace
x = let strings = ["foo", "bar", "baz"]
    in  [filter (== char) (trace "nconcat stringsn" (concat strings)) | char <- "oaxyz"]
main = do
    print x

以下是 "oaxyz" 对 -O0 的 5 次评估，对 -O1 和 -O2 的一次计算：

! 529)-> touch LC.hs ; ghc -O0 -o lc0 LC.hs 
[1 of 1] Compiling Main             ( LC.hs, LC.o )
Linking lc0 ...
(! 530)-> touch LC.hs ; ghc -O1 -o lc1 LC.hs 
[1 of 1] Compiling Main             ( LC.hs, LC.o )
Linking lc1 ...
(! 531)-> ./lc0; ./lc1; ./lc2
concat strings

concat strings

concat strings

concat strings

concat strings
["oo","aa","","","z"]
concat strings
["oo","aa","","","z"]
concat strings
["oo","aa","","","z"]

Answer 2

克里斯在

回答中所说的都是真的。虽然您不能完全依赖要共享的表达式，但 GHC 共享它是有效的优化，并且通常会在启用优化时执行此操作。尽管如此，您可能不想依赖此功能，并且如果您可以通过从 lambda 中解除concat调用来明确预期的共享，我会这样做。

将Debug.Trace.trace用于此类目的是了解何时以及多久评估一次的好方法。

另一种选择是查看生成的核心代码。对于此计划：

main = print x
x = let strings = ["foo", "bar", "baz"]
    in  [filter (== char) (concat strings) | char <- "oa"]

让我们编译没有优化并查看结果代码：

$ ghc NrEval -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling Main             ( NrEval.hs, NrEval.o )
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 50, types: 54, coercions: 0}
main
main =
  print
    ($fShow[] ($fShow[] $fShowChar))
    (let {
       a_ssN
       a_ssN = unpackCString# "foo" } in
     let {
       a1_ssQ
       a1_ssQ = unpackCString# "bar" } in
     let {
       a2_ssT
       a2_ssT = unpackCString# "baz" } in
     let {
       a3_ssU
       a3_ssU = : a2_ssT ([]) } in
     let {
       a4_ssV
       a4_ssV = : a1_ssQ a3_ssU } in
     let {
       strings_ahk
       strings_ahk = : a_ssN a4_ssV } in
     letrec {
       ds_dsE
       ds_dsE =
          ds1_dsF ->
           case ds1_dsF of _ {
             [] -> [];
             : ds3_dsG ds4_dsH ->
               : (filter
                    ( ds5_dsI -> == $fEqChar ds5_dsI ds3_dsG) (concat strings_ahk))
                 (ds_dsE ds4_dsH)
           }; } in
     ds_dsE (unpackCString# "oa"))
main
main = runMainIO main

我们可以看到，即使没有优化，列表理解也已脱糖为map的(内联(应用程序 ds_dsE .但是，concat strings_ahk仍然在lambda(ds1_dsF(下，这意味着每次计算函数时都会对其进行评估，这是两次：一次是在对字符串"oa" ds_dsE的调用中，一次是在递归调用ds_dsE ds4_dsH中。

现在，让我们将结果与优化进行比较：

$ ghc NrEval -fforce-recomp -ddump-simpl -dsuppress-all -O
[1 of 1] Compiling Main             ( NrEval.hs, NrEval.o )
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 89, types: 105, coercions: 9}
main9
main9 = unpackCString# "foo"
main8
main8 = unpackCString# "bar"
main7
main7 = unpackCString# "baz"
main6
main6 = : main7 ([])
main5
main5 = : main8 main6
main_strings
main_strings = : main9 main5
main4
main4 =
   ds_dsT ds1_dsS ->
    : (letrec {
         go_ato
         go_ato =
            ds2_atp ->
             case ds2_atp of _ {
               [] -> [];
               : y_atu ys_atv ->
                 let {
                   z_XtU
                   z_XtU = go_ato ys_atv } in
                 letrec {
                   go1_XtX
                   go1_XtX =
                      ds3_XtZ ->
                       case ds3_XtZ of _ {
                         [] -> z_XtU;
                         : y1_Xu6 ys1_Xu8 ->
                           case y1_Xu6 of wild2_atz { C# c1_atB ->
                           case ds_dsT of _ { C# c2_atF ->
                           case eqChar# c1_atB c2_atF of _ {
                             False -> go1_XtX ys1_Xu8;
                             True -> : wild2_atz (go1_XtX ys1_Xu8)
                           }
                           }
                           }
                       }; } in
                  go1_XtX y_atu
              }; } in
       go_ato main_strings)
      ds1_dsS
main3
main3 = unpackFoldrCString# "oa" main4 ([])
main2
main2 = showList__ $fShowChar_$cshowList main3 ([])
main1
main1 =  eta_B1 -> hPutStr2 stdout main2 True eta_B1
main
main = main1 `cast` ...
main10
main10 =  eta_Xp -> runMainIO1 (main1 `cast` ...) eta_Xp
main
main = main10 `cast` ...

在这里，我们可以看到发生了很多事情，但特别是，对 concat strings 的调用已被提升到顶层并在编译时完全展开，导致main_strings指向串联的三元素字符串列表。当与main_strings调用go_ato时，这显然是共享的。

Answer 3

它将被评估两次。全康不记。列表理解像这样脱糖

 [term | x <- xs, y <- ys ...] -- I ignore guards
 do
  x <- xs
  y <- ys
  ...
  return term

这与

 flip concatMap xs $ x -> flip concatMap ys $ y -> ... [term]

因此，很明显，term将被计算l1 * l2 * l3 ... ln次，其中li是第 i 个列表的长度。