Discussion :

[cibirsk]

Bonjour,

Je n'arrive pas à comprendre la différence entre paradigme de programmation fonctionnelle et impérative.

Par exemple pour un programme calculant le chiffre minimum d'une liste.

Ce que j'ai compris pour l'impératif:
- utilisation d'une boucle
- changement de valeur d'une variable en comparant un élément de la liste avec celui déjà présent dans la variable
- retour de la valeur de la variable quand toute la liste est parcouru

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
longueur=len(s)
              if longueur == 0 : print ("La liste est vide")
              else :
mini = s[0]
i=1
while i < longeuur :
ifs[i]<mini: mini=s[i]
                      i = i+1
                  print ("Le minimum est : ", mini)

Ce que j'ai compris pour la fonctionnelle
-pas de boucle
-utilisation de la récursivité (une fonction s'appelle elle-même)

L'exemple des fonctions factorielles m'aide à comprendre le principe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8

n! = n x (n-1)!
si n=0 => 0

3! = 3×(3−1)!=3×2!
= 3×2×(2−1)!=3×2×1!
= 3×2×1×(1−1)!=3×2×1×0! = 3×2×1×1=6

En revanche je ne comprends pas l'utilisation de ce principe pour trouver le minimum de la liste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec minimum s = match s with
              |[]   -> failwith "La liste est vide"
              |[x]  -> x
              |e::r -> let mini = minimum r in
                       if mini > e then e
                                   else mini

Quel est le mécanisme qui fait parcourir la liste à la ligne 4 ?


sources:
http://www.irem.univ-bpclermont.fr/I...paradigmes.pdf
https://caml.inria.fr/distrib/books/llc.pdf


PS: Je débute en programmation et j'ai choisi Scheme pour commencer.
Je m'aperçois que j'ai de grosses lacunes en mathématiques et notions informatiques de base.

Merci

[SpiceGuid]

Désolé, je ne crois pas tellement à la vertu de l'exemple pour répondre au fond de la question.

Disons que la plus importante différence est la suivante :

• Avec l'impératif, pour le comprendre, il faut exécuter le code mentalement.
• Avec le fonctionnel c'est déclaratif, il n'y pas besoin de simuler mentalement quoi que ce soit. Conséquence : il y a notoirement moins de bugs.

On pourrait caricaturer en disant qu'avec l'impératif on sait ce qu'on fait mais on ne sait pas ce que ça vaut et avec le fonctionnel on sait ce que ça vaut sans s'inquiéter de comment ça le fait.

[cibirsk]

Avec le fonctionnel c'est déclaratif, il n'y pas besoin de simuler mentalement quoi que ce soit.

Désolé, je n'arrive pas à comprendre.

[Grogro]

[*]Avec le fonctionnel c'est déclaratif, il n'y pas besoin de simuler mentalement quoi que ce soit. Conséquence : il y a notoirement moins de bugs.

Quels sont les vrais points forts du paradigme fonctionnel, particulièrement quand on vient de l'impératif et de l'orienté objet comme un peu nous tous ?

[SpiceGuid]

Moi aussi je viens de l'impératif, modulaire et/ou orienté objet.

Il ne faut pas vous laisser abuser par de soit disant avantages décisifs.
N'ayez aucun complexe. Essayez le fonctionnel. Et abandonnez-le si ça ne vous convient pas.
Après tout c'est comme ça que vous faites (et que je fais) avec n'importe quelle autre techno.

Si vous ne comprenez pas, au moins votre cœur doit vous dire s'il faut insister ou laisser tomber.
S'il faut insister vous trouverez des personnes pour vous aider.
Sinon l'éco-système autour de l'orienté objet est largement assez vaste pour épancher toute votre soif d'apprendre.

[byjav]

Tout d’abord, j’aimerais discuter l’exemple de la factorielle et illustrer qu’il est assez facile de transformer une boucle dans une fonction récursive.

Cette méthode naïve de calculer la factorielle est inefficace au niveau de la pile des appels. Le programme doit garder dans sa mémoire une chaîne des multiplication de longeur n.

Par contre, une réalisation impérative est tout à fait économe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
def fact(n):
    f = 1
    i = 1
    while i <= n:
        f = f * i
        i = i + 1
    return f

Grâce à la boucle, l’usage de la mémoire et la pile des appels ne dépendent pas de n.

Comme s’est « la bonne solution », il doit avoir une façon de l’exprimer en termes de la programmation fonctionnelle. En effet, c’est possible.

L’idée générale est que le corps de la boucle devient le corps d’une fonction récursive et les paramètres de la boucle deviennent les arguments de la fonction.

Ici on a trois paramètres : l’argument n, le compteur u et l’accumulateur f. Alors, la fonction auxiliaire est de la forme fact_helper(n, i, f). Comment doit-elle fonctionner ? Si le compteur i est égal a n, on renvoie la valeur de l’accumulateur f. Sinon, on passe à « l’itération suivante », c’est-à-dire, on appelle la fonction fact_helper de nouveau en augmentant la valeur du compteur et en multipliant l’accumulateur par i. Comme quoi, on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def fact_helper(n, i, f):
    if i = n:
        return n
    else
        return fact_helper(n, i + 1, f * i)

et le code de la factorielle devient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
def fact(n):
    fact_helper(n, 1, 1)

On peut s'assurer facilement que ça marche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
fact(4) = fact_helper(4, 1, 1)
        = fact_helper(4, 2, 1)
        = fact_helper(4, 3, 2)
        = fact_helper(4, 4, 6)
        = fact_helper(4, 5, 24) = 24

Alors, il n’y a pas d’affectations, ce ne sont que les mathématiques, mais « la dynamique » des arguments de fact_helper est identique à celle des paramètres de la boucle.

Tout de même, ce n’est pas exactement la même chose. Par exemple, j’ai le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

print fact(4)

Le raisonnement du programme « fonctionnel » est comme ça :

Je calcule fact(4) pour l’afficher.
Je calcule fact_helper(4, 1, 1) pour calculer fact(4) pour l’afficher.
Je calcule fact_helper(4, 2, 1) pour calculer fact_helper(4, 1, 1) pour calculer fact(4) pour l’afficher.
Je calcule fact_helper(4, 3, 2) pour calculer fact_helper(4, 2, 1) pour calculer fact_helper(4, 1, 1) pour calculer fact(4) pour l’afficher.
Je calcule fact_helper(4, 4, 6) pour calculer fact_helper(4, 3, 2) pour calculer fact_helper(4, 2, 1) pour calculer fact_helper(4, 1, 1) pour calculer fact(4) pour l’afficher.
Je calcule fact_helper(4, 5, 24) pour calculer fact_helper(4, 4, 6) pour calculer fact_helper(4, 3, 2) pour calculer fact_helper(4, 2, 1) pour calculer fact_helper(4, 1, 1) pour calculer fact(4) pour l’afficher.

C’est-à-dire, la pile des appelle est toujours là. Elle croît avec n, donc il semble que la nouvelle solution fonctionnelle est inefficace comparé à la boucle.

Mais il y a une observation subtile (ou un « hack ») qui permet de sortir de l’ornière. Si la valeur de f(x, y, z) est égale à celle de g(u, v, w), on peut oublier qu’on calcule f(x, y, z) et calculer g(u, v, w) à ça place. Ça se dit « l’optimisation de la récursion terminale ». Avec cette optimisation,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

print fact(4)

correspond à la raisonnement

Je calcule fact(4) pour l’afficher.
Je calcule fact_helper(4, 1, 1) pour l’afficher.
Je calcule fact_helper(4, 2, 1) pour l’afficher.
Je calcule fact_helper(4, 3, 2) pour l’afficher.
Je calcule fact_helper(4, 4, 6) pour l’afficher.
Je calcule fact_helper(4, 5, 24) pour l’afficher.
J’affiche 24.

Maintenant c’est autant efficace que la boucle !

Par contre, la récursion dans la formule n! = n(n-1)! n’est pas terminale:

Je calcule 3! pour le multiplier par 4 et obtenir 4!.
Je calcule 2! pour le multiplier par 3 pour le multiplier par 4 et obtenir 4!.
...
Rien ne peut être oublié.

La programmation fonctionnelle suppose il n’y a pas de boucles, alors l’optimisation de la récursion terminale est obligatoire pour écrire un code efficace. C’est le cas en Scheme, par exemple, où cette récursion est exigée par le standard. Par contre, le standard de Common Lisp n’exige pas cette optimisation, alors on se content plutôt des boucles (à vrai dire, elles sont excellentes en Common Lisp).

Un autre exemple classique, les nombres de Fibonacci, manifeste que la récursivité naturelle peut être très inefficace du point de vue du calcul:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) = ((fib(2) + fib(1)) + 1) + (1 + 1)

