Текущее состояние длин

[deniok]

Померил тут, похоже про магические хэши не надо рассказывать. Тут 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)

Comments

[deni-ok.livejournal.com]

Да, надо на Char поменять.

[qnikst (from livejournal.com)]

Разведка докладывает, что поменяли на String (без указания типа), но с ним можно (если контекст в котором фунция задана можно менять и добавить OverloadedStrings):

{-# LANGUAGE OverloadedStrings #-}
instance Blah where
   fromString = undefined

?

[deni-ok.livejournal.com]

Это уже вне рамок стандарта. Ясно, что расширения могут менять стандартное поведение достаточно сильно.

[qnikst (from livejournal.com)]

(не очень серьёзно), а потом люди доучиваются, приходят в реальную жизнь и начинается, почему length (1,2) = 1 :)