是否在Haskell中定義了部分函數或curried函數？

Question

在下面的代碼：

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子句的引用？

我有一些CPU的綁定代碼不能令人滿意地執行，我在尋找可能的錯誤在我的推理複雜性。

Answer 1

作爲您可以從分析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，其他人太快，甚至無法注意到，所以它必須在這裏計算最大值一次。

Answer 2

我一直沒能在Haskell Report中找到任何這樣的要求，事實上GHC似乎並未默認執行此優化。

我改變了你main功能

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 

Answer 3

這是你的代碼的修改版本，將讓你看到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開始做減少操作，直到全部的參數被提供給一個函數。另一方面，如果開啓了積極的優化，那麼很難預測特定的編譯器實際上會做什麼。但是你可能不應該依賴編譯器的任何部分，這很難預測何時你可以輕鬆地重寫代碼來製作你想要的東西。

Answer 4

GHC並沒有急於根據我的經驗進行這種優化。如果我不能輕易做出點東西自由，我常常訴諸與約束瓦爾對LHS和拉姆達混合寫着：

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

我特別不喜歡這種風格，但它確保maxel在部分應用ismaxl的調用之間共享。