Here I am, continuing my foray into the realm of array programming, that started in my previous post. Let me start with a disclaimer: I do not claim that what you read here is good, idiomatic J.This is not a J tutorial. I mean it as an exposé of the notions of array programming and how they can enhance the worldview of the traditional programmer. I’d love it if it could also be a bridge between mainstream FP and Array Programming, but I’m afraid I’m not sufficiently proficient in either to do it.
Remember the last five lines of code? I’m going to dissect them now for your benefit.
NB. Locations (mask bits) where digits have lines digitmasks =. ' ' ~:"(1) (,"2 digits)
Laid out, this means: concatenate all lines in each digit (keeping them in three lines serves only for displaying them). This is done by , (called append), applied to cells of digits of rank 2 (the "2 modifier, called an conjunction in J). Then, compare lines (cells of rank 1, the "1 thing) of that, using the “not equals” comparator (the ~:) to a literal with 9 spaces.
This gives you a bit (an 1) whenever there’s anything than a space. I can do that because the digits, as defined, when they share a graphic element, it’s always the same in the same location. So I’m getting rid of some excessive information to make my life easier. So, digitmasks is the following.
0 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1
NB. Locations where digits share mask bits maskcompmatrix =. (-"1/~ digitmasks) ="0 ] 0
Moving on, first, I make a table where, I subtract each line (i.e. digit bitmask) from each other. The -"1/~ digitmasks thing is shorthand for digitmasks -"1/ digitmasks, i.e. tabulate (the / adverb – another kind of higher-level construct, like conjunctions – for a dyadic operation) the operation “subtract each line” (the -"1). Afterwards, the whole thing is compared, bit by bit (the ="0) to zero. The result is a 10 x 10 x 9 bitmask array. Are you getting the hang of it?
NB. Count of similar mask bits between digits diffmatrix =. +/"1 maskcompmatrix
Further, I sum: insert, using the / adverb, the operation “plus” (the + verb) at the level of each line (the "1 conjunction) on maskcompmatrix. This gives a 10 x 10 array of the number of same bits in each bitmask (digit).
9 5 6 6 5 6 7 6 8 7 5 9 4 6 7 4 3 8 4 5 6 4 9 7 4 5 6 5 7 6 6 6 7 9 6 7 6 7 7 8 5 7 4 6 9 6 5 6 6 7 6 4 5 7 6 9 8 5 7 8 7 3 6 6 5 8 9 4 8 7 6 8 5 7 6 5 4 9 5 6 8 4 7 7 6 7 8 5 9 8 7 5 6 8 7 8 7 6 8 9
Now comes the easy part.
NB. Outside the diagonal: Digits that share 8 out of 9 mask bits offbyone =. diffmatrix ="(0) 8
I make a 10 x 10 array of selectors (bits) when digits share 8 out of 9 bits.
offbyones =. (monad : '< y # i. 10')"1 offbyone
Then, I make a vector (list, in J) of which digits share 8 bits for each digit.
┌─┬─┬┬─┬┬───┬───┬─┬─────┬─────┐ │8│7││9││6 9│5 8│1│0 6 9│3 5 8│ └─┴─┴┴─┴┴───┴───┴─┴─────┴─────┘
I wanted to spare you (and me!) the trouble of bringing up “boxing” but, since the shape is irregular, it was really the easiest solution. Boxing (conveniently displayed with actual boxes) creates an atomic value of anything you put into it.
And, in reality, I found out that it makes calculations simpler if the digits themselves are included, so I really need the following.
NB. Digits that share 8 or 9 (i.e. themselves) mask bits sameandoffbyone =. diffmatrix >:"(0) 8 sameandoffbyones =. (monad : '< y # i. 10')"1 sameandoffbyone
┌───┬───┬─┬───┬─┬─────┬─────┬───┬───────┬───────┐ │0 8│1 7│2│3 9│4│5 6 9│5 6 8│1 7│0 6 8 9│3 5 8 9│ └───┴───┴─┴───┴─┴─────┴─────┴───┴───────┴───────┘
This was sort of easy, wasn’t it? I’m afraid the rest will be a little more complicated. I’ll throw it all in one glob, and focus on the big picture first. The operation I’m trying to achieve, is fix broken account numbers by trying similar digits, where similar is defined by off-by-one bit.
NB. fold operation to produce the combinations
foldop =. dyad : ',/ <"1 (>y) ,"1/ (,. >x)'
identity =. <''
NB. Use if checksum is <> 0: try combinations with digits off by one mask bit and see which (if any) produce checksum of 0
alternatives =. monad define
alt =. >"0 foldop/ identity ,~ |. y { sameandoffbyones
((checksum"1 = 0:) alt) # alt
)
There’s a fold taking place, which is a common thing in FP. The first complication is that, in J, for reasons of uniformity with its right-to-left evaluation order, when you fold a list (remember, a list is a vector of something) you also do it right-to-left. That’s why I reverse (the |. thing) the result of indexing (the {) sameandoffbyones by the account digits (y stands for the argument in a monadic verb). Then I append the identity element, which is a boxed empty list. Folding takes place, and I’ll explain the operation folded next but, for now, let’s stick to what the fold produces, which is a list of boxed candidate account numbers, which are unboxed (the >"0) and then checked with checksum (the checksum"1 = 0: is actually a composite verb!) and only those with zero checksum are kept (operation copy, the #).
Example usage:
alternatives 2 4 4 4 1 2 5 6 7
2 4 4 4 1 2 5 6 1 2 4 4 4 1 2 9 8 7 2 4 4 4 7 2 6 6 1
However, don’t try it on 7 2 3 4 5 6 7 8 9. It produces 109 possible alternatives! In retrospect, this error correction policy is not very robust or, rather, the checksum used in not suitable to how digits can be misread.
Let’s go back to the folded operation now. I won’t go into it symbol-by-symbol but here’s an English description. One operand holds a list of boxes with partial account numbers, and the result is also a list of boxes with longer partial account numbers, formed by appending the initial partial account numbers with all alternatives for the current digit, held by the other operand as a boxed list.
Have I picked your curiosity until now? Have I succeeded in presenting J as more than a curiosity itself? There is real power in its notions and it goes beyond its conciseness. Imagine all these operations using standard Scala, for example. “It’s easy if you try.” I think it is a useful thing to add to standard FP, which lacks the language to talk about arrays at the level that array programming languages do. I have not even found a data type to represent arbitrary-ranked arrays, let alone how to represent ranked operations and implicit loops and stuff. But I think it can be done, and I’m setting it as a wanna-do-it for the future.
dsouflis 