Nested for loops in different languages

Question

Here is a fairly common problem. We have an array of arrays. We'd like to call some function for every combination of elements from the different arrays. Conceptually we'd like to do something like this:

for my $x (1, 2) {
  for my $y ('a', 'b') {
    for my $z ('A', 'B') {
      print "$x $y $z\n";
    }
  }
}

except that we don't want to have to write out a different number of loops if we have a different number of elements. In other words we want to be able to implement the above as something like:

nested_for(
  sub {print "@_\n"},
  [1, 2], ['a', 'b'], ['A', 'B']
);

and get the same result. (Exact syntax may vary by language.)

One solution per post, please.

Index of Solutions

(with at least +1 vote)

• APL by Christian D
• D by BCS
• Haskell
  • by Rodrigo Queiro
  • for both heterogenous and homogenous lists by Apocalisp
• Java by einarwh.myopenid.com
• JavaScript by Kent Fredric
• Lisp
  • by levy
  • a newbie attempt by Chris Jester-Young
• Nemerle by Cody Brocious
• Perl
  • by bentilly.blogspot.com
  • with Algorithm::Loops by runrig.myopenid.com
  • Perl 6 version by Eevee
• Python
  • by Alexander Kojevnikov
  • with generators by Torsten Marek
• Ruby
  • two solutions by Kent Fredric (including a variant with mapping)
  • by bentilly.blogspot.com on behalf of Christoph Rippel
  • by Kevin Conner
  • permutative/generative version by Kent Fredric

Answer 1

To get things going, here is a Perl solution:

nested_for(
  sub {print "@_\n";},
  [1, 2], ['a', 'b'], ['A', 'B']
);

sub nested_for {
  ret_iter(@_)->();
}

sub ret_iter {
  my $fn = shift;
  my $range = pop;
  my $sub = sub {$fn->(@_, $_) for @$range};
  return @_ ? ret_iter($sub, @_) : $sub;
}

Answer 2

It's not just 'conceptually' that you'd want to do that: it's what you would end up doing in any imperative language. In Python, you could use a generator function and a function to generate all combinations that together would pretty neatly express what you are doing, but in truth, it's still a for .. for .. for ..

Unless you think recursive answers, such as I see appearing now, are more intuitive and expressive, but I sure as hell do not agree with that. :)

Answer 3

In Nemerle using a macro:

macro nested_for(lists, block)
syntax("nested_for", lists, block) {
    def build(lists) {
        | [] => block
        | <[ $name in $sub ]> :: tail =>
            <[ 
                foreach($(name.ToString() : dyn) in $sub)
                    ${ build(tail) }
            ]>
    }

    build(lists)
}

To use (note: the print and <- string formatting macros are from the Nextem library):

nested_for(x in [1, 2], y in ['a', 'b'], z in ['A', 'B'])
    print "{0} {1} {2}" <- (x, y, z)

Answer 4

Here is a Ruby answer due to Christoph Rippel

def each (arg,*more_args)
      ( [] != more_args ) ?
               arg.each {|l| each(*more_args) {|r| yield [l]+ r }} :
               arg.each { |r| yield [r] }
end

each( 1..2, 'a'..'b', 'A'..'B') { |args|   puts args.join(" ") }

Answer 5

tested D

template T(t...)
{
  alias t T;
}

template Tof(uint i, Ty)
{
  static if(i >0) alias T!(Ty, Tof!(i-1,Ty)) Tof;
  else            alias T!() Tof;
}

void Loop(T, int i)(T[][i] arr, void delegate(Tof!(i, T)) dg)
{
  Inner!(T,i,i)(arr, dg);
}

void Inner(T, int i, int j)(T[][i] arr, void delegate(Tof!(i, T)) dg, Tof!(i-j, T) val)
{
  static if(j > 0)
    foreach(v;arr[j-1])
      Inner!(T,i,j-1)(arr,dg,v,val);
  else
    dg(val);
}

void main()
{
  Loop!(int,4)([[1,2][], [1], [1,2,3],[1,2,3,4,5,6,7,8]], 
  (int i, int j, int k, int m)
  {
    writef("%s,%s,%s,%s\n",i,j,k,m);
  });
}

Answer 6

In Python:

