In the worked out version of the |subs_asc| function in the test we select the sublist of the rest of the list which have a higher starting value than the value we want to prepend. If we keep the list of ascending sequences sorted, we can have a somewhat more efficient version. Write this version.
Instead of building the lists directly we can also build a tree which has the property that each paths from the root to a leaf represents one of the ascending subsequences of the list:
- define an appropriate tree type for representing such paths
- write the function which builds this tree out of a list
- can you say something about the size of the structure which is represented in memory?
Can you generalise the memoisation approach to functions which take e.g. two =Int='s as a parameter? And three?