Etoile de Kleene

Algorithme en Haskell qui est censé fonctionner. J'utilise la notion de langage mais un alphabet fonctionne tout autant (si l'on considère des chaînes de caractère de longueur 1).

J'assimile $\epsilon$ (le mot vide) à la chaîne de caractère(s) de longueur 0 (soit "" en Haskell)

1-- D'autres méthodes existent pour la concaténation
2-- de langages mais celle ci est la plus proche de
3-- la définition naturelle de cette opération.
4concatener :: [String] -> [String] -> [String]
5concatener langage_1 langage_2 = concatMap f langage_1
6  where
7    f :: String -> [String]
8    f mot_1 = map (g mot_1) langage_2
9    g :: String -> String -> String
10    g mot_1 mot_2 = mot_1 <> mot_2
11
12-- On peut aussi utiliser fold mais la méthode
13-- récursive fonctionne assez bien en termes
14-- de performance.
15puissance :: Integer -> [String] -> [String]
16puissance 0 _ = [""]
17puissance 1 langage = langage
18puissance p langage = concatener langage $ puissance (p - 1) langage
19
20kleene :: [String] -> [String]
21kleene langage = concatMap (`puissance` langage) [0 ..]
22
23-- Limite le nombre d'éléments que l'on prend afin
24-- d'éviter une liste infinie.
25kleeneN :: Int -> [String] -> [String]
26-- On peut aussi utiliser: concatMap (`puissance` langage) [0 .. n-1]
27kleeneN n = take n . kleene