Combinations of more things

You probably noticed that allCombs3 is getting painful to write. Worse still, it does not help us generate combinations of four or more things. We need to take a different approach if we want this to scale easily. This is a difficult step, so we are not going to make you figure it out yourself. All the same, spend some time thinking about how you might do it. Here is a hint though. You probably noticed that allCombs has ([a] -> [b]) in its type signature and allCombs3 has ([a] -> [b] -> [c]) in its type signature. When you are playing with this, do not try to generalize that pattern to [[a]]. That is not an adequate generalization because it only allows a and has no b or c anywhere. Spend some time thinking about this before you continue. But don’t be discouraged if you can’t figure it out. This one is hard.

Back? If you figured it out, congratulations. If not, here is the hex encoded type signature for a function called combStep that is the generalization we need.

636F6D6253746570203A3A205B61202D3E20625D202D3E205B615D202D3E205B625D

Now write that function. Then use the combStep function to implement allCombs and allCombs3 and check that the new implementations have the same behavior as before. Once you do this it should be pretty obvious how you would use combStep to implement allCombs4 and beyond. Also notice how combStep compares to allCombs.

Previous Page - Next Page