Hacker News Reader

Comment by ghshephard | Hacker News Reader

I think a lot of this is based on your experience with languages. If you have exposure to a list/iterator native language like python, you come up with solution in a few seconds, even if you aren't even remotely a programmer. Other languages might not lend themselves to so obvious a solution.

The perl example cited here kind of blows my mind compare to the trivial python approach:

  def flatten(lst):
      rlst=[]
      for x in lst:
          if type(x)==list:
              for y in(flatten(x)):
                  rlst.append(y)  
          else:
              rlst.append(x)
      return (rlst)

View on HN

A similar trivial approach works in Perl:

  sub flatten
  {
      my @in = @{$_[0]};
      my @out;
      while (@in) {
          my $item = shift @in;
          if (ref $item eq 'ARRAY') {
              unshift @in, @$item;
          } else {
              push @out, $item;
          }
      }
      return \@out;
  }

Input is a reference to the source list, output is a reference to the flattened list.

The main difference is that I opted to manipulate a copy of the source list in place to expand sublists rather than recurse.

As others have noted, a recursive version using map can be written much more concisely.

>The perl example cited here kind of blows my mind compare to the trivial python approach

That's because the Perl version is a two-for-one deal: just for fun, Cestith threw in a non-recursive version too. The 'trivial' recursive approach is more or less equivalent to the Python:

  sub flatten { map ref($_)? flatten(@$_) : $_, @_ }

Gee, that's almost exactly what I got:

  def flatten(nested_list):
      output_list = []
      for elem in nested_list:
          if type(elem) == list:
              output_list.extend(flatten(elem))
          else:
              output_list.append(elem)
      return output_list

I think that's easier to read than the following, and appears to run slightly faster as well?

  import collections

  def flatten(nested_list):
      if isinstance(nested_list, collections.Iterable):
          return [a for i in nested_list for a in flatten(i)]
      else:
          return [nested_list]

You perhaps missed that there were two solutions (+ test infrastructure) in that Perl post. You Python code is the moral equivalent of the three-line "flatten" function in the Perl example. The long "flatten2" function was doing it without recursion.

The part that was/is challenging/mind blowing for me to grok was:

   sub flatten {
        my @f;
        push @f, (ref $_ ? flatten( $_ ) : $_ ) for @{ $_[0] };
        return @f;
    }

The implicit $_, and whatever @{ $_[0]} does, is challenging enough that I bet I could find people who had been using perl to do work for years who wouldn't be able to explain what was happening here at first glance, even if they could eventually work it out/write it themselves with a bit of effort.

That's what I meant by native iterative/sequence languages like python lend themselves to easy solutions for this type of question, even for people who aren't programmers, whereas you really need to be a programmer to come up with something as powerful as the above.

Put another way, doing a complex joined query might be a trivial question for someone who knows even the slightest amount of SQL, but would be beyond most novice python developers (without of course just using a SQL select statement...)

I will admit the (dense) perl solution certainly has its own beauty that the more drawn out python solution is lacking, though I'm guessing it could be written in a pythonic way itself...

> I bet I could find people who had been using perl to do work for years who wouldn't be able to explain what was happening here

Don't jump to conclusions. You will not find such people, because those are very basics. Understanding of $_[0] is necessary to use arguments in Perl functions and understanding of @{...} is necessary to use array references as lists.

Challenge accepted.

Reply on news.ycombinator.com