I'm implementing Okasaki's O(log N) random access list, using the Hongwei Xi's ATS implementation as a basis:
https://github.com/githwxi/ATS-Postiats/blob/master/libats/DATS/funralist_nested.dats The advantage of this is that the ATS version uses dependent typing to prove correctness, so the Felix version should be correct too if I transcribe it faithfully. The routine is tricky to get right without the extra strength of the ATS dependent typing. However this re-raises an issue. This data structure has two functions: cons (v, ralist) uncons (ralist, &head, &tail) A functional version of uncons would be uncons[T]: ralist[T] -> T * ralist[T] This is roughly a pattern match like: match uncons xss with | (?head, ?tail) => .... However, this does not nest. For example the xss list were inside a tuple: match (1,xss,2) with | (?one, ?lst, ?two) => match uncons lst with | (?head, ?tail) =:> ... would be needed. Note the empty state wasn't checked! What we really need is more like: match 1,xss,2 with | ?one, uncons#(?head, ?tail).?two => ... which means to match the tuple produced by unconsing the component of the match argument. Because this nests. If instead an optional head were returned so uncons is total: | uncons#(None, ?tail) => empty case ... | uncons#(Some ?head, ?tail) => nonempty case However, Felix matching doesn't quite work like this. Instead there are TWO functions: (a) a match checker, which determines if a pattern or subpattern matches (b) a match handler, which extracts the variable values Switching cases of he match is determined by (a) which is a simple boolean function. So I think two functions are needed not one, or, at least one which returns an option type, which would unfortunately get applied twice (once to check if there's a result and once to calculate it). At present no form of "user defined pattern matching" is possible. However other languages like C# allow this using object method calls. The match handling code will need to be rewritten to handle dynamic patterns. This is not so easy because it happens long before type checking. Just as an example the tuple pattern: match .. v ... with | ... (?h,?t) ... => ... is done by h = v .projection_0, t = v.projection_1 So a nested match: (?h1,(?h2,?t)) is h1 = v. projection_0 h2 = v.projection_1.projection_0 t = v.projection_1.projection_1 so the list of operators applied to the original argument is a just a path down the tree structure of the match argument. It follows any value which can be decomposed by any set of function paths can be matched with a single pattern, provided there's a consistent way to name the functions which define the paths. The "tree" or "nesting" structure of the pattern just reflects common prefix merging. -- john skaller skal...@users.sourceforge.net http://felix-lang.org ------------------------------------------------------------------------------ Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS, MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft MVPs and experts. ON SALE this month only -- learn more at: http://p.sf.net/sfu/learnmore_122712 _______________________________________________ Felix-language mailing list Felix-language@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/felix-language
