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,这是为什么?我猜大约是编译器优化吧。