是否在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的调用之间共享。