7po3j-syaaa-aaaal-qbqea-cai.icp0.io
Open in
urlscan Pro
2a00:fb01:400:200:5000:eeff:fe3d:aa0d
Public Scan
URL:
https://7po3j-syaaa-aaaal-qbqea-cai.icp0.io/advanced-types/recursive-types.html
Submission: On December 24 via api from US — Scanned from CH
Submission: On December 24 via api from US — Scanned from CH
Form analysis 1 forms found in the DOM
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>Text Content
1. The Motoko Programming Language
2.
3. Part 1
4. 1. Introduction
❱
5. 1. 1.1. Getting Started
6. 2. Common Programming Concepts
❱
7. 1. 2.1. Variables
2. 2.2. Mutability
3. 2.3. Comments
4. 2.4. Types
❱
5. 1. 2.4.1. Tuples
2. 2.4.2. Records
3. 2.4.3. Variants
4. 2.4.4. Immutable Arrays
5. 2.4.5. Mutable Arrays
6. 2.5. Operators
❱
7. 1. 2.5.1. Numeric operators
2. 2.5.2. Relational operators
3. 2.5.3. Assignment operators
4. 2.5.4. Text concatenation
5. 2.5.5. Logical expressions
6. 2.5.6. Bitwise operators
7. 2.5.7. Operator precedence
8. 2.6. Pattern Matching
9. 2.7. Functions
10. 2.8. Options and Results
11. 2.9. Control Flow
❱
12. 1. 2.9.1. If Expression
2. 2.9.2. If Else Expression
3. 2.9.3. Switch Expression
13. 2.10. Objects and Classes
❱
14. 1. 2.10.1. Objects
2. 2.10.2. Classes
15. 2.11. Modules and Imports
16. 2.12. Assertions
8. 3. Internet Computer Programming Concepts
❱
9. 1. 3.1. Actors
❱
2. 1. 3.1.1. From Actor to Canister
2. 3.1.2. Canister Calls from Clients
3. 3.2. Principals and Authentication
4. 3.3. Async Data
❱
5. 1. 3.3.1. Shared Types
2. 3.3.2. Candid
6. 3.4. Basic Memory Persistence
❱
7. 1. 3.4.1. Upgrades
2. 3.4.2. Stable Variables
10.
11. Part 2
12. 4. Advanced Types
❱
13. 1. 4.1. Generic Types
2. 4.2. Subtyping
3. 4.3. Recursive Types
4. 4.4. Type Bounds
14. 5. The Base Library
❱
15. 1. 5.1. Primitive Types
❱
2. 1. 5.1.1. Bool
2. 5.1.2. Nat
3. 5.1.3. Int
4. 5.1.4. Float
5. 5.1.5. Principal
6. 5.1.6. Text
7. 5.1.7. Char
8. 5.1.8. Bounded Number Types
❱
9. 1. 5.1.8.1. Nat8
2. 5.1.8.2. Nat16
3. 5.1.8.3. Nat32
4. 5.1.8.4. Nat64
5. 5.1.8.5. Int8
6. 5.1.8.6. Int16
7. 5.1.8.7. Int32
8. 5.1.8.8. Int64
10. 5.1.9. Blob
3. 5.2. Utility Modules
❱
4. 1. 5.2.1. Iterators
2. 5.2.2. Hash
3. 5.2.3. Option
4. 5.2.4. Result
5. 5.2.5. Order
6. 5.2.6. Error
7. 5.2.7. Debug
5. 5.3. Data Structures
❱
6. 1. 5.3.1. Array
2. 5.3.2. List
3. 5.3.3. Buffer
4. 5.3.4. HashMap
5. 5.3.5. RBTree
7. 5.4. More Data Structures
8. 5.5. IC APIs
❱
9. 1. 5.5.1. Time
2. 5.5.2. Timer
3. 5.5.3. CertifiedData
4. 5.5.4. Random
5. 5.5.5. Experimental
16. 6. Advanced Concepts
❱
17. 1. 6.1. Async Programming
2. 6.2. Scalability
❱
3. 1. 6.2.1. Actor Classes
2. 6.2.2. Stable Storage
4. 6.3. System API's
❱
5. 1. 6.3.1. Message Inspection
2. 6.3.2. Timers
3. 6.3.3. Certified Variables
4. 6.3.4. Pre-upgrade and Post-upgrade
5. 6.3.5. Cryptographic Randomness
18.
19. Part 3
20. 7. Project Deployment
❱
21. 1. 7.1. Installing the SDK
2. 7.2. Local Deployment
3. 7.3. Canister Status
4. 7.4. Identities and PEM Files
5. 7.5. Cycles and ICP
6. 7.6. Cycles Wallet
7. 7.7. IC Deployment
22. 8. Common Internet Computer Canisters
❱
23. 1. 8.1. IC Management Canister
2. 8.2. ICP Ledger Canister
3. 8.3. Cycle Minting Canister
24. 9. Internet Computer Standards
❱
25. 1. 9.1. ICRC1
26. 10. Tokenized Comments Example
27.
28. APPENDIX
29. 11. TABLES
* Light
* Rust
* Coal
* Navy
* Ayu
THE MOTOKO PROGRAMMING LANGUAGE BOOK
RECURSIVE TYPES
Lets ask everyone's favorite AI about recursive types:
Q: How would you define recursive types?
ChatGPT: Recursive types are types that can contain values of the same type.
This self-referential structure allows for the creation of complex data
structures. Recursive types are commonly used in computer programming languages,
particularly in functional programming languages, to represent recursive data
structures such as trees or linked lists.
Wow! And since Motoko provides an implementation of a linked list, a common data
structure in programming languages, we will use that as an example.
LIST
Consider the following type declaration in the List module in the Base Library:
type List<T> = ?(T, List<T>);
A generic type List<T> is declared which takes one type parameter T. It is a
type alias for an option of a tuple with two elements.
The first element of the tuple is the type parameter T, which could take on any
type during the construction of a value of this List<T> type by providing a type
argument.
The second element of the tuple is List<T>. This is where the same type is used
recursively. The type List<T> contains a value of itself in its own definition.
This means that a List is a repeating pattern of elements. Each element is a
tuple that contains a value of type T and a reference to the tail List<T>. The
tail is just another list element of the same type with the next value and tail
for the next value and so on...
NULL LIST
Since our List<T> type is an option of a tuple, a value of type <List<T> could
be null as long as we initialize a value with a type argument for T:
let list : List<Nat> = null;
Our variable list has type List<Nat> (a list of Nat values) and happens to have
the value null.
THE 'TAIL' OF A LIST
The shortest list possible is a list with exactly one element. This means that
it does not refer to a tail for the next value, because there is no next value.
let list1 : List<Nat> = ?(0, null);
The second element in the tuple, which should be of type List<T> is set to null.
We use the null list as the second element of the tuple. This list could serve
as the last element of a larger list.
THE 'HEAD' OF A LIST
If we wanted to add another value to our list list1 we could just define another
value of type List<T> and have it point to list1 as its tail:
let list2 : List<Nat> = ?(1, list1);
list2 is now called the head of the list (the first element) and list1 is the
tail of our 2-element list.
We could repeat this process by adding another element and using list2 as the
tail. We could do this as many times as we like (within memory limits) and
construct a list of many values.
RECURSIVE FUNCTIONS
Suppose we have a list bigList with many elements. This means we are presented
with a head of a list, which is a value of type <List<T>.
There several possibilities for this head value:
* The head value bigList could be the null list and in that case it would not
contain any values of type T.
* Another possibility is that the head value bigList has a value of type T but
does not refer to a tail, making it a single element list, which could be the
last element of a larger list.
* Another possibility is that the head value bigList contains one value of type
T and a tail, which is another value of type List<T>.
These possibilities are used in the last<T> function of the List module. This
function is used to retrieve the last element of a given list:
func last<T>(l : List<T>) : ?T {
switch l {
case null { null };
case (?(x, null)) { ?x };
case (?(_, t)) { last<T>(t) };
};
};
We have a generic function List<T> with one type parameter T. It takes one
argument l of type List<T>, which is going to be a head of some list.
If the function finds a last element, it returns an option of the value ?T
within it. If there is no last element it returns null.
In the function body, we switch on the argument l : List<T> and are presented
with the three possibilities described above.
* In the case that l is the null list, we return null because there would not
be a last element.
* In the case that l is a list element ?(x, null), then we are dealing with the
last element because there is not tail. We bind the name x to that last value
by pattern matching and return an option ?x of that value as is required by
our function signature.
* In the case that l is a list element ?(_, t), then there is a tail with a
next value. We use the wildcard _ because we don't care about the value in
this element, because it is not the last value. We do care about the tail for
which we bind the name t. We now use the function last<T> recursively by
calling it again inside itself and provide the tail t as the argument:
last<T>(t). The function is called again receiving a list which it now sees
as a head that it can switch on again and so on until we find the last
element. Pretty cool, if you ask me!