Opérations sur les tableaux

Instructions

Implémente les opérations de base sur les listes.

Dans les langages fonctionnels, les opérations sur les listes telles que length, map et reduce sont très courantes. Implémente une série d'opérations de base sur les listes, sans utiliser les fonctions existantes.

Le nombre et les noms exacts des opérations à implémenter dépendent du parcours, afin d'éviter les conflits avec des noms existants, mais les opérations générales que tu implémenteras incluent :

• append (étant donné deux listes, ajouter tous les éléments de la seconde liste à la fin de la première) ;
• concatenate (étant donné une série de listes, combiner tous les éléments de toutes les listes en une seule liste aplatie) ;
• filter (étant donné un prédicat et une liste, renvoyer la liste de tous les éléments pour lesquels predicate(item) est vrai) ;
• length (étant donné une liste, renvoyer le nombre total d'éléments qu'elle contient) ;
• map (étant donné une fonction et une liste, renvoyer la liste des résultats de l'application de function(item) à tous les éléments) ;
• foldl (étant donné une fonction, une liste et un accumulateur initial, replier (réduire) chaque élément dans l'accumulateur en partant de la gauche) ;
• foldr (étant donné une fonction, une liste et un accumulateur initial, replier (réduire) chaque élément dans l'accumulateur en partant de la droite) ;
• reverse (étant donné une liste, renvoyer une liste contenant tous les éléments d'origine, mais dans l'ordre inverse).

Remarque : l'ordre dans lequel les arguments sont passés aux fonctions de repli (foldl, foldr) est important.

Implémentation

Tu vas devoir utiliser le polymorphisme de paramètres d'Odin (plus souvent appelé génériques) pour cet exercice. Si tu n'as jamais vu cette fonctionnalité auparavant, voici un rapide récapitulatif pour te lancer.

Le polymorphisme de paramètres est une fonctionnalité des langages de programmation qui permet aux programmeurs d'être moins précis (plus génériques, d'où le nom) sur les types utilisés dans leur code, tout en conservant la sûreté du typage. Évidemment, cela n'a de sens que pour les langages fortement typés comme Odin.

Commençons par un exemple. Imaginons que tu veuilles incrémenter tous les éléments d'un tableau d'une valeur fixe, un problème assez simple.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Et si maintenant tu as aussi besoin de la même fonctionnalité pour les nombres à virgule flottante ?

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Et ensuite pour les entiers non signés, les flottants 32 bits, et ainsi de suite ?

Tu te retrouves vite avec une multitude de procédures qui font exactement la même chose, mais sur des types différents. Si tu dois un jour mettre à jour la logique, tu dois alors t'assurer de le faire pour toutes les variantes, ce qui peut représenter beaucoup de travail de maintenance. L'autre inconvénient, c'est que tu dois donner un nom différent à chacune des procédures, car Odin ne prend pas en charge la surcharge implicite de procédures (tu peux toujours utiliser la surcharge explicite, mais c'est une histoire pour un autre exercice).

Odin, étant un langage pratique, offre une solution grâce au polymorphisme de paramètres. Tant que le compilateur peut déterminer le type d'un paramètre au moment de la compilation, tu peux lui donner un nom générique, comme T. Réécrivons notre procédure ci-dessus :

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

Remarque que l'on a remplacé toutes les annotations de type (int ou f64) par T, et que la première occurrence de T est précédée d'un signe dollar ($T). Le type $T indique au compilateur Odin que le nom T est un nom générique pour le type, à remplacer par le nom réel lors de la compilation. Et, comme le compilateur connaît maintenant le type générique T, les occurrences suivantes de ce même type n'ont plus qu'à être marquées avec le nom de type choisi (T).

Tu peux maintenant écrire du code comme :

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

Dans la première instruction, le compilateur Odin identifiera le type du premier paramètre ([]int) au type du paramètre générique ([]$T), en déduira que T = int, puis compilera une version où toutes les instances suivantes de T sont remplacées par int (équivalent à la version spécialisée incr_array_int() ci-dessus). Si tu omettais le signe dollar dans la définition du premier paramètre, le compilateur aurait cherché un type nommé T dans le paquet courant et dans la liste des imports, et aurait très probablement renvoyé une erreur de compilation Error: Undeclared name: T.

La deuxième instruction fonctionne exactement comme la première, si ce n'est que le compilateur identifie T comme f64.

Il est d'usage de donner aux types génériques des noms d'une seule lettre (T et E sont souvent utilisés).

Tu devrais maintenant en savoir assez sur le polymorphisme de paramètres, aussi appelé types génériques, pour t'attaquer à l'exercice Opérations sur les listes.