![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Текущее состояние длин
Mar. 7th, 2016 05:09 pmПомерил тут, похоже про магические хэши не надо рассказывать. Тут length' - текущая реализация из GHC, length0 - трех?летней давности:
{-# LANGUAGE MagicHash #-}
module Length where
import GHC.Prim
import GHC.Exts (Int(I#))
import Data.List
length0 :: [a] -> Int
length0 l = len l 0#
where
len :: [a] -> Int# -> Int
len [] a# = I# a#
len (_:xs) a# = len xs (a# +# 1#)
length' :: [a] -> Int
length' xs = lenAcc xs 0 where
lenAcc [] n = n
lenAcc (_:ys) n = lenAcc ys (n+1)
length'' :: [a] -> Int
length'' = foldl' (const . succ) 0
length''' :: [a] -> Int
length''' [] = 0
length''' (_:xs) = 1 + length''' xs
Результаты
C:\Users\deniok\Documents\Haskell>ghc -O2 Length.hs [1 of 1] Compiling Length ( Length.hs, Length.o ) C:\Users\deniok\Documents\Haskell>ghci Length.hs GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Ok, modules loaded: Length. > :set +s > length [1..100000000] 100000000 (1.56 secs, 8,014,793,624 bytes) > length0 [1..100000000] 100000000 (1.55 secs, 8,002,029,776 bytes) > length' [1..100000000] 100000000 (1.55 secs, 8,001,085,992 bytes) > length'' [1..100000000] 100000000 (2.00 secs, 9,601,216,960 bytes) > length''' [1..100000000] *** Exception: stack overflow > > length [1..50000000] 50000000 (0.86 secs, 3,938,034,240 bytes) > length0 [1..50000000] 50000000 (0.84 secs, 3,937,631,120 bytes) > length' [1..50000000] 50000000 (0.84 secs, 4,240,225,000 bytes) > length'' [1..50000000] 50000000 (1.08 secs, 4,845,463,912 bytes) > length''' [1..50000000] 50000000 (1.34 secs, 4,420,898,928 bytes)
