Side effects – Don’t leave home without them

For me, one of the coolest things about functional programming languages is using [arglist] pattern matching and recursion to concisely express an algorithm. However, there are other ways to juice the pomegranate. I was staring at the Pure code for zip/unzip and there is a lot of it (for a seemingly simple function). I was surprised. There is some short list checking (which I punt on) but there are pair and triple versions (Haskell has 3 .. 7 versions). I noticed that while zip and unzip are basically the same thing (zip takes lists, unzip takes a list of lists), the code is pretty different for each.

After a bunch of head scratching, I was able to implement versions that are basically the same code and handle all input “widths” (pairs, triples, quads, …). The following were key:

  • All methods & functions are variadic, the number of parameters is never fixed. This means I just look at the arg count to determine if it is zip2, zip3, zip4, etc.
  • Late binding. Methods are bound to their instance. So, if foo and bar are lists, foo.reduce and bar.reduce are unique methods, even though they perform the same operation on a list. Late binding allows me to call a method on an arbitrary object when that object is not known at compile time.
  • Implicit-ish looping. This algorithm is basically a nested loop processing a list while processing a list. The “reduce” method (aka foldl) keeps a rolling sum, which can be used as an loop value (index in this case).
  • Side effects. Mutable lists are used as “accumulators” to build the results.

    // zip(a,b…) –>
    //   L( L(a[0],b[0]…), …,  L(a[n],b[n]…) )
    // zip(L(1,2),L(3,4),L(5,6)) –> L( L(1,3,5), L(2,4,6))
    // zip is unzip(vm.arglist)
fcn listZip(lists){
   results := T.build(lists.len(),0,List);
   vm.arglist.apply2(“reduce”,
      fcn(n,x,results){results[n].append(x); n+1},0,results);
   results;
}

    // unzip(L(L(1,2),L(3,4),L(5,6))) –> L( L(1,3,5), L(2,4,6))
    // unzip(unzip(a)) –> a
    // unzip is zip(listOfLists.xplode())
fcn listUnzip(listOfLists){
   results := // T(L1(),L2() … Ln())
       T.build(listOfLists[0].len(),0,List);
       // L( L(1,3,5) ) –> T(L(1),L(3),L(5))
   listOfLists.apply2(“reduce”,
      fcn(n,x,results){results[n].append(x); n+1 },0,results);
   results;
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s