初学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函数一样快?

参考