Comme on calcule fib(4) et fib(3) indépendamment, on calcule fib(3) deux fois. Plus grande est n, pire devient la situation. Pour efficacité, on doit recourir à une boucle ou la récursivité terminale équivalent à une boucle. C’est un bon exercice.

[byjav]

Maintenant, aux listes.

Tout d’abord, il faut distinguer entre listes et tableaux. Le temps nécessaire pour accéder un élément d’un tableau ne dépend pas de l’element (grosso modo, il suffit d’additioner l’offset à l’addresse de base du tableau). Mathématiquement, le temps d’accès est O(1). Par contre, pour accéder l’élément numéro i d’une liste, il faut parcourir tous les éléments précédents à partir de la tête. Évidemment, plus grand est i, plus c’est cher. Mathématiquement, le temps d’accès est O(i). Donc, on préfère travailler avec la tête d’une liste ou la décomposer en tête et queue (la liste des éléments à partir du deuxième). Par contre, une boucle de la forme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for (i = 0; i < n; ++i) {
    liste[i]

est très inefficace, car on revient à la tête à chaque itération, donc le parcours total est 1 + 2 + .. + n = n(n+1)/n = O(n^2) au lieu de n. Si une langue supporte des listes et des boucles, il y a, peut-être, une boucle de la forme « for elt in liste ».

Alors, une recherche impérative du minimum d’une liste peut être comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def min_list(list):
    if is_empty(list):
        return fail
    else
        mini = head(list)
        t = tail(list)
        while not(is_empty(t)):
            mini = min(mini, head(t))
            t = tail(t)
    return mini

À propos, la programmation fonctionnelle nous apprend à séparer l’IO du calcul, ce qui est une bonne idée même en paradigme impérative. Donc, ici la fonction renvoie le résultat au lieu de l’afficher.

Voici le code équivalent avec récursion terminale :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
def min_list_helper(list, mini, t):
    if is_empty(t):
        return mini
    else
        return min_list_helper(list, min(mini, head(t)), tail(t))

def min_list(list):
    if is_empty(list):
        return fail
    else:
        return min_list_helper(list, head(list), tail(list))

En Scheme (trois versions):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(define (min-list-1 lst)
  (define (helper lst mini tail)
    (if (null? tail)
        mini
        (helper lst (min mini (car tail)) (cdr tail))))
  (if (null? lst)
      (error "Empty list.")
      (helper lst (car lst) (cdr lst))))

(define (min-list-2 lst)
  (if (null? lst)
      (error "Empty list.")
      (letrec ((helper (lambda (mini tail)
                         (if (null? tail)
                             mini
                             (helper (min mini (car tail)) (cdr tail))))))
        (helper (car lst) (cdr lst)))))

(define (min-list-3 lst)
  (if (null? lst)
      (error "Empty list.")
      (let loop ((mini (car lst))
                 (tail (cdr lst)))
        (if (null? tail)
            mini
            (loop (min mini (car tail)) (cdr tail))))))

La première version correspond au pseudocode au-dessus, j’ai seulement déplacé la definition de la fonction auxiliaire en dedans de la fonction principale. La deuxième version emploie letrec. Dans la première version, le premier argument de la fonction auxiliaire était toujours le même, alors dans la deuxième version, je l’ai éliminé. La troisième version avec « let nommé » (named let) réalise la même idée d’une façon plus concise.

D’ailleurs, des modèles typiques de la récursivité sont abstraits en forme de certaines fonctions d’ordre supérieur. Par exemple, ici le modèle est comme suit : on a un accumulateur (mini), une fonction (min) et une liste (la queue de lst) et on appelle la fonction aux éléments successifs de la liste, en substituant toujours l’accumulateur par la valeur retournée par la fonction. C’est un algorithme que l’on peut exprimer par une fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

fold fonction accumulateur-initial liste

En scheme, une telle fonction est définie dans SRFI-1. Donc, on a encore une version :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
(define (min-list-4 lst)
  (if (null? lst)
      (error "Empty list.")
      (fold min (car lst) (cdr lst))))

L’utilité des fonctions d’ordre supérieur dépasse la programmation fonctionnelle. En effet, on peut en bénificier même en C, en manipulant des fonctions sur des fonctions. Cependant, en C il ne s’agit que des fonctions prédéfinies (pendant la compilation). Les fonctions d’ordre supérieur sont bien plus pratiques dans des langages qui permettent la création des fonctions dans le run time et qui supportent les clôtures.

[byjav]

Quant’à l’algorithme original, il n’est pas bon pour les listes, mais il marche pour les tableaux. En voici une version récursive :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def boucle(longeur, i, mini):
    if i >= longeur:
        return mini
    elseif s[i] < mini:
        return boucle(longeur, i + 1, s[i])
    else
        return boucle(longeur, i + 1, mini)

def min_array(s):
    longeur = len(s)
    if longeur == 0:
        return fail
    else
        return boucle(longeur, 0, s[1])

À propos, si « boucle » est définie à l’intérieur de min_array, on peut supprimer l’argument longeur, car il est toujours le même. En Scheme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
(define (min-vector s)
  (let ((longeur (vector-length s)))
   (if (zero? longeur)
       (error "Empty vector.")
       (letrec ((boucle (lambda (i mini)
                          (cond ((>= i longeur) mini)
                                ((< (vector-ref s i) mini) (boucle (+ i 1) (vector-ref s i)))
                                (else (boucle (+ i 1) mini))))))
         (boucle 1 (vector-ref s 0))))))

[Jedai]

En revanche je ne comprends pas l'utilisation de ce principe pour trouver le minimum de la liste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec minimum s = match s with
              |[]   -> failwith "La liste est vide"
              |[x]  -> x
              |e::r -> let mini = minimum r in
                       if mini > e then e
                                   else mini

Quel est le mécanisme qui fait parcourir la liste à la ligne 4 ?

Ce n'est pas la bonne question à poser, comme l'indique Spiceguid, le fonctionnel est déclaratif, il fonctionne en décrivant ce qui est et doit être obtenu, pas en donnant des ordres successifs à la machine.

Voici une autre version du même code mais légèrement réécrite en Haskell et commentée:

Code haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
minimum []     = error "Une liste vide n'a pas de minimum !"
minimum [x]    = x                   -- si une liste a un seul élément, c'est son minimum
minimum (x:xs) = min x (minimum xs)  -- sinon le minimum est le plus petit entre le premier élément et le minimum du reste de la liste

Note comme dans la troisième ligne je ne me préoccupe pas de comment la liste est parcourue, je décris juste le minimum d'une liste à plusieurs éléments, je me permets même d'utiliser le mot que je suis en train de définir (minimum) pour ce faire, sans s'inquiéter de comment ou de s'il marche. A partir du moment où les cas de bases sont traités et où je récurse sur un cas plus petit (ici le reste de la liste), la magie de l'induction me permet de garantir que le tout marchera.

Est-ce là la meilleure façon de faire ? Ça dépend ! De toi, de ton expérience, du problème à traiter, de l'efficacité en temps ou espace souhaitée, etc. Il est néanmoins certain que cette méthode conduit à moins de bugs une fois maîtrisée.

Bonne exploration du paradigme fonctionnel (je te conseille Haskell si tu as libre choix de ton langage d'introduction et que tu n'es pas allergique à l'anglais).
--
Jedaï

[byjav]

Est-ce là la meilleure façon de faire ?

Claire et inefficace. C’est toujours comme ça, la récursivité naïve.

[Jedai]

Claire et inefficace. C’est toujours comme ça, la récursivité naïve.

Non, la récursivité naïve est souvent efficace ou du moins suffisamment efficace pour que son énorme avantage en terme de lisibilité l'emporte sur les mineurs gains d'efficacité d'une implémentation plus complexe...
Par exemple pour calculer la profondeur d'un arbre, la "meilleure" solution est :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
data Tree a = Leaf a | Branch [Tree a]
 
depth :: Tree a -> Int
depth (Leaf _) = 1
depth (Branch ts) = 1 + maximum (map depth ts)

Bien sûr il y a de nombreux cas où passer à une récursion terminale est préférable (quoique beaucoup moins dans un langage à évaluation paresseuse comme Haskell) mais il est souvent encore préférable de simplement se passer de récursion directe et d'utiliser une fonction d'ordre supérieure. Par exemple ici notre fonction minimum était clairement égale à :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

minimum = foldr1 min

qui place un "min" entre chaque élément (fold) et commence son calcul par la droite/fin de la liste (r) et ne marche que sur des listes non-vides (1)
foldr1 min [1,2,3] == min 1 (min 2 3)

Et dès lors qu'on sait que min n'est pas une fonction paresseuse (sur les nombres usuels en tout cas...) on voit qu'il est préférable d'utiliser :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

minimum = foldl1' min

qui fait de même mais à partir de la gauche (l) et strictement (').
Et il est impossible de faire plus efficace sur une liste.

--
Jedaï

[byjav]

Ben, il est difficile de définir strictement ce que veulent dire « souvent » et « suffisamment efficace », alors je ne vais pas en discuter. Au moins, il me semble que O(n) au lieu de O(1) (par exemple, au niveau de la pile des appelles) sans aucune compensation, c’est un signe de l’inefficacité, et je doute que la paresse aide beaucoup. Quoique je puisse moi-même songer à des situations où l’efficacité est beaucoup moins importante que la lisibilité: par exemple, en écrivant des macros en lisp.

Quant au fold, je suis d’accord que c’est la bonne version, surtout parce que c’est une abstraction adéquate. Et du fait qu’elle adéquate, elle permet une réalisation efficace (il y a une récursion terminale en dedans).

[Jedai]

Ben, il est difficile de définir strictement ce que veulent dire « souvent » et « suffisamment efficace », alors je ne vais pas en discuter. Au moins, il me semble que O(n) au lieu de O(1) (par exemple, au niveau de la pile des appelles) sans aucune compensation, c’est un signe de l’inefficacité, et je doute que la paresse aide beaucoup. Quoique je puisse moi-même songer à des situations où l’efficacité est beaucoup moins importante que la lisibilité: par exemple, en écrivant des macros en lisp.

« souvent » peut être difficile à définir précisément mais « toujours » est beaucoup plus simple... Et c'est ce à quoi je réagissais dans ta réponse. Quant aux situations où la récursivité non-terminale est suffisante même dans un cadre d'évaluation strict, ce sont les cas où tu maintiendrais une pile ou une structure équivalente dans ton algorithme impératif de toute façon (comme dans ma fonction depth, où le O(depth) en complexité spatiale est inévitable s'il n'y a pas de lien vers le parent dans les nœuds).

Avec l'évaluation paresseuse, la distinction est beaucoup plus floue et il est souvent possible d'écrire un programme dans un style récursif direct sans récursion terminale mais dont la complexité spatiale sera tout de même O(1). Par exemple :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
-- le "ou" booléen classique
[||) :: Bool -> Bool -> Bool
True || _ = True
False || b = b
 
-- appliqué à une liste de booléens
or :: [Bool] -> Bool
or [] = False
or (b::bs) = b || or bs

Ce code semble être une récursion naïve mais grâce à l'évaluation paresseuse de (||), la fonction or() fonctionne en espace O(1) (et s'arrête au premier True rencontré dans la liste). Bien sûr on écrirait ceci "foldr (||) False" plutôt que d'utiliser une récursion directe mais foldr fait exactement ce que tu vois ci-dessus.

--
Jedaï

[byjav]

Bon, c’etait une exagération, je demande pardon.

Quant à l’exemple avec le « ou »: supposons qu’on veut calculer

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

or [True, True, True]

Ça donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

True || or [True, True]

Est-ce que je comprends correctement que la part

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

True ||

est immédiatement simplifié conformément à la définition de || et que l’on arrive à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

or [True, True]

?

[Jedai]

Tout à fait :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

False || n'importe quoi

sera "remplacé" par :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

n'importe quoi

n'occupant donc pas plus d'espace sur la pile.

Tandis que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

True || ...

n'évaluera jamais le deuxième opérande et donnera directement True (donc or n'a pas besoin de parcourir le reste de la liste).

On dit que (||) est paresseux en son deuxième opérande, c'est d'ailleurs le comportement normal de (||) dans la plupart des langages, simplement en Haskell (||) est une fonction comme une autre et tu peux donc la passer à foldr ((||) est d'ailleurs défini normalement dans une bibliothèque en Haskell au lieu d'être un mot clé). Tu peux reproduire ce genre de comportement avec des macros pour certains cas mais c'est moins flexible et par exemple pour les structures de données c'est moins pratique (en Haskell il est assez courant d'avoir des structures infinies).

Conceptuellement tu peux voir ça comme un système de réécriture (où l'on peut avoir des pointeurs, la liste n'est pas dupliquée !) mais si tu veux mieux comprendre la base du système tu peux aller voir du côté de la STG-Machine.

--
Jedaï

[cibirsk]

@ byjav: je te remercie d'avoir pris du temps pour me répondre mais ce que tu écris me dépasse complètement.
L'optimisation de récursion terminale, c'est encore un peu dur à saisir pour le moment.
Je suis sûr que je retrouverai ce concept plus tard.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

minimum (x:xs) = min x (minimum xs)  -- sinon le minimum est le plus petit entre le premier élément et le minimum du reste de la liste

Note comme dans la troisième ligne je ne me préoccupe pas de comment la liste est parcourue, je décris juste le minimum d'une liste à plusieurs éléments, je me permets même d'utiliser le mot que je suis en train de définir (minimum) pour ce faire, sans s'inquiéter de comment ou de s'il marche. A partir du moment où les cas de bases sont traités et où je récurse sur un cas plus petit (ici le reste de la liste), la magie de l'induction me permet de garantir que le tout marchera.

Bonne exploration du paradigme fonctionnel (je te conseille Haskell si tu as libre choix de ton langage d'introduction et que tu n'es pas allergique à l'anglais).
--
Jedaï

"Magie" est le mot juste. Je travaille actuellement avec un livre sur le Scheme et cela m'a permis d'accepter le principe à défaut de le comprendre vraiment.
Cela m'évoque la théorie de la "boîte noire" en psychologie où les entrées (stimulations, environnement...) et les sorties (réactions, comportement) sont connues mais où le fonctionnement interne est totalement inconnu.

le fonctionnel est déclaratif, il fonctionne en décrivant ce qui est et doit être obtenu, pas en donnant des ordres successifs à la machine.

J'ai déjà entendu ce genre de phrase