{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:56:01Z","timestamp":1776891361265,"version":"3.51.2"},"reference-count":40,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"5-6","license":[{"start":{"date-parts":[[2008,9,2]],"date-time":"2008-09-02T00:00:00Z","timestamp":1220313600000},"content-version":"unspecified","delay-in-days":1,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This paper introduces a pattern for almost compositional functions over recursive data types, and over families of mutually recursive data types. Here \u201calmost compositional\u201d means that for all of the constructors in the type(s), except a limited number of them, the result of the function depends only on the constructor and the results of calling the function on the constructor's arguments. The pattern consists of a generic part constructed once for each data type or family of data types, and a task-specific part. The generic part contains the code for the predictable compositional cases, leaving the interesting work to the task-specific part. Examples of the pattern are given, implemented in dependent type theory with inductive families, in Haskell with generalized algebraic data types and rank-2 polymorphism, and in Java using a variant of the Visitor design pattern. The relationships to the \u201cScrap Your Boilerplate\u201d approach to generic programming, and to general tree types in dependent type theory, are investigated by reimplementing our operations using those frameworks.<\/jats:p>","DOI":"10.1017\/s0956796808006898","type":"journal-article","created":{"date-parts":[[2008,9,2]],"date-time":"2008-09-02T04:05:57Z","timestamp":1220328357000},"page":"567-598","source":"Crossref","is-referenced-by-count":8,"title":["A pattern for almost compositional functions"],"prefix":"10.46298","volume":"18","author":[{"given":"BJ\u00d6RN","family":"BRINGERT","sequence":"first","affiliation":[]},{"given":"AARNE","family":"RANTA","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,9,2]]},"reference":[{"key":"S0956796808006898_ref13","volume-title":"Workshop on Mathematically-Structured Functional Programming (MSFP 2006)","author":"Gibbons","year":"2006"},{"key":"S0956796808006898_ref7","unstructured":"Coquand Catarina & Coquand Thierry . (September 1999) Structured type theory. Workshop on Logical Frameworks and Meta-languages (LFM'99), Paris, France."},{"key":"S0956796808006898_ref31","unstructured":"Peyton Jones , Simon. (August 2007). The GHC Commentary. http:\/\/hackage.haskell.org\/trac\/ghc\/wiki\/Commentary."},{"key":"S0956796808006898_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796807006326"},{"key":"S0956796808006898_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018349"},{"key":"S0956796808006898_ref4","unstructured":"Augustsson Lennart & Petersson Kent . (1994) Silly type families. http:\/\/www.cs.pdx.edu\/sheard\/papers\/silly.pdf."},{"key":"S0956796808006898_ref40","unstructured":"Winstanley Noel , Wallace Malcom & Meacham John . (2007) The DrIFT homepage. http:\/\/repetae.net\/john\/computer\/haskell\/DrIFT\/."},{"key":"S0956796808006898_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567077"},{"key":"S0956796808006898_ref29","first-page":"1","article-title":"The Haskell 98 language","volume":"13","author":"Peyton","year":"2003","journal-title":"J. Funct. Program"},{"key":"S0956796808006898_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211308"},{"key":"S0956796808006898_ref22","volume-title":"Intuitionistic Type Theory","author":"Martin-L\u00f6f","year":"1984"},{"key":"S0956796808006898_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504302"},{"key":"S0956796808006898_ref30","first-page":"149","article-title":"The Haskell 98 libraries","volume":"13","author":"Peyton","year":"2003","journal-title":"J. Funct. Program"},{"key":"S0956796808006898_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796803004738"},{"key":"S0956796808006898_ref26","unstructured":"Nordstr\u00f6m Bengt , Petersson Kent & Smith Jan M. (1990) Programming in Martin-L\u00f6f's Type Theory: An Introduction. USA: Oxford University Press. http:\/\/www.cs.chalmers.se\/Cs\/Research\/Logic\/book\/."},{"key":"S0956796808006898_ref5","unstructured":"Bracha Gilad , Odersky Martin , Stoutamire David & Wadler Philip . (1998) Making the future safe for the past: Adding genericity to the java programming language. In ACM Symposium on Object Oriented Programming: Systems, Languages, and Applications (OOPSLA), Vancouver, BC, Chambers, Craig (ed.), pp. 183\u2013200."},{"key":"S0956796808006898_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_7"},{"key":"S0956796808006898_ref11","volume-title":"Design Patterns: Elements of Reusable Object-Oriented Software","author":"Gamma","year":"1995"},{"key":"S0956796808006898_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811432"},{"key":"S0956796808006898_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263763"},{"key":"S0956796808006898_ref14","volume-title":"Java Language Specification","author":"Gosling","year":"2005"},{"key":"S0956796808006898_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"S0956796808006898_ref19","volume-title":"Proceedings of the ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI)","author":"L\u00e4mmel","year":"2003"},{"key":"S0956796808006898_ref33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0956796806006034","article-title":"Practical type inference for arbitrary-rank types","volume":"17","author":"Peyton","year":"2007","journal-title":"J. Funct. Program"},{"key":"S0956796808006898_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1159803.1159811"},{"key":"S0956796808006898_ref37","first-page":"1","volume-title":"Haskell'02: Proceedings of the ACM SIGPLAN workshop on Haskell","author":"Sheard","year":"2002"},{"key":"S0956796808006898_ref27","unstructured":"Norell Ulf . (2007) Towards a Practical Programming Language Based on Dependent Type Theory. Ph.D. Thesis, Department of Computer Science and Engineering, Chalmers University of Technology, G\u00f6teborg, Sweden."},{"key":"S0956796808006898_ref36","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680300488X"},{"key":"S0956796808006898_ref16","first-page":"13","volume-title":"Lecture Notes in Computer Science","author":"Hinze","year":"2006"},{"key":"S0956796808006898_ref9","unstructured":"Forsberg Markus . (September 2007) Three Tools for Language Processing: BNF Converter, Functional Morphology, and Extract. Ph.D. Thesis, G\u00f6teborg University and Chalmers University of Technology."},{"key":"S0956796808006898_ref6","unstructured":"Bringert Bj\u00f6rn . (2006) The Transfer programming language. http:\/\/www.cs.chalmers.se\/Cs\/Research\/Language-technology\/GF\/doc\/transfer.html."},{"key":"S0956796808006898_ref20","volume-title":"The Boost Graph Library: User Guide and Reference Manual","author":"Lee","year":"2002"},{"key":"S0956796808006898_ref10","unstructured":"Forsberg Markus & Ranta Aarne . (2006) BNF Converter homepage. http:\/\/www.cs.chalmers.se\/markus\/BNFC\/."},{"key":"S0956796808006898_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811449"},{"key":"S0956796808006898_ref18","first-page":"97","volume-title":"Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text","author":"Jones","year":"1995"},{"key":"S0956796808006898_ref12","volume-title":"Spring School on Datatype-Generic Programming","author":"Gibbons","year":"2007"},{"key":"S0956796808006898_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1016850.1016882"},{"key":"S0956796808006898_ref25","unstructured":"Mitchell Neil & O'Rear Stefan . (August 2007) Data Derive: A User Manual. http:\/\/www.cs.york.ac.uk\/fp\/darcs\/derive\/derive.htm."},{"key":"S0956796808006898_ref1","volume-title":"Modern C++ Design: Generic Programming and Design Patterns Applied","author":"Alexandrescu","year":"2001"},{"key":"S0956796808006898_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005605"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796808006898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:19:11Z","timestamp":1776889151000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796808006898\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":40,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["S0956796808006898"],"URL":"https:\/\/doi.org\/10.1017\/s0956796808006898","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9]]}}}