haskell可以優化不尾遞歸函數嗎？

我有以下程序：haskell可以優化不尾遞歸函數嗎？

my_sum 0 = 54321 
my_sum i = i + (my_sum (i - 1)) 

main = do 
    print $ my_sum 12345

我想找出產生my_sum功能是否是遞歸的。換句話說，haskell將這個轉換爲不遞歸的類型。

我試圖看到本地c--代碼（asm幾乎相同）。但對我來說太困難了。它的代碼是my_sum：

my_sum_s24N_entry() // [R1] 
    { info_tbl: [(c25x, 
        label: block_c25x_info 
        rep:StackRep [False, False]), 
        (c267, 
        label: my_sum_s24N_info 
        rep:HeapRep 1 nonptrs { Fun {arity: 1 fun_type: ArgSpec 5} })] 
     stack_info: arg_space: 8 updfr_space: Just 4 
    } 
{offset 
    c267: 
     _s24N::P32 = R1; 
     _s24O::P32 = P32[Sp]; 
     if ((Sp + 8) - 32 < SpLim) goto c268; else goto c269; 
    c269: 
     Hp = Hp + 8; 
     if (Hp > HpLim) goto c26b; else goto c26a; 
    c26b: 
     HpAlloc = 8; 
     goto c268; 
    c268: 
     R1 = _s24N::P32; 
     call (stg_gc_fun)(R1) args: 8, res: 0, upd: 4; 
    c26a: 
     I32[Hp - 4] = sat_s24V_info; 
     _c25n::P32 = Hp - 4; 
     I32[Sp - 8] = c25x; 
     P32[Sp - 24] = GHC.Integer.Type.$fEqInteger_closure; 
     I32[Sp - 20] = stg_ap_pp_info; 
     P32[Sp - 16] = _s24O::P32; 
     P32[Sp - 12] = _c25n::P32; 
     P32[Sp - 4] = _s24N::P32; 
     Sp = Sp - 24; 
     call GHC.Classes.==_info() returns to c25x, args: 20, res: 4, upd: 4; 
    c25x: 
     _s24N::P32 = P32[Sp + 4]; 
     _s24O::P32 = P32[Sp + 8]; 
     _s24W::P32 = R1; 
     _c266::P32 = _s24W::P32 & 3; 
     if (_c266::P32 != 1) goto c265; else goto c264; 
    c265: 
     Hp = Hp + 8; 
     if (Hp > HpLim) goto c26j; else goto c26i; 
    c26j: 
     HpAlloc = 8; 
     R1 = _s24W::P32; 
     call stg_gc_unpt_r1(R1) returns to c25x, args: 4, res: 4, upd: 4; 
    c26i: 
     I32[Hp - 4] = GHC.Integer.Type.S#_con_info; 
     I32[Hp] = 54321; 
     _c26k::P32 = Hp - 3; 
     P32[Sp] = GHC.Num.$fNumInteger_closure; 
     I32[Sp + 4] = stg_ap_p_info; 
     P32[Sp + 8] = _c26k::P32; 
     call GHC.Num.fromInteger_info() args: 16, res: 0, upd: 4; 
    c264: 
     Hp = Hp + 16; 
     if (Hp > HpLim) goto c26e; else goto c26d; 
    c26e: 
     HpAlloc = 16; 
     R1 = _s24W::P32; 
     call stg_gc_unpt_r1(R1) returns to c25x, args: 4, res: 4, upd: 4; 
    c26d: 
     I32[Hp - 12] = sat_s250_info; 
     P32[Hp - 4] = _s24N::P32; 
     P32[Hp] = _s24O::P32; 
     _c25B::P32 = Hp - 12; 
     P32[Sp - 4] = GHC.Num.$fNumInteger_closure; 
     I32[Sp] = stg_ap_pp_info; 
     P32[Sp + 4] = _s24O::P32; 
     P32[Sp + 8] = _c25B::P32; 
     Sp = Sp - 4; 
     call GHC.Num.+_info() args: 20, res: 0, upd: 4; 
} 
}

來源

2017-01-09 LmTinyToon

GHC核心通常更具可讀性，而不是C--。從簡單的角度來看，我會說它是作爲一個遞歸函數而留下的。請記住註釋類型，順便說一下：這對優化程序有很大的幫助。 – chi

答案是否定的，GHC不會優化它到尾遞歸函數。作爲一個評論者指出，要看到這一點，你應該看看GHC核心^：

Rec { 
my_sum :: Integer -> Integer 
my_sum = 
    \ (ds :: Integer) -> 
    case eqInteger# ds my_sum'2 of wild { __DEFAULT -> 
    case tagToEnum# wild of _ { 
     False -> plusInteger ds (my_sum (minusInteger ds lvl)); 
     True -> my_sum'1 
    } 
    } 
end Rec }

這個功能顯然不是尾遞歸 - 最外面的調用是plusInteger。 GHC核心是所有優化執行後的代碼 - 該代碼實際上已轉換爲機器代碼。所以你知道，如果你的函數在覈心中不是尾遞歸的，它實際上不是尾遞歸。它也基本上就是Haskell，除了一些有趣的名字，所以閱讀它不應該是一個問題。

如果你想要一個尾遞歸函數，只需使用foldl'：

import Data.List (foldl') 

my_sum' :: Integer -> Integer 
my_sum' i0 = foldl' (+) 54321 [0..i0]

其中給出了以下核心：

my_sum' :: Integer -> Integer 
my_sum' = 
    \ (i0 :: Integer) -> 
    letrec { 
     go :: Integer -> Integer -> Integer 
     go = 
     \ (x :: Integer) (eta :: Integer) -> 
      case gtInteger# x i0 of wild { __DEFAULT -> 
      case tagToEnum# wild of _ { 
      False -> go (plusInteger x $fEnumInteger1) (plusInteger eta x); 
      True -> eta 
      } 
      }; } in 
    go my_sum'2 my_sum'1

這裏my_sum'2，my_sum'1和lvl是在程序中的常量：

my_sum'2 :: Integer 
my_sum'2 = 0 
my_sum'1 :: Integer 
my_sum'1 = 54321 
lvl :: Integer 
lvl = 1

^生成選項-ddump-simpl -dsuppress-idinfo -dsuppress-coercions -dsuppress-type-applications -dsuppress-uniques -dsuppress-module-prefixes --make

來源

2017-01-10 00:01:14 user2407038

這就是我需要的。謝謝！ – LmTinyToon

haskell可以優化不尾遞歸函數嗎？

回答

相關問題