Haskell 的无限列表, 底层实现是怎样的?

题叶
  • 17.3k
回复
阅读 4.5k
4 个回答

惰性求值的底层其实是借助了thunk。粗浅的解释就是一个求值用的函数和它的自由变量环境的结合。
每一个表达式在其值被需要之前,总是先存储为一个thunk,一旦其值必须要被求解出来,就强迫执行求值过程。
比如说,如果有这样的列表:

list :: [Integer]
list = [1..]

它首先会被实现为对系统函数enumFrom的调用,调用的结果类似这样:

enumFrom :: Integer -> [Integer]
enumFrom n = n : enumFrom (n + 1)

list = enumFrom 1
     = 1 : enumFrom 2
     = 1 : 2 : enumFrom 3
     = 1 : 2 : 3 : enumFrom 4
     -- on and on ...

其中每个enumFrom的调用都会被实现为一个thunk。
我们以take 5 list为例。
take函数用(:)进行模式匹配,类似于:

take :: Int -> [a] -> [a]
take 0 _ = []
take n (x:xs) = x : take (n-1) xs
take _ _ = error "Invalid call of take."

需要对列表进行模式匹配时,将要求从thunk中匹配一个(:)运算符(构造器),这时thunk求值一层,从list展开成1 : thunk2,模式匹配成功,取出了1。take函数会要求进一步匹配,新thunk(即thunk2)也会被求值,又产生新的thunk。当thunk中的值不再需要时,就不会进一步求值了。这样,无穷的求解步骤就被拆分开来,总是用一个thunk来表达无穷的部分,就不会耗尽内存了。

惰性计算(Lazy Evaluation)是haskell的一大特点之一。无限列表也是Lazy Evaluation的一种表现。它的底层实现感觉上没那么重要吧。了解概念就OK了,反正它很快,O(1)的时间复杂度、空间复杂度。

delay不是一个函数,而是一个宏(macro),它的具体实现,可以看一下R5RS标准后面的附录,记得是有delay的实现的

scheme(define-syntax mydelay
  (syntax-rules (define)
    ((mydelay (define expr ...))
     (error "can't delay define -- macro mydelay"))
    ((mydelay expr ...)
     (cons 'promise (lambda () (begin expr ...))))))

(define-syntax myforce
  (syntax-rules ()
    ((myforce delayed-expr)
     (if (and (pair? delayed-expr) (eq? 'promise (car delayed-expr)))
       ((cdr delayed-expr))
       (error "not a promise")))))

我写的一个很简陋的实现,就是把一个表达式用一个函数封装一下……

sqd
  • 1
新手上路,请多包涵
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