Ici, pour vous montrer, j'ai utilisé :
beartype.Notez que ce n'est absolument pas nécessaire, c'était juste pour montrer que ce genre d'annotations peut aider à passer de Caml à Python.
In [1]:
def successeur(i : int) -> int:
assert isinstance(i, int), "Erreur : i = {} doit etre entier.".format(i)
assert i >= 0, "Erreur : i = {} doit etre >= 0.".format(i)
return i + 1
In [2]:
successeur(3)
successeur(2 * 2)
successeur(2.5)
Out[2]:
Out[2]:
In [4]:
def produit3(x, y, z):
return x * y * z
produit3_2 = lambda x, y, z: x * y * z
produit3_3 = lambda x: lambda y: lambda z: x * y * z
In [5]:
produit3(1, 2, 3)
produit3_2(1, 2, 3)
produit3_3(1)(2) # lambda z : 1 * 2 * z
f = produit3_3(1)(2) # lambda z : 1 * 2 * z
f(3)
produit3_3(1)(2)(3)
Out[5]:
Out[5]:
Out[5]:
Out[5]:
Out[5]:
In [6]:
def exercice6(n : int) -> None:
for i in range(1, n + 1):
print(i)
for i in range(n, 0, -1):
print(i)
In [7]:
exercice6(4)
In [8]:
def factorielle(n : int) -> int:
if n <= 0:
return 0
elif n == 1:
return 1
else:
return n * factorielle(n - 1)
In [10]:
for i in range(8):
print("{}! = {:>5}".format(i, factorielle(i)))
# Note : ce {:>5} signifie que l'affichage utilise au moins
# 5 caractères, pour avoir un joli alignement :
In [1]:
def pgcd(x : int, y : int, log: bool=False) -> int:
if log: print("x = {:>7}, y = {:>7}".format(x, y))
assert x >= 0 and y >= 0
if y == 1:
return 1
elif y == x or y == 0:
return x
if x < y:
return pgcd(x, y % x, log=log)
else:
return pgcd(y, x % y, log=log)
In [2]:
pgcd(10, 5)
Out[2]:
On peut faire des essais pour afficher notre calcul de PGCD, sur des entiers aléatoires entre $1$ et $100$.
Pour se rassurer, on peut chercher dans la bibliothèque standard, à partir de Python 3.6 il y a la fonction math.gcd pour calculer le PGCD, sinon fractions.gcd ou encore dans le module (non standard) SymPy sympy.gcd.
In [15]:
try:
from math import gcd
except ImportError:
try:
from fractions import gcd
except ImportError:
from sympy import gcd
from random import randint
for _ in range(10):
x = randint(1, 100)
y = randint(1, 100)
d = pgcd(x, y)
print("{:>3} ^ {:>3} = {:>3}".format(x, y, d))
assert d == gcd(x, y), "Erreur : mauvais calcul de pgcd(x={}, y={}) = {}, alors qu'il devrait etre = {}.".format(x, y, pgcd(x, y), gcd(x, y))
In [17]:
def fibonacci(n : int) -> int:
assert n >= 0
if n == 0 or n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
Dans IPython (ou Jupyter) on peut facilement mesurer le temps (moyen) d'exécution d'une fonction sur une entrée donnée, avec la macro %timeit.
In [18]:
%timeit fibonacci(35)
Dans Python, on peut faire pareil avec timeit() du module timeit.
In [21]:
from timeit import timeit
timeit("fibonacci(35)", globals=globals())
Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.
In [77]:
def fibonacci_lin(n : int) -> int:
un, uns = 1, 1
for _ in range(n):
un, uns = uns, un + uns
return un
On peut vérifier que cette deuxième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.
In [79]:
for i in range(10):
assert fibonacci(i) == fibonacci_lin(i)
In [80]:
%timeit fibonacci_lin(35)
Voilà la différence.
In [44]:
from types import FunctionType # inutile, juste pour faire joli
# première version, f : type x -> type x (simple)
def itere(f : FunctionType, n : int) -> FunctionType:
def fn(x):
for _ in range(n):
x = f(x)
return x
return fn
In [45]:
itere(lambda x: x + 1, 10)(1)
Out[45]:
In [119]:
# deuxième version, f : tuple -> tuple (simple)
def itere2(f : FunctionType, n : int) -> FunctionType:
def fn(*args):
for _ in range(n):
if isinstance(args, tuple):
args = f(*args)
else:
args = f(args)
if isinstance(args, tuple) and len(args) == 1:
return args[0]
else:
return args
return fn
In [132]:
def plusun(x):
return x + 1
itere2(plusun, 10)(1)
def foisdeux(x, y):
return x * 2, y * 2
itere2(foisdeux, 10)(1, 2)
Out[132]:
Out[132]:
In [144]:
def hanoi(x : str, y : str, z : str, n : int) -> None:
def hanoiaux(orig : str, dest : str, inter : str, n : int):
if n == 0:
return 0
c1 = hanoiaux(orig, inter, dest, n - 1)
print("{} -> {}".format(orig, dest))
c2 = hanoiaux(inter, dest, orig, n - 1)
return c1 + 1 + c2
return hanoiaux(x, z, y, n)
In [145]:
hanoi("T1", "T2", "T3", 1)
Out[145]:
In [146]:
hanoi("T1", "T2", "T3", 2)
Out[146]:
In [148]:
hanoi("T1", "T2", "T3", 5) # 31 = 2^5 - 1
Out[148]:
In [152]:
def concatene(liste1 : list, liste2 : list) -> list:
# return liste1 + liste2 # solution facile
n1, n2 = len(liste1), len(liste2)
res = []
for i in range(n1 + n2):
if i < n1:
res.append(liste1[i])
else:
res.append(liste2[i - n1])
return res
In [153]:
concatene([1, 2, 3], [4, 5])
Out[153]:
In [163]:
from types import FunctionType
def applique(f : FunctionType, liste : list) -> list:
res = [f(x) for x in liste] # solution facile
res = map(f, liste) # encore plus facile
# en itérant la liste :
res = [ ] # tableau vide
for x in liste:
res.append(f(x))
# en itérant ses valeurs :
res = [ ] # tableau
for i in range(len(liste)):
res.append(f(liste[i]))
return res
In [164]:
applique(lambda x : x + 1, [1, 2, 3])
Out[164]:
In [165]:
def liste_carree(liste : list) -> list:
return applique(lambda x: x**2, liste)
In [167]:
liste_carree([1, 2, 3])
Out[167]:
In [10]:
def miroir_quad(liste : list) -> list:
# pour le faire naïvement en Python
# on fait une concaténation de liste
if liste:
return miroir_quad(liste[1:]) + [ liste[0] ]
else:
return []
def miroir_lin(liste : list) -> list:
return [liste[-i] for i in range(1, len(liste) + 1)]
In [11]:
miroir_quad([1, 2, 3])
Out[11]:
In [12]:
%timeit miroir_quad(list(range(1000)))
In [13]:
miroir_lin([1, 2, 3])
Out[13]:
In [14]:
%timeit miroir_lin(list(range(1000)))
In [186]:
def insertion_dans_liste_triee(entiers : list, x : int) -> list:
i = 0
while i < len(entiers) and entiers[i] < x:
i += 1
return entiers[:i] + [x] + entiers[i:]
In [187]:
insertion_dans_liste_triee([1, 2, 5, 6], 4)
Out[187]:
In [190]:
def tri_insertion(entiers : list) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee(acc, e[0]))
return trix(entiers, [])
In [191]:
tri_insertion([5, 2, 6, 1, 4])
Out[191]:
In [193]:
def ordre_decroissant(x, y):
return x > y
In [195]:
from types import FunctionType
def insertion_dans_liste_triee2(entiers : list, x : int, ordre : FunctionType) -> list:
i = 0
while i < len(entiers) and ordre(entiers[i], x):
i += 1
return entiers[:i] + [x] + entiers[i:]
In [196]:
insertion_dans_liste_triee2([6, 5, 2, 1], 4, ordre_decroissant)
Out[196]:
In [197]:
def tri_insertion2(entiers : list, ordre : FunctionType) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee2(acc, e[0], ordre))
return trix(entiers, [])
In [200]:
tri_insertion([5, 2, 6, 1, 4])
tri_insertion2([5, 2, 6, 1, 4], ordre_decroissant)
Out[200]:
Out[200]:
In [3]:
def exp(x : int, n : int) -> int:
res = 1
for _ in range(n):
res *= x
return res
In [4]:
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp(x, n)))
In [201]:
def exp2(x : int, n : int) -> int:
assert n >= 0
if n == 0:
return 1
elif n == 1:
return x
elif n % 2 == 0:
return exp2(x ** 2, n // 2)
elif n % 2 == 1:
return exp2(x ** 2, (n - 1) // 2) * x
In [205]:
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp2(x, n)))
In [6]:
def mult_float(x : float, y : float) -> float:
return x * y
monoide_flottants = {
'mult': mult_float, # (*.) en Caml
'neutre': 1.
}
In [15]:
import numpy as np
def mult_ndarray(A : np.array, B : np.array) -> np.array:
return np.dot(A, B)
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_nparray = lambda n, m: {
'mult': mult_ndarray,
'neutre': np.eye(n, m)
}
In [16]:
mult_ndarray([[1, 1], [1, 1]], [[1, 2], [3, 4]])
Out[16]:
Manuellement ce n'est pas trop dur :
In [31]:
def mult_mat(A : list, B : list) -> list:
n, m = len(A), len(A[0]) # A est (n, m)
m2, p = len(B), len(B[0]) # B est (m2, p)
assert m == m2
C = [[0 for _ in range(p)] for _ in range(n)] # C est (n, p)
for i in range(n):
for j in range(p):
for k in range(m):
C[i][j] += A[i][k] * B[k][j]
return C
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_mat = lambda n, m: {
'mult': mult_mat,
'neutre': [[int(i==j) for j in range(m)] for i in range(n)] # I est (n, m)
}
In [32]:
mult_mat([[1, 1], [1, 1]], [[1, 2], [3, 4]])
Out[32]:
In [33]:
def exp_rapide(monoide : dict, x, n : int):
mult = monoide['mult']
assert n >= 0
if n == 0:
return monoide['neutre']
elif n == 1:
return x
elif n % 2 == 0:
return exp_rapide(monoide, mult(x, x), n // 2)
elif n % 2 == 1:
return mult(exp_rapide(monoide, mult(x, x), (n - 1) // 2), x)
In [34]:
def exp_rapide_float(x : float, n : int) -> float:
return exp_rapide(monoide_flottants, x, n)
In [35]:
exp_rapide_float(2.0, 8)
Out[35]:
In [36]:
exp_rapide_float(0.2, 8)
Out[36]:
Et pour les matrices, un petit piège à cause des tailles :
In [37]:
def exp_rapide_mat(A : list, k : int) -> float:
n, m = len(A), len(A[0])
mono = monoide_mat(n, m)
return exp_rapide(mono, A, k)
In [38]:
for k in range(5):
exp_rapide_mat([[1, 1], [1, 1]], k)
Out[38]:
Out[38]:
Out[38]:
Out[38]:
Out[38]:
In [42]:
for k in range(5): # nilpotente
exp_rapide_mat([[0, 1, 2], [0, 0, 1], [0, 0, 0]], k)
Out[42]:
Out[42]:
Out[42]:
Out[42]:
Out[42]:
In [48]:
from operator import mul
def exp_rapide_2(x, n : int):
def mul_par_x(y):
return x * y
return itere(mul_par_x, n)(x)
In [49]:
exp_rapide_2(2.0, 8)
Out[49]:
(not p ^ ((q ^ not p) v (r v q))) s'écrit en Caml (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q"))))).
On va imbriquer des dictionnaires, les types, V, Not, Conj et Disj seront des clés, et les valeurs seront des formules ou couples de formules.
Mais on va cacher ça et l'utilisateur verra exactement la même chose qu'en Caml !
In [63]:
V = lambda x: {'V': x}
Not = lambda x: {'Not': x}
Disj = lambda x, y: {'Disj': (x, y)}
Conj = lambda x, y: {'Conj': (x, y)}
p = V('p')
r = V('r')
q = V('q')
not_p = Not(p)
f = Conj(Not(p), Disj(Conj(q, not_p), Disj(r, q)))
f
Out[63]:
In [59]:
(Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q")))))
Out[59]:
Ensuite on fait une filtration "à la main" sur les clés du dictionnaire (de niveau 1, on ne récurse pas quand on teste 'V' in formule).
In [79]:
def taille(formule : dict) -> str:
if 'V' in formule:
return 0
elif 'Not' in formule:
return 1 + taille(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return 1 + taille(x) + taille(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return 1 + taille(x) + taille(y)
In [69]:
taille(f)
Out[69]:
In [109]:
def formule_to_string(formule : dict) -> str:
if 'V' in formule:
return formule['V']
elif 'Not' in formule:
return "~" + formule_to_string(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return "(" + formule_to_string(x) + " ^ " + formule_to_string(y) + ")"
elif 'Disj' in formule:
x, y = formule['Disj']
return "(" + formule_to_string(x) + " V " + formule_to_string(y) + ")"
In [110]:
def affiche(formule):
print(formule_to_string(formule))
In [111]:
affiche(f)
Et voilà. Pas tellement plus dur hein !
Les valeurs des variables seront données comme un dictionnaire associant nom de variable à valeurs booléennes.
Et comme on veut frimer, on prend un defaultdict.
In [115]:
from collections import defaultdict
d = defaultdict(lambda: False, {'p': True, 'q': False})
d['p'] # -> True car présent et True
d['q'] # -> False car présent et False
d['x'] # -> False car absent
Out[115]:
Out[115]:
Out[115]:
In [113]:
valeurs_1 = defaultdict(lambda: False, {'p': True})
In [114]:
valeurs_2 = defaultdict(lambda: False, {'r': True})
In [89]:
def eval(valeurs : dict, formule : dict) -> bool:
if 'V' in formule:
return valeurs[formule['V']]
elif 'Not' in formule:
return not eval(valeurs, formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return eval(valeurs, x) and eval(valeurs, y)
elif 'Disj' in formule:
x, y = formule['Disj']
return eval(valeurs, x) or eval(valeurs, y)
In [90]:
eval(valeurs_1, f)
Out[90]:
In [91]:
eval(valeurs_2, f)
Out[91]:
In [93]:
def extrait_variables_x(formule : dict) -> list:
if 'V' in formule:
return [formule['V']]
elif 'Not' in formule:
return extrait_variables_x(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return extrait_variables_x(x) + extrait_variables_x(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return extrait_variables_x(x) + extrait_variables_x(y)
# on enlève les doublons
def extrait_variables(formule : dict) -> list:
return list(set(extrait_variables_x(formule)))
In [94]:
extrait_variables(f)
Out[94]:
On trouve facilement les $n$ variables d'une formule.
Ensuite, un itertools.product permet de générer les $2^n$ valuations.
In [98]:
from itertools import product
def toutes_valeurs(variables):
for valeurs in product([False, True], repeat=len(variables)):
yield defaultdict(lambda: False, {k:v for k,v in zip(variables, valeurs)})
In [103]:
list(toutes_valeurs(extrait_variables(f)))
Out[103]:
In [106]:
def str_of_bool(x : bool) -> str:
# return str(int(x))
return '1' if x else '0'
In [116]:
def table_verite(formule : dict) -> None:
variables = extrait_variables(formule)
# D'abord la formule
for k in variables:
print(k, end=' ')
print('| ', end='')
affiche(f)
# Puis toutes ces valeurs possibles
for valeurs in toutes_valeurs(variables):
for k in variables:
print(str_of_bool(valeurs[k]), end=' ')
print('| ', end='')
print(str_of_bool(eval(valeurs, formule)))
In [117]:
table_verite(f)
Note : ce code est encore plus concis que celui donné dans la solution en Caml.
On peut vérifier, par exemple sur Wolfram|Alpha que l'on obtient bien le bon résultat...
Comme vous le voyez, on arrive à répondre aux mêmes questions dans les deux langages, et il n'y a pas de grosses différences en pratique dans la mise en oeuvre.
Là où Caml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles...