Chaining Haskell Функции типов данных

Question

Допустим, у меня есть следующие:

data FuncAndValue v res = FuncAndValue (v -> res) v 

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res 
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v 

ли GHC, вероятно, чтобы иметь возможность совмещать функции new_f и old_f в одну функцию через встраивание?

В принципе, сохранение функций в типах данных в любом случае затрудняет оптимизацию.

Я бы хотел, чтобы GHC легко мог создавать цепочки функций в одну (т. Е. Так что «сумма» в моей структуре не включает повторные вызовы на thunk, который представляет (+), а вместо этого просто вставляет (+), поэтому он работает как цикл. Я надеюсь, что хранение функции в типах данных, а затем доступ к ним позже не подавляет это.

Answer 1

ли GHC, вероятно, чтобы иметь возможность совмещать функции new_f и old_f в одну функцию через встраивание ?

Ye с, если бы он мог сделать то же самое без вмешательства FuncAndValue. Разумеется, разворачивание функций должно быть доступно, иначе шансов на вложение не будет. Но если есть шанс, обертывание функции (функций) в FuncAndValue не имеет большого значения, если таковое имеется.

Но давайте попробуем сам GHC. Первый тип и очень простой chain ING:

module FuncAndValue where 

data FuncAndValue v res = FuncAndValue (v -> res) v 

infixr 7 `chain` 

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res 
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v 

apply :: FuncAndValue v res -> res 
apply (FuncAndValue f x) = f x 

trivia :: FuncAndValue Int (Int,Int) 
trivia = FuncAndValue (\x -> (2*x - 1, 3*x + 2)) 1 

composed :: FuncAndValue Int Int 
composed = chain (uncurry (+)) trivia 

и (интересная часть) ядро ​​мы получаем для trivia и composed:

FuncAndValue.trivia1 = 
    \ (x_af2 :: GHC.Types.Int) -> 
    (case x_af2 of _ { GHC.Types.I# y_agp -> 
    GHC.Types.I# (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1) 
    }, 
    case x_af2 of _ { GHC.Types.I# y_agp -> 
    GHC.Types.I# (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2) 
    }) 

FuncAndValue.composed2 = 
    \ (x_agg :: GHC.Types.Int) -> 
    case x_agg of _ { GHC.Types.I# y_agp -> 
    GHC.Types.I# 
     (GHC.Prim.+# 
     (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1) 
     (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2)) 
    } 

встраиваемого достаточно справедливыми, не (.) видны. Два case s от trivia были соединены так, что у нас есть только один в composed. Если кто-то не учит GHC достаточной алгебре, чтобы упростить \x -> (2*x-1) + (3*x+2) до \x -> 5*x + 1, это так хорошо, как вы можете надеяться. apply composed сокращен до 6 во время компиляции, даже в отдельном модуле.

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

inlinable версия until (текущее определение until является рекурсивным, так GHC не встраивать его),

module WWUntil where 

wwUntil :: (a -> Bool) -> (a -> a) -> a -> a 
wwUntil p f = recur 
    where 
    recur x 
     | p x  = x 
     | otherwise = recur (f x) 

Другой простой функции он ее собственный модуль,

collatzStep :: Int -> Int 
collatzStep n 
    | n .&. 1 == 0 = n `unsafeShiftR` 1 
    | otherwise  = 3*n + 1 

и наконец, гайка

module Hailstone (collatzLength, hailstone) where 

import FuncAndValue 
import CollatzStep 
import WWUntil 

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int 

fstP :: P -> Int 
fstP (P x _) = x 

sndP :: P -> Int 
sndP (P _ y) = y 

hailstone :: Int -> FuncAndValue Int Int 
hailstone n = sndP `chain` wwUntil ((== 1) . fstP) (\(P n k) -> P (collatzStep n) (k+1)) 
        `chain` FuncAndValue (\x -> P x 0) n 

collatzLength :: Int -> Int 
collatzLength = apply . hailstone 

Я помог e анализатор строгости, используя строгую пару. С ванилью (,) второй компонент будет распакован и переустановлен после добавления 1 на каждом шаге, и я просто не могу нести такие отходы;) Но в остальном нет никакой разницы.

И (интересная часть) ядро ​​GHC генерирует:

Rec { 
Hailstone.$wrecur [Occ=LoopBreaker] 
    :: GHC.Prim.Int# 
    -> GHC.Prim.Int# -> (# GHC.Prim.Int#, GHC.Prim.Int# #) 
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL] 
Hailstone.$wrecur = 
    \ (ww_sqq :: GHC.Prim.Int#) (ww1_sqr :: GHC.Prim.Int#) -> 
    case ww_sqq of wild_Xm { 
     __DEFAULT -> 
     case GHC.Prim.word2Int# 
       (GHC.Prim.and# (GHC.Prim.int2Word# wild_Xm) (__word 1)) 
     of _ { 
      __DEFAULT -> 
      Hailstone.$wrecur 
       (GHC.Prim.+# (GHC.Prim.*# 3 wild_Xm) 1) (GHC.Prim.+# ww1_sqr 1); 
      0 -> 
      Hailstone.$wrecur 
       (GHC.Prim.uncheckedIShiftRA# wild_Xm 1) (GHC.Prim.+# ww1_sqr 1) 
     }; 
     1 -> (# 1, ww1_sqr #) 
    } 
end Rec } 

lvl_rsz :: GHC.Types.Int -> GHC.Types.Int 
[GblId, Arity=1, Caf=NoCafRefs] 
lvl_rsz = 
    \ (x_iog :: GHC.Types.Int) -> 
    case x_iog of _ { GHC.Types.I# tpl1_B4 -> 
    case Hailstone.$wrecur tpl1_B4 0 of _ { (# _, ww2_sqH #) -> 
    GHC.Types.I# ww2_sqH 
    } 
    } 

и это именно то, что вы получите без FuncAndValue. Все внятно красиво, красиво плотная петля.

В принципе, сохранение функций в типах данных в любом случае затрудняет оптимизацию.

Если вы завершите функцию с достаточным количеством слоев, да. Но это то же самое с другими значениями.