Array 数组

数组🚚

任何编程语言中的数据结构都是必不可少的，几乎每个程序都需要将数据存储和访问数据结构。 

数据结构有很多不同的形式，每种形式都有自己的优点和缺点，没有完美的数据结构（即使有些数据结构比其他数据结构更常用），给定任务的最佳数据结构取决于具体情况和您的优先级 。

We have already played with Array, but today we'll see exactly how they are created and many useful functions to use with them.

An array is a fixed-length data structure, once an array of a specified size is created you cannot increase the capacity expect by creating a completely new array. This means that at the time the code will run, it will always know what is the size of the array. (This is not the case for all datastructures)
Accessing an element in an array is extremely simple, you only need to request the value at a specific index.

数组是一种固定长度的数据结构，一旦创建了指定大小的数组，就无法通过创建全新的数组来增加预期的容量。 这意味着在代码运行时，它将始终知道数组的大小是多少。 （并非所有数据结构都是如此）

访问数组中的元素非常简单，您只需要请求特定索引处的值即可。

let array : [Nat] = [10, 3, 4, 5];
let a : Nat = array[3]; // 5

You can access tothe size of an array using .size().

let array : [Nat] = [1, 3 , 4];
let size : Nat = array.size() // 3

🕵️ Deeply understanding why accessing an element in an array is so efficient involves explaining how the computer manages memory, this is out of scope for this lesson but I'll try to explain it in simple terms : if we know the size of an array when the code is compiled, we can allocate the exact memory for it, remember the memoy location of the first value in the array and write all other values in the memory locations directly following the location of the first value.

Then if we want to access any element in the array we just need to look at the location of the first element and eventually jump to the right memory location by taking into account the index of the element we are trying to access.

In Motoko, by default arrays are immutable (like variables). This means once the array is created you can only read the values inside but cannot write.

You can create mutable arrays but you need to use the keyword var.

let array_1 : [Nat] = [1, 2, 3]; // immutable

let array_2: [var Nat] = [1, 2, 3]; // mutable

array_1[1] := 0; // ⛔️ impossible to reassign values of an immutable array.

array_2[1] := 0; // ✅ valid reassignment in a mutable array.

Optional type 

In Motoko there is a special value called null.
This value represents the absence of a result, this is useful if you want one of your function to indicate that it has no specific return value. The type of null is Null (this type contains only one value).

Let's say you want to create a function named index_of_one that takes an array of type [Nat] and returns the first index such that the value at that index is equal to 1.
You also want this function to return null if no matching index was found.

在 Motoko 中，有一个称为 null 的特殊值。

该值表示不存在结果，如果您希望某个函数表明它没有特定的返回值，则此值非常有用。 null 的类型为 Null（该类型仅包含一个值）。

假设您要创建一个名为 index_of_one 的函数，该函数接受 [Nat] 类型的数组并返回第一个索引，使得该索引处的值等于 1。

如果未找到匹配的索引，您还希望此函数返回 null。

actor {
    public func index_of_one(array : [Nat]) : async Nat {
        for((number,index) in array.vals()){
            if(number == 1) {
                return index;
            }
        };
        return null;
    };
};

This declaration is not valid because null is not a type Nat 😕
Trying to deploy this code would result in the following error.

type error [M0050], literal of type
  Null
does not have expected type
  Nat

We need a way to explain to Motoko that the value returned can be either a Nat or null.

Luckily there is a notation exactly for that, it's called the optional type : ?T.
In our case we would use ?Nat because we are returning Nat or null.

We can rewrite our actor using our new type.

actor {
    public func index_of_one(array : [Nat]) : async ?Nat {
        for((number,index) in array.vals()){
            if(number == 1) {
                return index;
            }
        };
        return null;
    };
};

Sometimes in your code you will need to handle those optional values, you can do so with a switch expression.