def loop(action, values, *args):
    if values is None:
        values = []
    if args:
        for value in args[0]:
            loop(action, values + [value], *args[1:])
    else:
        action(*values)

def action(a, b, c):
    print a, b, c

loop(action, None, [1, 2], ['a', 'b'], ['A', 'B'])

Answer 7

Ruby:

def loopme( list, reg = [], &block )
 if( list.length > 0 )
   list[0].each{ |x|
    m = list.clone;  
    m.shift;
    loopme( m, reg +[x] , &block );
   }
 else
  block.call( reg )
 end
end
loopme( [[1,2],[3,4],[5,6]] ) {  |x|  p x }

( Note, the double bracketing is needed to pass all the positional registers down the stack )

Output:

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

And heres a variant with mapping instead.

def loopme( list, reg = [], &block )
  if( list.length > 1 )
    out = [];
    list[0].each{ |x|
      m = list.clone;  
      m.shift;
      out = out + loopme( m,  reg + [x] , &block )
    }
    return out
  else
   return list[0].map{ |x|
     block.call( reg + [x] )
   }
  end
end

require "pp";

pp loopme( [[1,2],[3,4],[5,6]] ) {  |x|  ['hello',x,'world'] }

[["hello", [1, 3, 5], "world"],
 ["hello", [1, 3, 6], "world"],
 ["hello", [1, 4, 5], "world"],
 ["hello", [1, 4, 6], "world"],
 ["hello", [2, 3, 5], "world"],
 ["hello", [2, 3, 6], "world"],
 ["hello", [2, 4, 5], "world"],
 ["hello", [2, 4, 6], "world"]]

( Note: Using tree flattening for ease of use.

Answer 8

D, no (extra) template stuff, no recursion, no "nested for loops"

void Loop(T)(T[][] arr, void delegate(T[]) dg)
{
  int[] index = new int[arr.length];  // set of indexes
  foreach(ref i;index)i=0;

  T[] val = new T[arr.length]; // set of values

  // main loop
  outer: while(true)
  {
    // select values
    foreach(int i, a;arr) val[i] = a[index[i]];

    dg(val); // call function

    for(int i=0; i < arr.length; i++) // inc, roll & continue on overflow
    {
      index[i]++;
      if(index[i] < arr[i].length) continue outer;
      index[i]=0;
    }

    return; // for loop continues outer on non-terminating case
  }
}


void main()
{
  Loop!(int)([[1,2][], [1], [1,2,3],[1,2,3,4,5,6,7,8]], 
    (int[] i){   writef("%s\n",i);   });
}

Answer 9

Ruby:

def nested_for(axes, args = [], &block)
    if axes.empty?
     yield args
    else
     axes[0].each do |value|
      nested_for(axes[1,axes.length], args + [value], &block)
     end
    end
end

nested_for([[1, 2], [3, 4], [5, 6]]) do |args|
    puts args.join(" ")
end

Answer 10

Permutative/Generative version:

( Nonrecursive / Ruby )

def loopme( list, &block )
 perms = [];
 list[0].each{ |set|
   perms.push([set])
 }
 list[1..-1].each{ |set|
   newperms = [];
   perms.each{ |oldperms|
     set.each{ |item|
      newperms.push( oldperms + [item] )
     }
   }
   perms = newperms
 }
 return perms.each{ |x| block.call(x) }
end

To make into a map equivalent, change the last line.

Answer 11

Javascript:

function nested_for(axes, args, delegate) {
 if (axes.length == 0) {
  delegate(args);
 }
 else {
  var axis = axes[0];
  for (var i = 0; i < axis.length; i++) {
   nested_for(axes.slice(1), args.concat([axis[i]]), delegate);
  }
 }
}

nested_for([[1, 2], [3, 4], [5, 6]], [], function(args) {
 alert(args.join(" "));
});

Answer 12

Cheating Perl version. (Sometimes useful in golf.)

print "$_\n" for glob "{1,2}\\ {a,b}\\ {A,B}"

Answer 13

Java w/ Decorators. Iterates over last list first, first list last (easily reversed, of course).

public final class Loop {

   public static void nestedFor(final Method sub, final List... lists) {
      Method m = sub;
      for (final List list : lists) {
         m = new Iterator(list, m);
      }
      m.execute(new ArrayList());
   }

   interface Method {
      void execute(List objs);
   }

   private static class Iterator implements Method {

      private final List list;
      private final Method method;

      public Iterator(final List list, final Method method) {
         this.list = list;
         this.method = method;
      }

      @Override
      public void execute(final List objs) {
         for (final Object o : list) {
            objs.add(o);
            method.execute(objs);
            objs.remove(o);
         }
      }
   }

   private static class Printer implements Method {

      @Override
      public void execute(final List objs) {
         for (final Object o : objs) {
            System.out.print(o + " ");
         }
         System.out.println();
      }

   }

}

Answer 14

In Common Lisp see the Alexandria package and search for map-product:

(defun map-product (function list &rest more-lists) ...)

Returns a list containing the results of calling FUNCTION with one argument from LIST, and one from each of MORE-LISTS for each combination of arguments. In other words, returns the product of LIST and MORE-LISTS using FUNCTION.

Example:

(map-product 'list '(1 2) '(3 4) '(5 6)) => ((1 3 5) (1 3 6) (1 4 5) (1 4 6)
                                             (2 3 5) (2 3 6) (2 4 5) (2 4 6))

In case you are interested in the details it is implemented as:

(defun map-product (function list &rest more-lists)
  (labels ((%map-product (f lists)
             (let ((more (cdr lists))
                   (one (car lists)))
               (if (not more)
                   (mapcar f one)
                   (mappend (lambda (x)
                              (%map-product (curry f x) more))
                            one)))))
    (%map-product (if (functionp function)
                      function
                      (fdefinition function))
                  (cons list more-lists))))

Answer 15

Apart from levy's answer, I decided to try writing a Common Lisp version too. I don't like my version very much, because of the need to modify the expansion "after the fact"; I'm a newbie, and could do with some tips on how to make it better. :-)

(defmacro nested-for (func &rest sets)
  (let* ((holder `(funcall ,func))
         syms
         (result holder))
    (dolist (set (nreverse sets))
      (let ((sym (gensym)))
        (push sym syms)
        (setq result `(dolist (,sym ,set) ,result))))
    (setf (cddr holder) syms)
    result))

