Example:List as a function

From CS2800 wiki
(Redirected from List)

Many data structures can be represented by functions with a specialized domain or codomain. For example, one could represent a list of natural numbers as a function [math]ℓ : \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1,\dots,n\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]; the kth element of the list would be [math]ℓ(k) [/math].

For example, the list [5,7,1] would be represented as the function [math]f : \{0,1,2\} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php?title=Natural_numbers&action=edit&redlink=1}{\mathbb{N}} [/math] given by [math]f(0):=5 [/math], [math]f(1):=7 [/math], and [math]f(2):=1 [/math].

Similarly, we can think of a sequence [math](x_0, x_1, x_2, \dots) [/math] of elements of [math]X [/math] as a function [math]s : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} X [/math]; [math]x_i [/math] is just shorthand for [math]s(i) [/math].