Haskell中将单字段data重构为newtype为何能大幅提升程序性能

我编写了一个遍历表达式树的程序，用于对概率分布执行代数运算，支持采样或直接计算最终得到的分布。

我实现了两套分布计算逻辑：

• 一套是基于monad转换器、复用性良好的computeDistribution
• 另一套是手动完成全量具体化的simpleDistribution
  我不希望采用手动全量具体化的实现方式，否则会在采样逻辑和分布计算逻辑间产生大量代码重复。

初始类型定义与性能观测 #

我最初使用两种数据类型表示分布：

type Measure a = [(a, Rational)]
-- data Distribution a = Distribution (Measure a) deriving Show
newtype Distribution a = Distribution (Measure a) deriving Show

测试计算20d2（20个两面骰子点数和）分布的性能时，观测到明显差异：

• 当我将data版本的类型定义搭配可复用代码使用时，编译运行命令为ghc -O3 program.hs; time ./program 20 > /dev/null，耗时约1秒，速度明显过慢，n取更大值时耗时会急剧上升
• 当我使用手动具体化的代码，或是任意实现搭配newtype类型表示时，运行命令为time ./program 20 s > /dev/null，耗时极短，几乎瞬时完成

我对Haskell的执行机制了解极少，仅知道运行时存在和程序结构大致对应的thunk图，除此之外认知非常有限。我猜测使用newtype时，Distribution的内存表示和Measure完全一致，本质就是原生列表；而data版本的每个Distribution值类似单字段记录，需要额外存储指向内部列表的指针，因此会产生更多内存分配开销。我希望确认这个猜测是否正确，以及该差异是否足以解释观测到的巨大性能差距。
此外我刚接触monad转换器栈，希望确认simpleDistribution中Let和Uniform分支的逻辑是否和基于walkTree的实现等价，以及如何验证二者的等价性。

程序简化过程 #

后续我根据评论反馈简化了程序，移除了所有和性能差异无关的逻辑，做了两处语义调整：

• 概率不再做归一化处理（计算结果不再符合概率语义）
• 移除了化简步骤
  但完整保留了程序的核心结构（可查看问题编辑历史获取未简化的原始程序）。

第二次更新中我做了进一步简化，将Distribution精简为带微小改动的列表monad，移除了所有概率相关逻辑、缩短了标识符命名，仍然观测到使用data定义时性能远差于newtype定义的现象，简化后的代码如下：

import Control.Monad (liftM2)
import Control.Monad.Trans (lift)
import Control.Monad.Reader (ReaderT, runReaderT)
import System.Environment (getArgs)
import Text.Read (readMaybe)

main = do
  args <- getArgs
  let dieCount = case map readMaybe args of Just n : _ -> n; _ -> 10
  let f = if ["s"] == (take 1 $ drop 1 $ args) then fast else slow
  print $ f dieCount

fast, slow :: Int -> P Integer
fast n = walkTree n
slow n = walkTree n `runReaderT` ()

walkTree 0 = uniform
walkTree n = liftM2 (+) (walkTree 0) (walkTree $ n - 1)

data P a = P [a] deriving Show
-- newtype P a = P [a] deriving Show

class Monad m => MonadP m where uniform :: m Integer
instance MonadP P where uniform = P [1, 1]
instance MonadP p => MonadP (ReaderT env p) where uniform = lift uniform

instance Functor P where fmap f (P pxs) = P $ fmap f pxs

instance Applicative P where
  pure x = P [x]
  (P pfs) <*> (P pxs) = P $ pfs <*> pxs

instance Monad P where
  (P pxs) >>= f = P $ do
    x <- pxs
    case f x of P fxs -> fxs

内容的提问来源于stack exchange，提问作者Jonas Kölker