Является ли выражение в понимании списка избыточным?

Question

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

Оценивает ли GHC concat strings, когда char == 'o', а затем снова, когда char == 'a'? Или он помнит, что concat strings == "foobarbaz" для последующего использования?

Я понимаю, что мог бы избежать этой неопределенности путем рефакторинга этого кода, но меня интересует, как компилируется код.

Answer 1

Что Крис говорит, что в его ответе все верно. Хотя вы не можете полностью полагаться на выражение для совместного использования, это эффективная оптимизация для GHC для его совместного использования, и обычно это делается при оптимизации. Тем не менее, вы можете не захотеть полагаться на эту функциональность, и если вы можете сделать явный доступ к ним, подняв вызов лямбды, я бы так сказал.

Использование 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 остается под лямбдой (ds1_dsF), что означает, что он будет оцениваться каждый раз, когда функция будет оценена, что два раза: один раз в вызове ds_dsE в строку "oa" и один раз в рекурсивном вызове 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 указывает на объединенный трехэлементный список строк. Это явно разделяется, если go_ato вызывается с main_strings.

Answer 2

Он будет оцениваться дважды. GHC не memoize. списочные desugar как этот

[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 м.

Answer 3

GHC может оценивать его гораздо меньше, чем 9 раз. На самом деле это не так, и мы можем доказать, что использование Debug.Trace.trace

module Main (main) where 
import Debug.Trace 

x = let strings = ["foo", "bar", "baz"] 
    in [filter (== char) (trace "\nconcat strings\n" (concat strings)) | char <- "oaxyz"] 

main = do 
    print x 

Вот оценивает для "oaxyz" 5 раз для -O0, и один раз для -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"]