Re:In Lisp, should lists be replaced with trees?
by p4bl0 on Monday May 16, 2011 @08:04AM
(#2552280)
Also, Guy Steele is one of the two inventor of Scheme. So it may not be directly lisp related, but it definitely is indirectly lisp related ;-).
I think that's directly related. The answer to the question "Why should we replace our lists?" is that you can avoid known failure cases with lists at a relatively small price in complexity and memory in the worst case, and sometimes get big gains. Singly-linked lists are not suitable for a concurrent world and functional programming really needs to stop putting lists on a pedestal and writing them into their very syntax. There's actually other problems they cause, too, but the concurrent problem is a real killer, because you can not just program your way around it, you need a fundamentally different data structure.
http://vimeo.com/6624203 Conc lists as video. Titled Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful (Guy Steele)
[1] http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...