How to get a flattened list from nested class List?

Question

I have a question using these same examples - this question is focused on a different issue. Given the following classes:

   [XmlRoot]
   public class Family {

      [XmlElement]
      public List<Person> Person;
   }

   public class Person {

      [XmlAttribute("member")]
      public MemberType Member { get; set; }

      [XmlAttribute("id")]
      public int Id { get; set; }

      [XmlElement]
      public string Surname { get; set; }

      [XmlElement]
      public string Forename { get; set; }

      [XmlElement("Person")]
      public List<Person> People;
   }

   public enum MemberType {
      Father,
      Mother,
      Son,
      Daughter
   }

If Family has a method defined as such:

public IEnumerable<Person> Find (Func<Person, bool> predicate) {
    //  how do I get SelectMany to flatten the list?
    foreach (var p in family.Person.SelectMany(p => p)) {
        if(predicate(p)) {
            yield return p;
        }
    }
}

I need to be able to execute the predicate over a flattened list of Person. In the example above SelectMany is not flattening the list as I had hoped. The above actually won't compile because the inferred type cannot be determined.

How can I get the Family.Person collection to become one flattened list of Person?

If you have loops in your data structure you can this solution: http://stackoverflow.com/questions/141467/recursive-list-flattening/24747394#answer-24747394 — Aidin, Jul 14 '14 at 23:03

score 6 · Answer 1 · edited Jan 13 '12 at 09:48

To my knowledge, the easiest way to accomplish this is using a helper.

    private List<Person> FlattenTree(Person person)
    {
        var accumulator = new List<Person>();
        FlattenPersonHelper(person, accumulator);

        return accumulator;
    }


    private void FlattenPersonHelper(Person person, List<Person> accumulator)
    {
        accumulator.Add(person);

        foreach (var child in person.People)
        {
            FlattenPersonHelper(child, accumulator);
        }
        return;
    }

You can then run your predicate against this list:

public IEnumerable<Person> Find (Func<Person, bool> predicate) {
    var familyRoot = new Person() { People = family.Person };
    return FlattenTree(familyRoot).Where(predicate);
}

Thanks! and Thanks! PS I use this pattern often enough that I've written a generic version as an extension method. Super useful. — armen.shimoon, Jan 12 '12 at 16:52

Petr Behenský · Accepted Answer · 2012-01-12T17:52:24.380

5

public IEnumerable<Person> Find(IEnumerable<Person> input, Func<Person, bool> predicate) {
    return input.Select(p => 
        {
            var thisLevel = new List<Person>();
            if(predicate(p))
                thisLevel.Add(p);

            return thisLevel.Union(Find(p.People ?? new List<Person>(), predicate));
        }
    ).SelectMany(p => p);
}

edited Jan 12 '12 at 17:52

answered Jan 12 '12 at 17:21

Petr Behenský

620
1
6
17

+1 for spotting the recursive data structure, the question didn't make this point obvious enough :) – MattDavey Jan 13 '12 at 09:46
2

I recommend Concat over Union since there is no need to screen for cross-set duplicates. – Amy B Jan 13 '12 at 13:28

Amy B · Answer 3 · 2012-01-12T16:40:25.403

SelectMany only flattens one level of hierarchy:

public IEnumerable<Person> FindLevel2 (Func<Person, bool> predicate)
{
  return family.Person.SelectMany(p => p.People).Where(predicate);
}

You might actually want an arbitrary depth walk of the hierarchy. That's best done by recursion (Untested).

public IEnumerable<Person> Find(Func<Person, bool> predicate)
{
  foreach(Person p in family.Person)
  {
    IEnumerable<Person> result = FindFromPerson(p);
    foreach(Person x in result)
    {
      yield return x;
    }
  }
}

public IEnumerable<Person> FindFromPerson(Person p, Func<Person, bool> predicate)
{
  if predicate(p)
  {
    yield return p;
  }
  foreach(Person child in p.People)
  {
    IEnumerable<Person> childResults = FindFromPerson(child);
    foreach(Person x in childResults)
    {
      yield return x;
    }
  }
}

score 3 · Answer 4 · answered Jan 12 '12 at 16:23

3

You do not need both SelectMany and yield return - you need one or the other:

public IEnumerable<Person> Find (Func<Person, bool> predicate) {
    foreach (var p in family.Person) {
        if(predicate(p)) {
            yield return p;
        }
    }
}

OR

public IEnumerable<Person> Find (Func<Person, bool> predicate) {
    return family.Person.Where(p => predicate(p)); // Can be written simply as Where(predicate)
}

answered Jan 12 '12 at 16:23

Sergey Kalinichenko

714,442
84
1,110
1,523

1

*'p => predicate(p)'* can be reduced to just *'predicate'* - atm you're wrapping one *Func* with another. – MattDavey Jan 12 '12 at 16:26
1

@MattDavey I added a wrapper to remove the "magic" from the expression. I added a comment line to say that it can be simplified. It is just that looking at a `Where` clause without `=>` in it may be confusing to people with relatively little LINQ experience. – Sergey Kalinichenko Jan 12 '12 at 16:26
yeah I think that's a pertinent thing to do :) – MattDavey Jan 12 '12 at 16:38

Adam Rackis · Answer 5 · 2012-01-12T16:27:59.253

2

family.Person already is a flattened list; there's no need to call SelectMany on it.

foreach (var p in family.Person) {
    if(predicate(p)) {
        yield return p;
    }
}

Also, you can more simply do:

public IEnumerable<Person> Find (Func<Person, bool> predicate) {
    return family.Person.Where(predicate);
}

edited Jan 12 '12 at 16:27

answered Jan 12 '12 at 16:22

Adam Rackis

82,527
56
270
393

notice that Person has a nested *List*. It is **not** a flattened list, it's a recursive data structure. – MattDavey Jan 13 '12 at 09:44
1

@Matt - I totally didn't see that - especially considering OP's original code of `family.Person.SelectMany(p => p)` I'd edit to fix, but it looks like Petr already knocked it out of the park – Adam Rackis Jan 13 '12 at 15:40

How to get a flattened list from nested class List?

5 Answers5