{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:19Z","timestamp":1779836719591,"version":"3.53.1"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[1997,7,1]],"date-time":"1997-07-01T00:00:00Z","timestamp":867715200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1997,7]]},"abstract":"<jats:p>A common solution to the problem of handling list indexing efficiently\n \n\nin a functional \n\nprogram is to build a binary tree. The tree has the given list as frontier\n and is of \n\nminimum height. Each internal node of the tree stores size information\n (actually, \n\nthe size of its left subtree) to direct the search for an element at a\n given position \n\nin the frontier. One application was considered in my previous pearl (Bird,\n 1997). \n\nThere are two complementary methods for building such a tree, both of which\n can \n\nbe implemented in linear time. One method is \u2018recursive\u2019, \n\nor top down, and works \n\nby splitting the list into two equal halves, recursively building a tree\n \n\nfor each half, and then combining the two results. The other method is\n \n\n\u2018iterative\u2019, or bottom up, \n\nand works by first creating a list of singleton trees, and then \n\nrepeatedly combining \n\nthe trees in pairs until just one tree remains. The two methods lead \n\nto different trees, \n\nbut in each case the result is a tree with smallest possible height.<\/jats:p>","DOI":"10.1017\/s0956796897002803","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T09:26:15Z","timestamp":1027761975000},"page":"441-445","source":"Crossref","is-referenced-by-count":4,"title":["FUNCTIONAL PEARL On building trees with minimum height"],"prefix":"10.1017","volume":"7","author":[{"given":"RICHARD S.","family":"BIRD","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[1997,7,1]]},"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796897002803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:35:28Z","timestamp":1779834928000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796897002803\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,7]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,7]]}},"alternative-id":["S0956796897002803"],"URL":"https:\/\/doi.org\/10.1017\/s0956796897002803","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,7]]}}}