Haskell学习笔记: Unboxed Type

上文 提出了一个问题,怎么能写一个length函数能和内置的length一样快?最简单的办法莫过于 查看GHC源代码 了。

库里面的源代码确是这个样子:

-- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.
-- It is an instance of the more general 'Data.List.genericLength',
-- the result type of which may be any kind of number.
length                  :: [a] -> Int
length l                =  len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

搞不明白 Int# 是什么玩意,到处查,最后发现上面那个Slide里面有提示(自己太粗心了):

All those # marks are for “unboxed types”, which are faster but not asymptotically

然后再Google, 就可以找到 unboxed type的定义 。于是自己可以写一个和库里面源代码一模一样的 length:

{-# MagicHash #-}

import Data.List
import GHC.Prim
import GHC.Exts

length1                  :: [a] -> Int
length1 l                =  len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

用GHCi测试了下,速度比上回的好,但还是不如内置的length,这是为什么?我猜大约是编译器优化吧。