Friday, July 10, 2015

How to See the Equivalence of Select and Cases

MatchQ and PatternTest Equate Cases and Select

Select and Cases are essential Mathematica filtering functions. Select filters expressions, usually Lists, with predicates, such as ones that end with Q (evaluate ?*Q to see them) or those that don't, such as Greater, Less, and others that I list here. Cases uses patterns such as testing for a Head (e.g. _Integer) or a more general pattern (e.g. for a 2-element List, {x_,y_}.

Cases and Select are equivalent and a versatile Mathematica programmer knows how to use either one in any circumstance according to the need of the moment. The keys to seeing their equivalence are MatchQ, which translates a pattern into a predicate, and PatternTest (_?test), which translates a predicate into a pattern.

MatchQ[4.1,_Real]

True

MatchQ[{2,2.1},{_Integer,_Real}]

True

Thus you can take any usage of Cases and translate it into Select.

Cases[{a,4,4.2,6,7.5,8},x_Integer/;x>4]

{6,8}

integerGreaterThan4Q@n_:=MatchQ[n,_Integer&&n>4];
Select[{a,4,4.2,6,7.5,8},integerGreaterThan4Q]

{6,8}

And you can take any usage of Select and translate it into Cases.

Select[{1,2,4,7,6,2},EvenQ]

{2,4,6,2}

Cases[{1,2,4,7,6,2},_?EvenQ]

{2,4,6,2}

If we built our own predicate for EvenQ using MatchQ, it works the same way.