Answer 16

Haskell, without using the List monad (which makes it too easy)

cartesianProduct [] = [[]]
cartesianProduct (heads:rest) = concatMap (\head -> map (head:) subProduct)
    where subProduct = cartesianProduct rest

Answer 17

APL (one-liner):

(Unicode characters in code snippet may not show in some browsers.)

x←'1' '2'
y←'a' 'b'
z←'A' 'B'
⎕←,x∘.,y∘.,z

Outputs:

 1aA  1aB  1bA  1bB  2aA  2aB  2bA  2bB

I'm using the outer product (∘.,) to combine three vectors to a matrix, then flatten the matrix (,) back to a vector. Finally, ⎕← shows the result.

Answer 18

In Python, with generators & recursion:

def nested_for(items):
    def _outer_product(depth, current):
        if depth == 1:
            return (current + [elem] for elem in items[-depth])
        else:
            return (res 
                    for elem in items[-depth]
                    for res in _outer_product(depth - 1, current + [elem]))
    if items:
        return _outer_product(len(items), [])
    else:
        return []

def apply_all(action, iterable):
    for elem in iterable:
        action(elem)

def action(elem):
    print elem

apply_all(action, nested_for([[1, 2], ['a', 'b'], ['A', 'B']]))

Answer 19

Haskell, for lists of different types:

[printf "%d %s %s\n" x y z | x <- [1, 2], y <- ["ab"], z <- ["AB"]]

For lists of lists:

cp []       =  [[]]
cp (xs:xss) =  [y:ys | y <- xs, ys <- cp xss]

printEm xs = mapM (putStrLn . intercalate " " . map show) (cp xs)

main = printEm [[1,2], [3,4], [5,6]]

Answer 20

Perl6

multi sub nested_join( String $join, String $join_line, Int :$index, Array *@data ){
  return undef unless @data.length;
  return undef unless $index < @data.length;
  $index //= 0;
  my @return;

  if( $index == @data.length -1 ){
    return @{@data[$index]};
  }else{
    my @lower = nested( $code, :index($index+1), @data );

    for @{@data[$index]} -> ($left) {
      for @lower -> $right {
        push @return, $left ~ $join ~ $right;
      }
    }
  }

  if( $index == 0 ){
    return join $join_line, @return;
  } else {
    return @return;
  }
}

