A conservative approximation of which patterns do not discern anything. They are discarded during the translation.

The translation of pat if guard => body has two aspects: 1) the substitution due to the variables bound by patterns 2) the combination of the extractor calls using flatMap.

2) is easy -- it looks like: translatePattern_1.flatMap(translatePattern_2....flatMap(translatePattern_N.flatMap(translateGuard.flatMap((x_i) => success(Xbody(x_i)))))...) this must be right-leaning tree, as can be seen intuitively by considering the scope of bound variables: variables bound by pat_1 must be visible from the function inside the left-most flatMap right up to Xbody all the way on the right 1) is tricky because translatePattern_i determines the shape of translatePattern_i + 1: zoom in on translatePattern_1.flatMap(translatePattern_2) for example -- it actually looks more like: translatePattern_1(x_scrut).flatMap((x_1) => {y_i -> x_1._i}translatePattern_2)

x_1 references the result (inside the monad) of the extractor corresponding to pat_1, this result holds the values for the constructor arguments, which translatePattern_1 has extracted from the object pointed to by x_scrut. The y_i are the symbols bound by pat_1 (in order) in the scope of the remainder of the pattern, and they must thus be replaced by: - (for 1-ary unapply) x_1 - (for n-ary unapply, n > 1) selection of the i'th tuple component of x_1 - (for unapplySeq) x_1.apply(i)

in the treemakers,

Thus, the result type of translatePattern_i's extractor must conform to M[(T_1,..., T_n)].

Operationally, phase 1) is a foldLeft, since we must consider the depth-first-flattening of the transformed patterns from left to right. For every pattern ast node, it produces a transformed ast and a function that will take care of binding and substitution of the next ast (to the right).

Implement a pattern match by turning its cases (including the implicit failure case) into the corresponding (monadic) extractors, and combining them with the orElse combinator.

For scrutinee match { case1 ... caseN }, the resulting tree has the shape runOrElse(scrutinee)(x => translateCase1(x).orElse(translateCase2(x)).....orElse(zero))

NOTE: the resulting tree is not type checked, nor are nested pattern matches transformed thus, you must typecheck the result (and that will in turn translate nested matches) this could probably be optimized... (but note that the matchStrategy must be solved for each nested patternmatch)