Lists Hylomorphism (computer science)

in previous example (written in haskell, purely functional programming language) can seen function, applied given valid input, generate linear call tree isomorphic list. example, given n = 5 produce following:

factorial 5 = 5 * (factorial 4) = 120
factorial 4 = 4 * (factorial 3) = 24
factorial 3 = 3 * (factorial 2) = 6
factorial 2 = 2 * (factorial 1) = 2
factorial 1 = 1 * (factorial 0) = 1
factorial 0 = 1

in example, anamorphic part of process generation of call tree isomorphic list [1, 1, 2, 3, 4, 5]. catamorphism, then, calculation of product of elements of list. thus, in notation given above, factorial function may written




factorial

=
[

[
(
1
,
×
)
,
(
g
,
p
)
]

]


{\displaystyle {\text{factorial}}=[\![(1,\times ),(g,p)]\!]}





g
 
n
=
(
n
,
n
−
1
)


{\displaystyle g\ n=(n,n-1)}

,



p
 
n
=
(
n
=
0
)


{\displaystyle p\ n=(n=0)}

.