tag:blogger.com,1999:blog-3773144963927368838.post4411942780958282428..comments2022-11-06T20:45:13.094-08:00Comments on hackerdashery: Tree Lists as a Default List Data StructureSteven Hazelhttp://www.blogger.com/profile/16132606068051543995noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3773144963927368838.post-66362527873601730192008-06-29T23:47:00.000-07:002008-06-29T23:47:00.000-07:00@rog:You can share structure in immutable trees, t...@rog:<BR/><BR/>You can share structure in immutable trees, too. The advantage over lists is that you can share more: common prefixes, for example.michaelwhttps://www.blogger.com/profile/10926144101079011297noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-54222678856694954182008-04-22T00:53:00.000-07:002008-04-22T00:53:00.000-07:00one characteristic of simple linked lists that you...one characteristic of simple linked lists that you didn't mention is that when they're immutable, you can share substructure (i.e. you've got an inverted tree, with potentially many list heads). this can save much space, and is also wonderful in a multithreaded environment, as you don't have to copy the data structure when passing it to another thread.rog peppehttps://www.blogger.com/profile/00839344798030831980noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-26086008174161527692008-04-17T00:15:00.000-07:002008-04-17T00:15:00.000-07:00When you use lists (eg in Scheme/Lisp) you most of...When you use lists (eg in Scheme/Lisp) you most often map a function on each element, i.e. you process the elements in sequence from the beginning the the end. Lists play well with recursive programming.<BR/><BR/>If you use lists and often end up looking up values, there is a slight chance you're do something wrong. The answer IMHO would not be to change the implementation of lists but (1) to not use lists or (2) to consider a change in your programming style.Unknownhttps://www.blogger.com/profile/05907222259020844445noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-51475075211339713532008-03-15T10:50:00.000-07:002008-03-15T10:50:00.000-07:00Although a Haskell compiler won't figure out that ...Although a Haskell compiler won't figure out that you're using lists uniquely and turn that into mutable update, it can (theoretically at least) compile certain list usages very efficiently via various fusion rules and other optimizations. For instance:<BR/><BR/> fac n = product [1..n]<BR/><BR/>could be fused and inlined into a loop with an accumulator. The work on stream fusion that Don Stewart and company have been doing, or Neil Mitchell's Supero optimizer are attempts to do this sort of stuff (although Supero is more general than just list fusion). In fact, you can see one of his papers for a somewhat more realistic example, where his optimizer turns:<BR/><BR/> print . length . words =<< getContents<BR/><BR/>into a loop that is competitive with the handwritten C equivalent.<BR/><BR/>Of course, setting individual values at random indices isn't the sort of operation that will be nicely fused. If that's really what you need to do, lists probably aren't the right structure.Dan Doelhttps://www.blogger.com/profile/16761291400347369301noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-68050589522795903812008-03-15T04:09:00.000-07:002008-03-15T04:09:00.000-07:00Steven: They don't, for the most part. Certainly n...Steven: <BR/><BR/>They don't, for the most part. Certainly not in instances like this. Most things converted to mutable state will be things like tail call optimisation and uniqueness types. Most of the time (like here!) converting to mutable state would require the compiler fundamentally change the algorithm you're using, which is both hard and fairly dangerous. It also probably loses a lot of the implementation efficiencies gained by using largely immutable datastructures.<BR/><BR/>(Incidentally, it's been pointed out to me that Scheme linked lists are in fact mutable, even if they're not normally used that way. Haskell ones are very decidedly not).<BR/><BR/>Also, seconding the use of finger trees. They're a nice structure.David R. MacIverhttps://www.blogger.com/profile/17522579015536144620noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-91912968453994377752008-03-14T15:43:00.000-07:002008-03-14T15:43:00.000-07:00The language I'm working on for my thesis project ...The language I'm working on for my thesis project will use tree lists as an implementation of the map type. It is an AVL tree with linked nodes.<BR/><BR/>http://www.cs.queensu.ca/~thurston/colm/<BR/><BR/>AdrianAdrian Thurstonhttps://www.blogger.com/profile/07166814808666322064noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-72059582257299663492008-03-14T15:02:00.000-07:002008-03-14T15:02:00.000-07:00Seems to me like 2-3 finger trees is something you...Seems to me like 2-3 finger trees is something you may want to look up. It supports fast access to either end, concatenation etc, and most other operations are O(log n)Sebastianhttps://www.blogger.com/profile/08546775571354068787noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-86797392695101147992008-03-14T15:00:00.000-07:002008-03-14T15:00:00.000-07:00David:Good point. Although, I always wonder to wh...David:<BR/><BR/>Good point. Although, I always wonder to what extent implementations of languages with immutable semantics are able to determine when a value will become unreachable, and implement value-replacements like immutable insertions using faster mutation-based methods. I don't know whether that kind of thing is ever done in practice.Steven Hazelhttps://www.blogger.com/profile/16132606068051543995noreply@blogger.comtag:blogger.com,1999:blog-3773144963927368838.post-69584318588127745762008-03-14T14:42:00.000-07:002008-03-14T14:42:00.000-07:00You might want to check your entry on linked lists...You might want to check your entry on linked lists. You say they're commonly used in Haskell and Scheme (which they are), but then go on to list performance characteristics corresponding to mutable linked lists... <BR/><BR/>With an immutable linked list you need to recreate the head of the list to insert or delete, so inserting or deleting from point k is an O(k) operation.<BR/><BR/>Keeping a zipper into a linked list corresponds a bit better to your notion of "iterator in the right place", where you have O(1) insert and delete at the current point, but that's not the same thing.David R. MacIverhttps://www.blogger.com/profile/17522579015536144620noreply@blogger.com