tag:blogger.com,1999:blog-6628985022531866193.post2420625269882444158..comments2024-02-12T17:37:05.629+00:00Comments on The OldWood Thing: A Tail of Two ListsChris Oldwoodhttp://www.blogger.com/profile/18183909440298909448noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6628985022531866193.post-51165248254579221372013-06-21T09:05:26.205+01:002013-06-21T09:05:26.205+01:00Perhaps more important is *why* the tail is "...Perhaps more important is *why* the tail is "the rest of the items". As you say this promotes a recursive approach to manipulating lists, although you can flatten it (or write a tail-recursive function - although subtly different tail there).<br /><br />Assuming immutable structures (as would be typical in a functional context) how do you construct a list in the first place? When you realise that each list is composed of a head and *another list* it's easy to see how a singly-linked list does not mutate the intermediate state but always adds to it.<br /><br />However the gains come when you start to share state. If list A has ten items and list B has eleven items, but the last nine are common, then there are only twelve items in total. That can be quite useful in a 64k system ;-)<br /><br />It gets a little more complex when you want to insert items in the middle (body?) of the list but the same principles apply (the shared tail is shorter and some items are duplicated - potentially much less memory efficient).<br /><br />This is not the only way the portions of immutable state can be shared and the whole area of persistent data types is quite fascinating - and we're using them (especially persistent maps and sets) to great effect on a large C++ project at the moment.Phil Nashhttps://www.blogger.com/profile/07697983218189410572noreply@blogger.com