NDLI: Church Encoding of Data Types Considered Harmful for Implementations: Functional Pearl

Please wait, while we are loading the content...

Type-Directed Elaboration of Quasiquotations: A High-Level Syntax for Low-Level Reflection

Combining Shared State with Speculative Parallelism in a Functional Language

An Efficient Type- and Control-Flow Analysis for System F

Church Encoding of Data Types Considered Harmful for Implementations: Functional Pearl

Really Natural Linear Indexed Type Checking

Editlets: type-based, client-side editors for iTasks

Task Oriented Programming with Purely Compositional Interactive Scalable Vector Graphics

Stream Processing for Embedded Domain Specific Languages

Parametric lenses: change notification for bidirectional lenses

Towards native higher-order remote procedure calls

Church Encoding of Data Types Considered Harmful for Implementations: Functional Pearl

Content Provider	ACM Digital Library
Author	Koopman, Pieter Jansen, Jan Martin Plasmeijer, Rinus
Abstract	From the λ-calculus it is known how to represent (recursive) data structures by ordinary λ-terms. Based on this idea one can represent algebraic data types in a functional programming language by higher-order functions. Using this encoding we only have to implement functions to achieve an implementation of the functional language with data structures. In this paper we compare the famous Church encoding of data types with the less familiar Scott and Parigot encodings. We show that one can use the encoding of data types by functions in a Hindley-Milner typed language by adding a single constructor for each data type. In an untyped context, like an efficient implementation, this constructor can be omitted. By collecting the basic operations of a data type in a type constructor class and providing instances for the various encodings, these encodings can co-exist in a single program. By changing the instance of this class we can execute the same algorithm in a different encoding. This makes it easier to compare the encodings with each other. We show that in the Church encoding selectors of constructors yielding the recursive type, like the tail of a list, have an undesirable strictness in the spine of the data structure. The Scott and Parigot encodings do not hamper lazy evaluation in any way. The evaluation of the recursive spine by the Church encoding makes the complexity of these destructors linear time. The same destructors in the Scott and the Parigot encoding requires only constant time. Moreover, the Church encoding has problems with sharing reduction results of selectors. The Parigot encoding is a combination of the Scott and Church encoding. Hence we might expect that it combines the best of both worlds, but in practice it does not offer any advantage over the Scott encoding.
Starting Page	1
Ending Page	12
Page Count	12
File Format	PDF
ISBN	9781450332842
DOI	10.1145/2746325.2746330
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-10-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Data types Church numbers Scott encoding Implementation Parigot encoding
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in