multi sub nested_join( String $join, String $join_line, Array *@data ){
  nested_join( $join, $join_line, 0, @data );
}

print nested_join( ' ', "\n", [1, 2], ['a', 'b'], ['A', 'B'] );

Answer 21

Perl 6

Built in!

my @x = 1..2;
my @y = 'a'..'b';
my @z = 'A'..'B';

for @x X @y X @z -> $x, $y, $z {
    say "$x $y $z";
}

Cross operator X
for statement

addendum:
If using the cross operator multiple times or more than one loop variable is still cheating, you could get away with the following somewhat less sane solution that uses the reduction operator:

for @@( [X] \@x, \@y, \@z ) -> @slice {
    say @slice.join(' ');
}

Alternatively, to operate on a list of lists:

my @foo = \@x, \@y, \@z;
for @@( [X] @foo ) -> @slice {
    say @slice.join(' ');
}

Answer 22

Scala:

val nums = List(1, 2)
val lows = List('a', 'b')
val highs = List('A', 'B')

for (x <- nums; y <- lows; z <- highs) {
  printf("%s %s %s%n", x, y, z)
}

Or if you prefer:

for {
  x <- nums
  y <- lows
  z <- highs
} printf("%s %s %s%n", x, y, z)

The neat thing about this construct is not defined by Scala specifically for List, the transformation is more generic than that. In fact, it's even better than Java's enhanced for-loop, which works on all Iterable. Both of the above Scala snippets will be translated into the following higher-order invocations:

nums.foreach { x =>
  lows.foreach { y =>
    highs.foreach { z =>
      printf("%s %s %s%n", x, y, z)
    }
  }
}

This means that any type which declares foreach accepting a function of arity-1 as a single parameter can be used with Scala's imperative for-comprehensions as shown. Thus, you can do this for arrays, maps, sets, or even custom types. It's a lot like C#'s LINQ, and reasonably so considering they both have their roots in Haskell's do-notation.

Oh, and in case there was any ambiguity, this works for anything that declares foreach, thus including all supported collections (heterogeneous and homogeneous alike).

Answer 23

