Opened 15 years ago

Closed 15 years ago

#395 closed task (fixed)

flatten command for nested lists

Reported by: mhampton Owned by: mhampton
Priority: major Milestone: sage-2.8.4.2
Component: basic arithmetic Keywords: lists, flatten
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The attached file has a candidate function for a flatten command. The default types to flatten are lists and tuples, but more can be added.

def flatten(in_list, ltypes=(list, tuple)):
    """
    Flattens a nested list.

    INPUT:
        in_list -- a list or tuple
        ltypes -- optional list of particular types to flatten

    OUTPUT:
        a flat list of the entries of in_list

    EXAMPLES:
        sage: flatten([[1,1],[1],2])
        [1, 1, 1, 2]
        sage: flatten((['Hi',2,vector(QQ,[1,2,3])],(4,5,6)))
        ['Hi', 2, (1, 2, 3), 4, 5, 6]
        sage: flatten((['Hi',2,vector(QQ,[1,2,3])],(4,5,6)),ltypes=(list, tuple, sage.modules.vector_rational_dense.Vector_rational_dense))
        ['Hi', 2, 1, 2, 3, 4, 5, 6]
    """
    index = 0
    new_list = [x for x in in_list]
    while index < len(new_list):
        if not new_list[index]:
            new_list.pop(index)
            continue
        while isinstance(new_list[index], ltypes):
            new_list[index : index + 1] = list(new_list[index])
        index += 1
    return new_list

Change History (12)

comment:1 Changed 15 years ago by mhampton

  • Status changed from new to assigned

comment:2 Changed 15 years ago by mhampton

New version:

def flatten(in_list, ltypes=(list, tuple)):

""" Flattens a nested list.

INPUT:

in_list -- a list or tuple ltypes -- optional list of particular types to flatten

OUTPUT:

a flat list of the entries of in_list

EXAMPLES:

sage: flatten([[1,1],[1],2]) [1, 1, 1, 2] sage: flatten(1,2,3], (4,5), [[[1],[2?]]) [1, 2, 3, 4, 5, 1, 2]

In the following example, the vector isn't flattened because it is not given in the ltypes input.

sage: flatten((['Hi',2,vector(QQ,[1,2,3])],(4,5,6))) ['Hi', 2, (1, 2, 3), 4, 5, 6]

We give the vector type and then even the vector gets flattened:

sage: flatten((['Hi',2,vector(QQ,[1,2,3])], (4,5,6)),

ltypes=(list, tuple,sage.modules.vector_rational_dense.Vector_rational_dense))

['Hi', 2, 1, 2, 3, 4, 5, 6]

We flatten a finite field.

sage: flatten(GF(5)) [0, 1, 2, 3, 4] sage: flatten([GF(5)]) [Finite Field of size 5] sage: flatten([GF(5)], ltypes = (list, tuple,

sage.rings.finite_field.FiniteField_prime_modn))

[0, 1, 2, 3, 4]

""" index = 0 new_list = [x for x in in_list] while index < len(new_list):

while isinstance(new_list[index], ltypes):

if len(new_list[index]) != 0:

new_list[index : index + 1] = list(new_list[index])

else:

new_list.pop(index) break

index += 1

return new_list

comment:3 Changed 15 years ago by mabshoff

  • Milestone set to sage-2.8.3

Sage 2.8.2 has a flatten command. It also seems to work on nested lists:

sage: L
[[1, 2], [1, 2]]
sage: flatten(L)
[1, 2, 1, 2]
sage: L=[L,[L,[L,[L]]]]
sage: L
[[[1, 2], [1, 2]], [[[1, 2], [1, 2]], [[[1, 2], [1, 2]], [[[1, 2], [1, 2]]]]]]
sage: flatten(L)
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

So am I correct to assume that this ticket can be closed?

Cheers,

Michael

comment:4 Changed 15 years ago by was

  • Resolution set to fixed
  • Status changed from assigned to closed

Yep, this has been in SAGE a while.

comment:5 Changed 15 years ago by mhampton

  • Milestone changed from sage-2.8.3 to sage-feature
  • Resolution fixed deleted
  • Status changed from closed to reopened
  • Type changed from enhancement to defect

This still has some problems on empty lists, which I (Marshall Hampton) will try to fix soon. the simplest example of the problem for the current (2.8.4.1) behavior is: flatten(],[?) [[]]

It should return [].

comment:6 follow-up: Changed 15 years ago by mhampton

  • Status changed from reopened to new

comment:7 in reply to: ↑ 6 Changed 15 years ago by mhampton

Replying to mhampton:

Sorry, I am not used to this formatting. My example should be:
flatten(],[?)
[[]]

comment:8 Changed 15 years ago by mhampton

  • Status changed from new to assigned

comment:9 Changed 15 years ago by mhampton

  • Milestone changed from sage-feature to sage-2.9.1
  • Type changed from defect to task

Here is a new version that I believe fixes the problem.

def flatten(in_list, ltypes=(list, tuple)):
   """
   Flattens a nested list.

   INPUT:
       in_list -- a list or tuple
       ltypes -- optional list of particular types to flatten

   OUTPUT:
       a flat list of the entries of in_list

   EXAMPLES:
       sage: flatten([[1,1],[1],2])
       [1, 1, 1, 2]
       sage: flatten([[1,2,3], (4,5), [[[1],[2]]]])
       [1, 2, 3, 4, 5, 1, 2]

   In the following example, the vector isn't flattened because
   it is not given in the ltypes input. 
       sage: flatten((['Hi',2,vector(QQ,[1,2,3])],(4,5,6)))
       ['Hi', 2, (1, 2, 3), 4, 5, 6]

   We give the vector type and then even the vector gets flattened:
       sage: flatten((['Hi',2,vector(QQ,[1,2,3])], (4,5,6)), ltypes=(list, tuple,sage.modules.vector_rational_dense.Vector_rational_dense))
       ['Hi', 2, 1, 2, 3, 4, 5, 6]

   We flatten a finite field. 
       sage: flatten(GF(5))
       [0, 1, 2, 3, 4]
       sage: flatten([GF(5)])
       [Finite Field of size 5]
       sage: flatten([GF(5)], ltypes = (list, tuple, sage.rings.finite_field.FiniteField_prime_modn))
       [0, 1, 2, 3, 4]

   Degenerate cases:
      sage: flatten([[],[]])
      []
      sage: flatten([[[]]])
      []
   """
   index = 0
   new_list = [x for x in in_list]
   while index < len(new_list):
      while isinstance(new_list[index], ltypes):
         v = list(new_list[index])
         if len(v) != 0:
            new_list[index : index + 1] = v
         else:
            new_list.pop(index)
            index += -1
            break
      index += 1
   return new_list

comment:10 Changed 15 years ago by was

  • Milestone changed from sage-2.9.1 to sage-2.8.4.2

comment:11 Changed 15 years ago by was

  • Priority changed from minor to major

comment:12 Changed 15 years ago by was

  • Resolution set to fixed
  • Status changed from assigned to closed

applied for sage-2.8.4.2.

Note: See TracTickets for help on using tickets.