Analytical expressions are derived for the first-order correction to the effective slip length of a weakly shear-thinning Carreau-Yasuda fluid in both longitudinal and transverse semi-infinite shear flow over a unidirectional superhydrophobic surface of flat no-shear slots. The formulas, which are derived using suitably generalized forms of the standard reciprocal theorem for Stokes flow, are given by explicit integrals which require only numerical quadrature for their evaluation. For both longitudinal and transverse flow we find that for a given no-shear fraction of the superhydrophobic surface and a given power-law index characterizing the Carreau-Yasuda fluid, there is a critical imposed strain rate of the shear at which the enhancement of effective slip is maximal. The theoretical results are qualitatively consistent with recent numerical work by other authors for the transverse case.