Scheme:

 (define-syntax foreach
  (lambda (x)
    (syntax-case x (=>)
      [(_ (v => l) ... e)
        (let ((p (map cons #'(v ...) #'(l ...))))
          (let f ((p p))
            (cond 
              [(null? p) #'e]
              [(null? (cdr p))
                #`(map (lambda (#,(caar p)) e) 
                    #,(cdar p))]
              [else
                #`(apply append 
                    (map 
                      (lambda (#,(caar p)) 
                        #,(f (cdr p))) 
                      #,(cdar p)))])))])))

    (foreach 
      [a  => '(1 2 3)]
      [b  => '(4 5 6)]
      (cons a b))

Answer 24

No LINQ sample, so here is one:

var query =
  from a in list1
  from b in list2
  from c in list3
  select new { a = a, b = b, c = c };

Answer 25

C# using delegates and anonymous methods

using System;
using System.Collections.Generic;

class MainClass
{

   delegate void Action(List<object> arguments);

   static void nestFor(Action action, List<object> arguments, List<List<object>> listOfLists)
   {
        if (listOfLists.Count == 0)
        {
            action(arguments);
            return;
        }
        List<object> targets = listOfLists[0];
        List<List<object>> newLol = new List<List<object>>(listOfLists);
        newLol.RemoveAt(0);
        foreach(object o in targets)
        {
            List<object> newArgs = new List<object>(arguments);
            newArgs.Add(o);
            nestFor(action, newArgs, newLol);
        }
   }

   public static void Main(string[] args)
   {
        List<List<object>> lol = new List<List<object>>();
        List<object> a = new List<object>(new object[]{0,1,2,3});
        List<object> b = new List<object>(new object[]{"a", "b", "c"});
        List<object> c = new List<object>(new object[]{"A", "B"});

        lol.Add(a); 
        lol.Add(b);
        lol.Add(c);

        nestFor(delegate(List<object> arguments) {
            arguments.ForEach( delegate(object o) { 
                Console.Write(o.ToString() + " ");
               });
            Console.WriteLine();
        }, new List<object>(), lol);
   }
}

Answer 26

Python 2.6

import itertools

def nested_for(func, *iterables):
    for item in itertools.product(*iterables):
        func(*item)

def print_em(*args):
    print " ".join("%s" % arg for arg in args)

nested_for(print_em, [1, 2], ['a', 'b'], ['A', 'B'])

Answer 27

Objective C:

First, the final output: 1 a A, 1 a B, 1 b A, 1 b B, 1 c A, 1 c B, 2 a A, 2 a B, 2 b A, 2 b B, 2 c A, 2 c B

Some of the matrix based approaches are interesting, but what happens when arrays have different numbers of elements?

Here's the code, recursive in nature (this first bit here I just included to show the data I initialized the array with):

NSMutableArray *allArrays = [NSMutableArray array];
[allArrays addObject:[NSArray arrayWithObjects:@"1", @"2", nil]];
[allArrays addObject:[NSArray arrayWithObjects:@"a", @"b", @"c", nil]];
[allArrays addObject:[NSArray arrayWithObjects:@"A", @"B", nil]];
[self doGatherResultsFromArray:allArrays 
                    baseString:@"" 
               performSelector:@selector(doPrintResult:)];

.....

  // Here's the method called when all the elements are together    
  - (void) doPrintResult:(NSString *)result  { NSLog(@"%@", result); }

  -(void) doGatherResultsFromArray:(NSArray *)currentArray baseString:(NSString *)baseString performSelector:(SEL)selector
  {
    if ( [currentArray count] == 0 )
      [self performSelector:selector withObject:baseString];
    else
      for ( NSObject *currentObject in [currentArray objectAtIndex:0] )
      {
        [self doGatherResultsFromArray:[currentArray subarrayWithRange:NSMakeRange(1, [currentArray count]-1 )] 
                            baseString:[NSString stringWithFormat:@"%@ %@", baseString, currentObject]
                       performSelector:selector];
      }
  }

Answer 28

Simple Java solution

public static void main(String[] args) {
    Object[][] arrayOfArrays = new Object[][] { { 1, 2 }, { "a", "b" }, { "A", "B" } };
    print(arrayOfArrays);

}

private static void print(Object[][] arrayOfArrays) {
    print("", arrayOfArrays, 0);

}

private static void print(String prefix, Object[][] arrayOfArrays, int start) {
    if (arrayOfArrays.length == start + 1) {
        for (Object o : arrayOfArrays[start]) {
            System.out.println(prefix + o);
        }
    } else {
        for (Object o : arrayOfArrays[start]) {
            print(prefix + o + " ", arrayOfArrays, start + 1);
        }
    }
}

Answer 29

Here's an Erlang version

nested(Fun, ListOfLists) ->
  nested(Fun, ListOfLists, {}).

nested(Fun, [], Current) ->
  Fun(Current);
nested(Fun, ListOfLists, Current) ->
  [List|T] = ListOfLists,
  lists:foreach(fun(Item) -> nested(Fun, T, erlang:append_element(Current, Item)) end, List).

And it would be called like:

nested(fun(Item) -> io:format("~w~n", [Item]) end, [ [1,2], ['a','b'], ['A', 'B']]).

Although to be honest, I would normally just use a list comprehension as follows:

lists:foreach(fun(Item) -> io:format("~w~n", [Item]) end, [{X,Y,Z} || X <- [1,2], Y <- ['a','b'], Z <- ['A', 'B'] ]).

Answer 30

using Linq's aggregate and select many

var a = new string[] { "1", "2" };
var b = new string[] { "a", "b" };
var c = new string[] { "A", "B" };

var result = new[] { a, b, c }.Aggregate<IEnumerable<String>>((l1, l2) => l1.SelectMany(s => l2, (s1, s2) => s1.ToString() + s2.ToString()));

foreach (var val in result)
    Console.WriteLine(val);

Anders should get a Nobel prize for the Linq thing!

Answer 31

Python, list comprehensions (useful for problems that can be translated to the map-reduce paradigm):

#totally random example made generic
#average length of words starting with 'a' in US and UK english
files = ['en_uk.dic', 'en_us.dic']
avg = lambda nums: sum(nums)/len(nums)
result = avg([len(word) for dictfile in files
                        for word in open(dictfile,'r').readlines()
                        if 'a' in word])

The ability to nest if statements as well makes this construct very powerful.