import Nat "mo:base/Nat";
actor {
    public func null_or_nat(n : ?Nat) : async Text {
        switch(n){
            // Case where n is null
            case(null) {
                return ("The argument is null");
            };
            // Case where n is a nat
            case(?something){
                return ("The argument is : " # Nat.toText(something));
            };
        };
    };
};

You can deploy this actor and try those commands.

dfx canister call day_3 null_or_nat '(opt 4)'
("The argument is : 4")

🕵️ Notice again the difference between Candid and Motoko.
Here we have to use the Candid syntax opt 4 whereas in Motoko we could just write ?4.

dfx canister call day_3 null_or_nat '(null)'
("The argument is null")

☢️ It's important to understand that the type ?Nat and Nat are really different.
If a function is expecting a value of type Nat as parameter and it receives a value of type ?Nat it will not appreciate. 😠

Take a loot at something we shouldn't do, we'll use again the same code from the previous example but without the switch expression.

import Nat "mo:base/Nat";
actor {
    public func null_or_nat(n : ?Nat) : async Text {
        return ("The argument is : " # Nat.toText(something)); ⛔️ what is the type of something at this point?
    };
};

This code will not compile because the function toText is expecting a parameter of type Nat as we can see in the documentation.

Some functions accept optional types, but not this one.
I hope you now appreciate the importance of switch / case.

Generic type 👤

I have briefly introduced the concept of generic type when we introduced the optional type with the notation ?T. Let's dive into it.

The generic type T allow us to write more general code, that can work with different types and be reused.

Let's say we want to write a function called is_array_size_even that returns a Bool indicating if the size of the array is even or not.
We could write something like this

public func is_array_size_even(array : [Nat]) : async Bool {
    let size = array.size();
    if(size % 2 == 0){
        return true;
    } else {
        return false;
    };
};

This function is valid, but it only works if our array is filled with Nat. What about an array with Text values inside ?

• An quick and dirty solution would be to create a lot of different functions for each type of array we want to use : _is_array_size_even_nat _is_array_size_even_text _is_array_size_even_char ... I hope you agree that this solution sucks.

• A better solution is to use the generic notation : T. This basically allow us to create one generic function that we can reuse for all the types available in Motoko.

public func is_array_size_even<T>(array : [T]) : async Bool {
    let size = array.size();
    if(size % 2 == 0){
        return true;
    } else {
        return false;
    };
};

T means "whatever type you want" and [T] means "whatever type you want as long as it's an array".

🕵️ Notice the following the name of the function. It means that this function now depends on the type of T.
If you want to use the array_size function you'll need to specify for which type you are going to use it !

func is_array_size_even<T>(array : [T]) : Bool {
    let size = array.size();
    if(size % 2 == 0){
        return true;
    } else {
        return false;
    };
};

let array : [Nat] = [1,2,3,4];
let bool : Boolean = is_array_size_even<Nat>(array); // I indicate to the compiler which type I'm gonna use the function on.

We've used T to represent the generic type but you will also see A or B or C being used in the documentation, this doesn't change anything.

Higher order functions 🏋️‍♀️

So far, we've only seen functions taking simple arguments (Nat, Text, Char...) but functions can also take other functions as arguments, such functions are called higher order function.

The Array module contains several higher order function, those are really powerful and useful methods so I'll present some of them.

到目前为止，程序中只看到了接受简单参数（Nat、Text、Char...）的函数，但函数也可以接受其他函数作为参数，此类函数称为高阶函数。

数组模块包含几个高阶函数，这些都是非常强大且有用的方法，因此下面将介绍其中的一些方法。

• Find : 该函数采用两个参数 [A] 一个数组和一个函数，该函数采用 A 类型的值并返回 Bool。 （f 称为predicate谓词）。

此函数返回predicate谓词为 true 的第一个值。

import Array "mo:base/Array";
actor {
    let f = func (n : Nat) : Bool {
        if (n > 10) {
            return true
        } else {
            return false
        };
    };

    public func mystere(array : [Nat]) : async ?Nat {
        return(Array.find<Nat>(array, f));
    };

};

注：此代码示例使用了程序一直在讨论的 3 个概念：Optional类型、Generic类型和高阶函数。 

🤔 What do you think mystere([1,4,5,18,0,2,3]) will return ?

• Filter : This function also takes an array [A] and a predicate f and returns a new array [A] where only values that validate the predicate are kept.

We can even reuse the same predicate as in the previous example. ♻️

import Array "mo:base/Array";
actor {
    let f = func (n : Nat) : Bool {
        if (n > 10) {
            return true
        } else {
            return false
        };
    };

    public func surprise(array : [Nat]) : async ?Nat {
        return(Array.filter<Nat>(array, f));
    };
};

🤔 What do you think surprise([1, 23, 4, 25, 12]) will return ?

• Map : This function (again) takes an array [A] but this time f is a function taking a value of type A and returning a value of type B. This function simply apply the function f to all elements in the array and returns the new array.

import Array "mo:base/Array";
actor {
    let f = func (n : Nat) : Nat {
        return(n + 1);
    };

    public func riddle(array : [Nat]) : async [Nat] {
        return(Array.map<Nat, Nat>(array, f));
    };
};

🤔 What do you think riddle([0, 0, 0, 0]) will return ?

awesome-motoko/lessons/day_3/README.md at main · motoko-bootcamp/awesome-motoko