Introduction
Here is a simple algorithm (code) which given a pair of lists, one considered as an input and second as an output of some operation, finds a Mathematica function (or a group of functions) which can perform this operation. At this moment the algorithm is limited to finding functions which change the order of elements in a list (e.g. Sort, Reverse), change the number of its elements (e.g. Part, Join, Riffle) or modify its elements according to some numerical transformation applied to each of them (e.g. Plus, Power), without changing the structure (other dimensions than the length) of the list. However, adding new functions does not pose much of a problem and the system can be further extended. Programming by example is a potentially powerful way to do programming, and very easy for people with no programming experience. Try it here.
Results
The devised program (code) takes two lists as an input and returns a function (or a set of equivalent functions) which transform the first of the lists into the second one. During the program execution the user can be asked to provide the desired output given the example of an input generated additionally by the program. This is done to disambiguate the input. The functions are currently called from inside the AskFunction (which makes it easy to cloud-deploy it), but can be used as a normal functions.
After the program is run a prompt appears asking for an input list:
After this is provided, it asks for an output list:
If the program is still unsure about the transformation we want to perform, it will ask additional questions:
And eventually return the function:
Note that after we gave the first pair of lists, the scenario could have been different:
And then the returned function would be:
There are also examples where the program will return more than one function, because there are more than one way to perform the transformation in Mathematica:
Here a different example of an output, given lists: {1, 2, 3, 4} and {1, 2, 3}:
The program was cloud-deployed (webForm) for anyone who wants to test it.
How it works
The special equivalents of selected functions are implemented which return the built-in functions themselves (with the arguments and parameters specified based on the first input provided) and the outputs of these functions.
join[list_, example_] := Module[{input, output, rules, func},
input = example[[1]];
output = example[[2]];
rules = {
{s__, Sequence @@ input} :> With[{l = List[s]}, (Join[l, #]&)],
{Sequence @@ input, s__} :> With[{l = List[s]}, (Join[#, l]&)],
{s1__, Sequence @@ input, s2__} :> With[{l1 = List[s1], l2 = List[s2]}, (Join[l1, #, l2]&)]
};
func = output /. rules;
If[func === output, {{}, {}}, {{func}, {func[list]}}]
]
The arguments are: example_ - a tuple containing input and output given by the user, list_ - a test input which can be different from the first example given by the user.
Some of the functions are less general then others and can thus be inferred from the more generic functions (this is done using Mathematica patterns). For example, having the function written for Join operation (as shown above), there is no need to write similar functions for Append, Prepend, PadLeft or PadRight.
joinFunctionRule = {
Function[Join[Slot[_], elem_]] :> (Append[#, First[elem]]&) /; Length[elem] == 1,
Function[Join[elem_, Slot[_]]] :> (Prepend[#, First[elem]]&) /; Length[elem] == 1,
Function[Join[Slot[_], elem_]] :> With[{
pattern = elem /. {PatternSequence[patt__]..} :> List[patt],
elemLen = Length[elem]
},
If[Length[pattern] < elemLen,
If[Length[pattern] > 1,
(PadRight[#, Length[#] + elemLen, pattern]&),
(PadRight[#, Length[#] + elemLen, First[pattern]]&)
],
(Join[#, elem]&)
]
],
Function[Join[elem_, Slot[_]]] :> With[{
pattern = elem /. {PatternSequence[patt__]..} :> List[patt],
elemLen = Length[elem]
},
If[Length[pattern] < elemLen,
If[Length[pattern] > 1,
(PadLeft[#, Length[#] + elemLen, pattern]&),
(PadLeft[#, Length[#] + elemLen, First[pattern]]&)
],
(Join[elem, #]&)
]
],
Function[Join[elemL_, Slot[_], elemR_]] :> With[{
patternL = elemL /. {PatternSequence[patt__]..} :> List[patt],
patternR = elemR /. {PatternSequence[patt__]..} :> List[patt],
elemLLen = Length[elemL],
elemRLen = Length[elemR]
},
If[patternL === patternR && (Length[patternL] < elemLLen || Length[patternL] < elemRLen),
If[Length[patternL] > 1,
(PadRight[#, Length[#] + elemLLen + elemRLen, patternL, elemLLen]&),
(PadRight[#, Length[#] + elemLLen + elemRLen, First[patternL], elemLLen]&)
],
(Join[elemL, #, elemR]&)
]
]
};
The same situation with Part and Take, Drop, First, Last, Most, Rest:
partFunctionRuleF[example_] := {
Function[Part[Slot[_], l_?ListQ]] :>
With[{ind = l[[1]], n = Length[example[[1]]] - 1}, {#[[ind]]&, First, Take[#, 1]&, Drop[#, -n]&}] /;
(Length[l] == 1 && l[[1]] == 1),
Function[Part[Slot[_], l_?ListQ]] :>
With[{ind = l[[1]], n = Length[example[[1]]] - 1}, {#[[ind]]&, #[[-1]]&, Last, Take[#, -1]&, Drop[#, n]&}] /;
(Length[l] == 1 && l[[1]] == Length[example[[1]]]),
Function[Part[Slot[_], l_?ListQ]] :> With[{ind = l[[1]]}, #[[ind]]&] /; Length[l] == 1,
Function[Part[Slot[_], Span[i_, j_]]] :>
{#[[ ;; j]]&, #[[ ;; -2]]&, Take[#, j]&, Most, Drop[#, -1]&} /; (i == 1 && j + 1 == Length[example[[1]]]),
Function[Part[Slot[_], Span[i_, j_]]] :>
With[{ind1 = Length[example[[1]]] - j + 1, ind2 = j + 1},
{#[[ ;; j]]&, #[[ ;; -ind1]]&, Take[#, j]&, Drop[#, ind2]&}
] /; i == 1,
Function[Part[Slot[_], Span[i_, j_]]] :>
With[{ind = j - 1}, {#[[i ;; ]]&, Take[#, -ind]&, Rest, Drop[#, 1]&}] /; (i == 2 && j == Length[example[[1]]]),
Function[Part[Slot[_], Span[i_, j_]]] :>
With[{ind1 = j - i + 1, ind2 = i - 1},
{#[[i ;; ]]&, #[[-ind1 ;; ]]&, Take[#, -ind1]&, Drop[#, ind2]&}
] /; j == Length[example[[1]]],
Function[Part[Slot[_], Span[i_, j_]]] :> {#[[i ;; j]]&, Take[#, {i, j}]&}
}
The numerical transformations changing the elements of lists are searched taking advantage of Mathematica built-in function: FindFormula.
findFormula[list_, example_] := Module[{formula},
formula = FindFormula[Transpose[example]];
{{formula}, {formula[list]}}
]
The search is done by probing all of the defined functions. Because the input can be ambiguous, a set of random inputs is generated and the functions are run on this set. One of the input is selected based on how well it divides the space of possible functions and it is issued to the user with question on what would be the output of a desired operation given the input provided. The user enters the output, which is then matched to the outputs given by the functions and only functions with matched output are considered further. This step is repeated until the right set of functions is found or until program acknowledges that it cannot find the transformation. The input which best divides the space of possible functions is chosen by the principle of maximal entropy. The entropy for a given input is calculated based on the probability of receiving specific output given this input. The probabilities are calculated upon the outputs given by the functions being checked at a given step of the program execution.
entropy[examples_] := -N[
Total[
Map[# Log2[#]&,
Map[Last, Tally[examples]] / Length[examples]
]
]
]
Future directions
At this moment the devised function is not able to recognize transformations which change dimensions of arrays other than their length (e.g. ArrayReshape, Partition) and cannot propose any complex transformation (transformation performed by more then one Mathematica functions applied in a row).
The next step is to add the dimensions-changing functions to the system. After this is done the search for complex transformations can be introduced - using the elements implemented for simple functions and asking additional questions to the user.
The whole system can be of course generalized to account for other than only list operations. The next transformations added would be string transformations.
