Хорошо ли определено выполнение частичных или каррированных функций в Haskell? - PullRequest
Новая
       18

Хорошо ли определено выполнение частичных или каррированных функций в Haskell?

22 голосов
/ 12 ноября 2010

В следующем коде: 

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
           where maxel = maximum l

main = do
  let mylist = [1, 2, 3, 5]
  let ismax = ismaxl mylist
  --Is each call O(1)?  Does each call remember maxel?
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

Частичная функция ismax, вычисляет maxel?В частности, кто-то может указать на правило о сложности частичных функций в Haskell?ДОЛЖЕН ли компилятор вызывать максимум один раз в приведенном выше примере?Другими словами, сохраняет ли частичная функция ссылки предыдущих вызовов для внутренних предложений where?

У меня есть некоторый код с привязкой к ЦП, который не выполняется приемлемо, и я ищу возможные ошибки в своих рассужденияхсложность.

Ответы [ 4 ]

17 голосов
/ 12 ноября 2010

В качестве демонстрации того, что вы можете узнать из профилирования вашего кода на Haskell, вот результат некоторых незначительных изменений в вашем коде.Во-первых, я заменил mylist на [0..10000000], чтобы убедиться, что для вычисления максимума требуется некоторое время.

Вот несколько строк из вывода профилирования после запуска этой версии: 

COST CENTRE                    MODULE               %time %alloc

ismaxl                         Main                  55.8    0.0
main                           Main                  44.2  100.0

                                                         individual    inherited
COST CENTRE              MODULE         no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN            1           0   0.0    0.0   100.0  100.0
 CAF:main_c5             Main          225           1   0.0    0.0    15.6    0.0
  main                   Main          249           0   0.0    0.0    15.6    0.0
   ismaxl                Main          250           1  15.6    0.0    15.6    0.0
 CAF:main_c3             Main          224           1   0.0    0.0    15.6    0.0
  main                   Main          246           0   0.0    0.0    15.6    0.0
   ismaxl                Main          247           1  15.6    0.0    15.6    0.0
 CAF:main_c2             Main          223           1   0.0    0.0    14.3    0.0
  main                   Main          243           0   0.0    0.0    14.3    0.0
   ismaxl                Main          244           1  14.3    0.0    14.3    0.0
 CAF:main_c1             Main          222           1   0.0    0.0    10.4    0.0
  main                   Main          239           0   0.0    0.0    10.4    0.0
   ismaxl                Main          240           1  10.4    0.0    10.4    0.0
 CAF:main8               Main          221           1   0.0    0.0    44.2  100.0
  main                   Main          241           0  44.2  100.0    44.2  100.0

Здесь довольно очевидно пересчитать максимум.

Теперь, заменив ismaxl на это: 

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = let maxel = maximum l in (== maxel)

... и снова профилируя: 

COST CENTRE                    MODULE               %time %alloc

main                           Main                  60.5  100.0
ismaxl                         Main                  39.5    0.0

                                                         individual    inherited
COST CENTRE              MODULE         no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN            1           0   0.0    0.0   100.0  100.0
 CAF:main_c5             Main          227           1   0.0    0.0     0.0    0.0
  main                   Main          252           0   0.0    0.0     0.0    0.0
   ismaxl                Main          253           1   0.0    0.0     0.0    0.0
 CAF:main_c3             Main          226           1   0.0    0.0     0.0    0.0
  main                   Main          249           0   0.0    0.0     0.0    0.0
   ismaxl                Main          250           1   0.0    0.0     0.0    0.0
 CAF:main_c2             Main          225           1   0.0    0.0     0.0    0.0
  main                   Main          246           0   0.0    0.0     0.0    0.0
   ismaxl                Main          247           1   0.0    0.0     0.0    0.0
 CAF:main_c1             Main          224           1   0.0    0.0     0.0    0.0
 CAF:main_ismax          Main          223           1   0.0    0.0    39.5    0.0
  main                   Main          242           0   0.0    0.0    39.5    0.0
   ismaxl                Main          243           2  39.5    0.0    39.5    0.0
 CAF:main8               Main          222           1   0.0    0.0    60.5  100.0
  main                   Main          244           0  60.5  100.0    60.5  100.0

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

11 голосов
/ 12 ноября 2010

Вот модифицированная версия вашего кода, которая позволит вам увидеть, используется ли maxel повторно или нет: 

import Debug.Trace

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
           where maxel = trace "Hello" $ maximum l

main = do
  let mylist = [1, 2, 3, 5]
  let ismax = ismaxl mylist
  --Is each call O(1)?  Does each call remember maxel?
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

Вы увидите, что maxel не запоминается между приложениями.

Как правило, не следует ожидать, что Haskell начнет выполнять сокращения, пока все аргументов не будут переданы функции.

С другой стороны, если выесли включить агрессивную оптимизацию, трудно предсказать, что конкретно будет делать конкретный компилятор.Но вам, вероятно, не следует полагаться на какую-либо часть компилятора, которую сложно предсказать, когда вы можете легко переписать код, чтобы сделать то, что вы хотите, явным.

6 голосов
/ 12 ноября 2010

Опираясь на другие хорошие ответы, GHC не стремился выполнить такую ​​оптимизацию в моем опыте.Если я не могу легко сделать что-то бессмысленное, я часто прибегаю к письму со смешанными переплетами на LHS и лямбде: 

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = \x -> x == maxel
           where maxel = maximum l

Мне не особенно нравится этот стиль,но он гарантирует, что maxel является общим для вызовов к частично примененному ismaxl.

1 голос
/ 12 ноября 2010

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

Я изменил ваше main function to 

main = do
  let mylist = [1..99999]
  let ismax = ismaxl mylist
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

Простое профилирование показывает (на моем старом Pentium 4): 

$ ghc a.hs
$ time ./a.out 
[False,False,False,False]

real    0m0.313s
user    0m0.220s
sys     0m0.044s

Но когда я меняю определение c2, c3 и c5 до let c2 = 2 == 99999 и т. д. (оставив c1 как есть), я получаю 

$ ghc a.hs
$ time ./a.out 
[False,False,False,False]

real    0m0.113s
user    0m0.060s
sys     0m0.028s
...