Factorial (AWK)
From LiteratePrograms
Factorial as a hylomorphism
A hylomorphism is the functional programmer's way to say that he is doing some data processing with an intermediate data structure. His theory may involve mumbling something about Functors and Algebraic Data Types, but his practice will follow the well-worn steps of early 1970's COBOL coders confronted with a structure clash (as advocated by Jackson Structured Programming).
The hylomorphism has two components: an anamorphism (cf. analyze, anabolic), which divides a complex structure into simpler parts (and has as its hardware parallel the demux), and a catamorphism (cf. concatenate, catabolic), which builds up a complex structure out of simpler parts (and has as its hardware parallel the mux).
<<fact.awk>>= #!/bin/awk -f {c=catamorphism;anamorphism}
Question: Are there programs that can't be expressed as hylomorphisms?
the anamorphism
Given a natural number N as input, we form the suffix list of its Peano representation.
<<anamorphism>>= while($1){print $1--|c}close(c)
Note that instead of generating an intermediate data structure, we use a pipe to connect the two processes. In the late 1990's, functional programmers called this deforestation, and used it to reduce pressure on their garbage collectors. In the late 1960's, dp programmers called this an online algorithm, and used it to avoid waiting several minutes while their tapes rewound.
the catamorphism
We take as input an EOF-terminated, linefeed-separated, stream of naturals. The factorial is formed simply by evaluating this input under the following map:
<<catamorphism>>= "awk 'BEGIN{n=1}{n*=$1}END{print n}'"
| Download code |