Select[{1,2,3,4},MatchQ[#/2,_Integer]&]

{2,4}

However note the need for parentheses around the test, which is often the case with PatternTest - the no parens usage fails.

Cases[{1,2,3,4},_?(MatchQ[#/2,_Integer]&)]

{2,4}

Cases[{1,2,3,4},_?MatchQ[#/2,_Integer]&]

{}

The reason is that Blank and PatternTest both have a higher Precedence ('stickiness') than Function, and so they stick together and PatternTest ends up inside the pure Function instead of using the pure Function as the pattern test. You don't need to worry about that — just as a rule of thumb put parens around any 'homemade' test.

Precedence/@{PatternTest,Blank,Function}

{680.,730.,90.}

The Q Predicates


This is a handy way to use Partition, especially using {} so a final short sublist won't be dropped from a 'ragged' List. The syntax says

Partition[list, sublist length, offset length, start Position, padding]

and here means divide the List into Partitions of length 4, moving the window that same length 4 with each Partition so there is no overlap, start the List at Position 1,  and the empty set {} for padding tells Partition to return the final sublist even if it's shorter than what is specified by the 2nd argument, and don't pad that final short list. Evaluate this code in your Notebook:

Qpredicates=Names@"*Q";
Print@Length@Qpredicates;
Partition[Qpredicates,4,4,1,{}]//TableForm

Here's the same result in a List.

Names@"*Q"

{AcyclicGraphQ,AlgebraicIntegerQ,AlgebraicUnitQ,AntihermitianMatrixQ,AntisymmetricMatrixQ,ArgumentCountQ,ArrayQ,AssociationQ,AtomQ,BinaryImageQ,BipartiteGraphQ,BooleanQ,BoundaryMeshRegionQ,BoundedRegionQ,BusinessDayQ,ColorQ,CompatibleUnitQ,CompleteGraphQ,CompositeQ,ConnectedGraphQ,ConstantRegionQ,ContinuousTimeModelQ,ControllableModelQ,CoprimeQ,DateObjectQ,DaylightQ,DayMatchQ,DeviceOpenQ,DiagonalizableMatrixQ,DigitQ,DirectedGraphQ,DirectoryQ,DiscreteTimeModelQ,DisjointQ,DispatchQ,DistributionParameterQ,DuplicateFreeQ,EdgeCoverQ,EdgeQ,EllipticNomeQ,EmptyGraphQ,EulerianGraphQ,EvenQ,ExactNumberQ,FileExistsQ,firedQ,FreeQ,GeoWithinQ,GraphQ,GroupElementQ,HamiltonianGraphQ,HermitianMatrixQ,HypergeometricPFQ,ImageQ,IndefiniteMatrixQ,IndependentEdgeSetQ,IndependentVertexSetQ,InexactNumberQ,integerGreaterThan4Q,IntegerQ,IntersectingQ,IntervalMemberQ,InverseEllipticNomeQ,IrreduciblePolynomialQ,IsomorphicGraphQ,KEdgeConnectedGraphQ,KeyExistsQ,KeyFreeQ,KeyMemberQ,KnownUnitQ,KVertexConnectedGraphQ,LeapYearQ,LegendreQ,LetterQ,LinkConnectedQ,LinkReadyQ,ListQ,LoopFreeGraphQ,LowerCaseQ,MachineNumberQ,ManagedLibraryExpressionQ,MandelbrotSetMemberQ,MarcumQ,MatchLocalNameQ,MatchQ,MatrixQ,MemberQ,MeshRegionQ,MixedGraphQ,MultigraphQ,NameQ,NegativeDefiniteMatrixQ,NegativeSemidefiniteMatrixQ,NormalMatrixQ,NumberQ,NumericQ,ObservableModelQ,OddQ,OptionQ,OrderedQ,OrthogonalMatrixQ,OutputControllableModelQ,PartitionsQ,PathGraphQ,PermutationCyclesQ,PermutationListQ,PlanarGraphQ,PolynomialQ,PositiveDefiniteMatrixQ,PositiveSemidefiniteMatrixQ,PossibleZeroQ,PrimePowerQ,PrimeQ,ProcessParameterQ,QHypergeometricPFQ,QuadraticIrrationalQ,QuantityQ,RegionQ,RegularlySampledQ,RootOfUnityQ,SameQ,SatisfiableQ,ScheduledTaskActiveQ,SimpleGraphQ,SquareFreeQ,SquareMatrixQ,StringFreeQ,StringMatchQ,StringQ,SubsetQ,SymmetricMatrixQ,SyntaxQ,TautologyQ,TensorQ,TreeGraphQ,TrueQ,UnateQ,UndirectedGraphQ,UnitaryMatrixQ,UnsameQ,UpperCaseQ,URLExistsQ,ValueQ,VectorQ,VertexCoverQ,VertexQ,WeaklyConnectedGraphQ,WeightedGraphQ}


Two excellent introductions to Mathematica:

Wednesday, July 8, 2015

New in Mathematica 10: Associations as General-Purpose Associative Arrays

Associations are the most important data structure introduced in Mathematica in years. As the Guide says:

Along with lists, associations are fundamental constructs in the Wolfram Language. They associate keys with values, allowing highly efficient lookup and updating even with millions of elements. Associations provide generalizations of symbolically indexed lists, associative arrays, dictionaries, hashmaps, structs, and a variety of other powerful data structures. 

They of course will underlie databases and artificial intelligence data structures. They are intended to replace less structured expressions such as pairs in Lists or Rules. The code written for Association functions has been highly optimized for speed. I suspect that Associations are the core data structure of the Wolfram Alpha natural language processor, which is the front end for the curated data collections in Alpha, just as the Notebook is the front end for the kernel.

So when I needed a lookup table today I decided to try Associations. Here are some simple functions that define an axon's threshold in terms of the stimulating pulse seen at the axon, according to the Lapicque equation Vth = Vrh(1+τch/pw).

(You don't need to understand these!)

absoluteRheobase@fiberDiameter_:=0.000589+0.01518 Exp[-fiberDiameter/2.3477]

chronaxie@fiberDiameter_:=102.764 +162.46744 Exp[-fiberDiameter/5.53435];

absoluteThreshold=.;absoluteThreshold[pulseWidth_,fiberDiameter_]:=Module[{},absoluteRheobase@fiberDiameter(1+chronaxie@fiberDiameter/pulseWidth)]

Now since fiber threshold is driven by their diameter and the pulse width of the stimulating pulse, we make sample tables of those. Esc + m + esc gives us the mu in microseconds and micrometers; no need to open a Palette.

pulseWidthTable50to500=Table[pw,{pw,100,500,100}] (* in μs *);

fiberDiameters1to15=Table[diameters,{diameters,5,10}] (* in μm *);

Now here is the function that creates the Associations. It took a bit of fiddling, but by making a Table of Rules in one step as should be done with good functional programming, it is then easy to Apply Association to the entire Table, simply replacing the Head, List, with Association, which converts the List of Rules into an Association. In the Table pulseWidth is the "i" iterator and fiberDiameter is the "j" iterator, and notice that we don't need to iterate numerically from 1 to Length@pulseWidthTable50to500, for example, we just directly iterate over the List itself, which is simpler.

absoluteThresholdTable=Association@@Table[Rule[{pulseWidth,fiberDiameter},absoluteThreshold[pulseWidth,fiberDiameter]],{pulseWidth,pulseWidthTable50to500},{fiberDiameter,fiberDiameters1to15}]

<|{100,5}->0.00642849,{100,6}->0.00455515,{100,7}->0.00337826,{100,8}->0.00263167,{100,9}->0.00215327,{100,10}->0.00184348,{200,5}->0.00441095,{200,6}->0.00316135,{200,7}->0.00236852,{200,8}->0.00186172,{200,9}->0.00153533,{200,10}->0.00132348,{300,5}->0.00373844,{300,6}->0.00269675,{300,7}->0.00203194,{300,8}->0.00160507,{300,9}->0.00132935,{300,10}->0.00115015,{400,5}->0.00340218,{400,6}->0.00246445,{400,7}->0.00186364,{400,8}->0.00147675,{400,9}->0.00122636,{400,10}->0.00106348,{500,5}->0.00320043,{500,6}->0.00232507,{500,7}->0.00176267,{500,8}->0.00139975,{500,9}->0.00116456,{500,10}->0.00101149|>

Here are several versions of lookup functions. The first one just uses the same syntax as we'd use to access elements of an associative array made with function@value, such as we'd construct with a memo function.

Clear@thresholdLookup; 
thresholdLookup[lookupTable_Association, pulseWidth_Integer, diameter_] := lookupTable@{pulseWidth, diameter}

absoluteThresholdTable@{100, 7}

0.00337826

Likely it's safer and more elegant to use the new Lookup function instead.

Clear@thresholdLookup2; 
thresholdLookup2[lookupTable_Association, pulseWidth_Integer, diameter_] := Lookup[lookupTable, {{pulseWidth, diameter}}]

thresholdLookup2[absoluteThresholdTable, 100, 7]

{0.00337826}

We see that using a List as the Key results in returning a List as the Value, like in solutions for equations returned by Solve, etc. So to access the Value we can use First@key to remove the List brackets, as we often do with solutions to equations.

Clear@thresholdLookup3; 
thresholdLookup3[lookupTable_Association, pulseWidth_Integer, diameter_] := Lookup[lookupTable, {{pulseWidth, diameter}}] // First

thresholdLookup3[absoluteThresholdTable, 100, 7]

0.00337826

Years ago I talked to Stephen Wolfram at an artificial life conference about artificial intelligence and his views were kind of naive. Things have changed. I expect that Mathematica and its Wolfram Language are headed inexorably toward large-scale AI applications,  approaching, and exceeding in some respects, human intelligence over the next two decades.