Matching against STL containers and ranges

[solodon4]

C++ containers are harder to decompose because they are not recursive data structures (not expressed in their own terms, not containing an instance of themselves like lists and trees in functional programming would). This was the subject of slides 66 and 67 of my C++ Now talk: http://bit.ly/Mach7CppNow

To explain the slides there: a recursive list is easy to decompose with nested matching, e.g.:

Case(C<List>(head, C<List>(nexthead, tail))) ...

However std::list<T> is not recursive, so it is not applicable to it.

Ranges are also not recursive, but at least they conceptually can reflect part of themselves, so I think we should be able to build patterns for matching against ranges. I started working on such a pattern (I called it sequence pattern: https://github.com/solodon4/Mach7/blob/master/code/patterns/sequence.hpp), however there was something else I still had to resolve on the level of idea, so I don't think I have yet an example of their usage. The idea was to let that pattern match against arbitrary number of elements and then accept as the last pattern something that would be capable of matching against the range of remaining (not yet matched elements). As such I added 'all' and 'exist' patterns, whose example usage can be found on lines 406 and 408 here:

https://github.com/solodon4/Mach7/blob/master/code/prolog-pat2.cpp#L406

In other words, it is very easy to create pattern that would match against first n elements of a container with its n sub-patterns. It is not clear what to do with the remaining elements after n as we would ideally want to forward the computation to them after decomposition through pattern matching (fold).

Besides the sequence pattern, I was also trying to experiment with syntaxes for other patterns capable of matching multiple elements, as for example, on commented-out lines 460 and 461 in the same file, but that didn't quite work, so I don't have a good solved story for STL containers yet.

[ghost]

Hi @solodon4,

Any update on this? This would greatly simplify my pattern matching use cases, as I would like to pattern-match on specific scheme lists without having to write nested C<Pair>(...)s all over again. A search returned only this issue for me.

I'd like to take this moment to say thank you for your awesome work. Already it has saved me tonnes of time.

Regards, Sam

[solodon4]

Hi Sam,

Can you please provide a few examples of what you have to do today? Also if you can elaborate on what you'd like to be able to match, I might be able to help you without having to have the solution for all containers.

Cheers! Yuriy

[ghost]

Hi @solodon4,

My apologies, I have been busy and the issue has slipped my mind. I'll make a repository public with the code I'm currently working on, so you can see for yourself. First it needs some updating, though.

Regards, Sam