\ndata structure: it’s superimposed on it.<\/p>\n
So, as I said: cons-cell style lists are ubiquitous and beloved by To illustrate: here’s the number list example from yesterdays post. The The point of this is that you’ve still got your cons list. All of the As an alert commenter pointed out, I left out one really important thing in my earlier post about finger trees. That’s what I get for trying to write when I’m sick :-). Seriously, this is a point that’s implied by the post as it stands, but never explicitly stated – and since it’s really important, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[83,35],"tags":[],"class_list":["post-776","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-markccs-errors"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-cw","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/776","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=776"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/776\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=776"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=776"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=776"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nfunctional and non-functional programmers. In finger trees, you’re
\nnot<\/em> getting rid of them. The point of finger trees is to let
\nyou keep<\/em> the convenient data structure, with its basic operations
\nand properties intact, and to augment<\/em> it with a tree that lets you search it efficiently.<\/p>\n
\noriginal list is at the bottom, with green pointers representing the
\noriginal cons-list next-pointers. The monoid-annotated tree is on top,
\nwith red pointers. The combination of the original list with the
\nmonoid annotated tree is a finger tree.<\/p>\n![\"counted-finger-tree-list.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_388.png?resize=546%2C278\")
<\/div>\n
\nbeautiful recursive\/iterative algorithms that walk the list continue to
\nwork exactly<\/em> the way that they would in the traditional cons-list: for code that walks the list, the fact that there are finger-tree pointers
\nsitting on top of the list is irrelevant – and, in fact, completely invisible. For algorithms that want to search the list, the tree structure is there,
\nand allows the searches to be performed much more quickly than they could be on
\nthe traditional list. The superposition of those two structures is the
\ngenius of the finger tree.<\/p>\n","protected":false},"excerpt":{"rendered":"