Puzzle: Générateur récursif sans boucles/importations

Question

Il est générateurs aujourd'hui. J'ai vu un question aujourd'hui qui voulait trouver un moyen d'aplatir une liste de manière récursive sans utiliser de boucles et d'importations. tobias_k a répondu avec un code suivant:

def flatten(test_list): 
    if isinstance(test_list, list): 
     if len(test_list) == 0: 
      return [] 
     first, rest = test_list[0], test_list[1:] 
     return flatten(first) + flatten(rest) 
    else: 
     return [test_list] 

Est-il possible de créer un générateur (avec le maintien des règles: pas d'importations, des boucles)?

NOTE: il est purement éducatif. Je sais que ce n'est pas la meilleure idée, mais je ne sais pas comment faire.

Answer 1

A generator function est une fonction qui contient au moins un yield statement et aucun return états qui ont une expression. Lorsqu'une fonction de générateur est invoquée, elle renvoie un itérateur de générateur qui, lorsqu'il est itéré (par exemple par une boucle for ou explicitement avec next) parcourt le corps de la fonction, gèle son état et renvoie le contrôle à l'appelant sur chaque instruction yield (et dans Python 3.3, yield from instructions).

Le contrôle de flux dans une fonction Python est toujours en avant; sans hacks comme le réglage des images actuelles f_lineno (comme le fait célèbre le (poisson d'avril) goto statement), la seule façon pour le contrôle d'atteindre un point antérieur est d'utiliser une boucle (for ou while). Donc, sans boucle ou yield from, le nombre maximum de fois qu'un itérateur de générateur peut être appelé est limité par le nombre d'instructions yield dans la fonction de générateur. Notez qu'il est facile d'écrire un flatten qui renvoie un itérateur;prendre la solution originale et écrire return iter(flatten(first) + flatten(rest)) ferait l'affaire. Mais ce ne serait pas un itérateur de générateur, et la fonction ne serait pas une fonction de générateur.

Voici une implémentation qui abuse de f_lineno pour donner une itération sans boucle. Malheureusement, il doit utiliser import sys:

def current_frame(): 
    i = None 
    def gen(): 
     yield i.gi_frame.f_back 
    i = gen() 
    return next(i).f_back 

class Loop(object): 
    jump = False 
    def __call__(self, frame, event, arg): 
     if self.jump: 
      frame.f_lineno = self.lineno 
      self.jump = False 
     return None if event == 'call' else self 
    def __enter__(self): 
     import sys 
     sys.settrace(self) 
     current_frame().f_back.f_trace = self 
     self.lineno = current_frame().f_back.f_lineno 
     return self 
    def __exit__(self, exc_type, exc_value, traceback): 
     if exc_type is None: 
      self.jump = True 
     else: 
      import sys 
      sys.settrace(None) 
      current_frame().f_back.f_trace = None 
      return exc_type is StopIteration 

def flatten(x): 
    if isinstance(x, list): 
     if x: 
      first, rest = flatten(x[0]), flatten(x[1:]) 
      with Loop(): 
       yield next(first) 
      with Loop(): 
       yield next(rest) 
      pass 
    else: 
     yield x 

Answer 2

En Python 3.3 (version de développement), vous pouvez utiliser la yield from construction pour éviter les boucles explicites:

def flatten(x): 
    if isinstance(x, list): 
     if x: 
      first, rest = x[0], x[1:] 
      yield from flatten(first) 
      yield from flatten(rest) 
    else: 
     yield x 

Dans les versions actuelles, je ne peux pas penser à une solution qui n'utilise pas itertools.chain.

Answer 3

fait avec une seule compréhension de liste de ligne:

def flatten (test_list): 
    return [element for temp in test_list for element in flatten(temp)] if isinstance(test_list, list) else [test_list] 


print(flatten([1, [2, 1, [3, 6, 7]], [1, 2, [3, 2, 3], 4, [1, 2, 3, 4, 5]]])) 
#[1, 2, 1, 3, 6, 7, 1, 2, 3, 2, 3, 4, 1, 2, 3, 4, 5]