Home>

### recursion - about recursive data types

What do you mean (;;)

The recursive data type A * of the alphabet set A is defined as follows:

Basic case
A * contains the empty character λ

Configuration case
If a ∈ A, s ∈ A * then the pair ∈ A *

The recursive definition is the definition of the starting point (in the case of a question, the basic case "A * contains the empty character λ") and the definition of how to extend it. (In the case of a question, it consists of a configuration case "a ∈ A * if a ∈ A, s ∈ A *").

Suppose that the alphabet set A contains three alphabets 'A', 'B', and 'C'.
I will represent it as ['A', 'B', 'C'].

And then
-Set A * containing only λ is a recursive data type of set A (base case): A * can be expressed as [λ].

-The set [λ, 'A'] with 'A' added to it includes the pair<λ, 'A'>(configuration case).
・ Furthermore, in the set [λ, 'A', 'B'] with 'B' added, the pairs<λ, 'A'>and<λ, 'B'>and<'A', 'B'>And<λ, 'A', 'B'>are included.
So the recursive data type A * can be extended and reconstructed,
[λ]
[λ, 'A']
[λ, 'B']
[λ, 'C']
[λ, 'A', 'B']
[λ, 'A', 'C']
[λ, 'B', 'C']
[λ, 'A', 'B', 'C']
Can be either.