Thumbnail
Access Restriction
Subscribed

Author Morihata, Akimasa ♦ Mu, Shin-Cheng
Source ACM Digital Library
Content type Audio ♦ Text
Publisher Association for Computing Machinery (ACM)
File Format PDF ♦ MP4
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Program derivation ♦ Third list homomorphism theorem
Abstract The third list-homomorphism theorem says that a function is a list homomorphism if it can be described as an instance of both a foldr and a foldl. We prove a dual theorem for unfolds and generalise both theorems to trees: if a function generating a list can be described both as an unfoldr and an unfoldl, the list can be generated from the middle, and a function that processes or builds a tree both upwards and downwards may independently process/build a subtree and its one-hole context. The point-free, relational formalism helps to reveal the beautiful symmetry hidden in the theorem.
Description Affiliation: Academia Sinica, Taipei, Taiwan Roc (Mu, Shin-Cheng) || Tohoku University, Sendai, Japan (Morihata, Akimasa)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 46
Issue Number 9
Page Count 7
Starting Page 385
Ending Page 391


Source: ACM Digital Library