初学haskell
最近学习 haskell ，在 Real world Haskell第三章 中有个作业，自己实现一个对list求长度的函数。这个问题还真不简单。
import Data.List
myLength0 :: [a] -> Integer
myLength0 [] = 0
myLength0 (a:x) = 1 + myLength0 x
h :: [a] -> Integer -> Integer
h [] l = l
h (x:xs) l = h xs $! (l + 1)
myLength1 :: [a] -> Integer
myLength1 x = h x 0
h2 :: [a] -> Integer -> Integer
h2 [] l = l
h2 (_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:xs) l = h xs $! (l + 128)
h2 (_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:xs) l = h xs $! (l + 64)
h2 (_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:xs) l = h xs $! (l + 32)
h2 (_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:_:xs) l = h xs $! (l + 16)
h2 (x:xs) l = h xs $! (l + 1)
myLength2 x = h2 x 0
myLength3 = foldl' (\acc x -> 1+acc) 0
我实现了这几个版本，和标准库的length比较了下，列表长度小不成问题，大了就很是问题了。
Prelude> :load exe1.hs
[1 of 1] Compiling Main ( exe1.hs, interpreted )
Ok, modules loaded: Main.
*Main> :set +s
*Main> length [1..100000]
100000
(0.03 secs, 17766888 bytes)
*Main> myLength0 [1..100000]
100000
(0.11 secs, 26769752 bytes)
*Main> myLength1 [1..100000]
100000
(0.08 secs, 29063752 bytes)
*Main> myLength2 [1..100000]
100000
(0.08 secs, 29064112 bytes)
*Main> myLength3 [1..100000]
100000
(0.03 secs, 13454440 bytes)
*Main> length [1..1000000]
1000000
(0.04 secs, 81961776 bytes)
*Main> myLength3 [1..1000000]
1000000
(0.16 secs, 114081320 bytes)
*Main> myLength2 [1..1000000]
1000000
(0.62 secs, 273896592 bytes)
*Main> myLength1 [1..1000000]
1000000
(0.63 secs, 273926760 bytes)
*Main> myLength0 [1..1000000]
1000000
(0.81 secs, 244863248 bytes)
*Main> length [1..10000000]
10000000
(0.26 secs, 802130896 bytes)
*Main> myLength3 [1..10000000]
10000000
(1.33 secs, 1122263992 bytes)
*Main> myLength2 [1..10000000]
10000000
(6.08 secs, 2722202704 bytes)
*Main> myLength1 [1..10000000]
10000000
(6.06 secs, 2722204664 bytes)
*Main> myLength0 [1..10000000]
10000000
(8.27 secs, 2427160704 bytes)
*Main> length [1..100000000]
100000000
(2.40 secs, 8002282840 bytes)
*Main> myLength3 [1..100000000]
100000000
(13.18 secs, 11202258200 bytes)
*Main> myLength2 [1..100000000]
100000000
(60.28 secs, 27202440376 bytes)
*Main> myLength1 [1..100000000]
100000000
(60.60 secs, 27201891056 bytes)
*Main> myLength0 [1..100000000]
*** Exception: stack overflow
已经解决的问题:
- 堆栈溢出 ( myLength0 )
- 不正确的尾递归优化
- 懒求值的副作用
没有解决的问题：
- 怎样才能和内置的length函数一样快？
参考