Re: [Chicken-users] matchable egg usage question
Hi, Alex! Are the new matchable extensions documented in the wiki? if not, could you update it? cheers, felix ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Sun, Jan 30, 2011 at 1:40 PM, Alex Shinn wrote: > > Because it searches for patterns where the head of the tree > at each step along the path matches _, and the leaf matches > '(bar 1). The head is not searched as a potential leaf. Sorry, whether the head is checked as a leaf or not is irrelevant in this case - the node must either be a list with a matching head pattern, or the leaf pattern. In this case it doesn't match the leaf, so the entire head (a (b (bar 1))) is matched as _, and then the tail of () recursively searched (and fails). It won't match one pattern and then recursively search within the matched value for other patterns. -- Alex ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Sun, Jan 30, 2011 at 1:33 PM, Alan Post wrote:
>
> Wonderful! This is working for the test cases I sent, but it
> doesn't seem to work when I have a list where the first element
> is also a list:
>
> (pretty-print (map
> (match-lambda
> (('foo (_ *** '(bar 1))) #t)
> (_ #f))
> '((foo (bar 1))
> (foo (a (bar 1)))
> (foo (a (b (bar 1
> ; these three fail
> (foo ((a (b (bar 1)
> (foo (a ((b (bar 1)
> (foo (a (b ((bar 1
>
> I don't understand why the last three examples fail to match the
> pattern here. I would expect them all to match, or if that weren't
> true I'd expect all but the last one to match.
Because it searches for patterns where the head of the tree
at each step along the path matches _, and the leaf matches
'(bar 1). The head is not searched as a potential leaf.
That's a somewhat arbitrary decision, but works well with the
intended use case which is matching SXML (where the head
is always a symbol).
--
Alex
___
Chicken-users mailing list
Chicken-users@nongnu.org
http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Sun, Jan 30, 2011 at 12:28:00PM +0900, Alex Shinn wrote:
> On Sun, Jan 30, 2011 at 12:09 PM, Alan Post
> wrote:
> >
> > Alex, will you explain what I'd doing wrong here using
> > tree searching patterns?
> >
> > (pretty-print (map
> > (match-lambda
> > (('foo *** '(bar 1)) #t)
> > (_ #f))
> > '((foo (bar 1))
> > (foo (a (bar 1)))
> > (foo (a (b (bar 1
> > (foo (a (b (c (bar 1
> >
> > Only the first form |(foo (bar 1))| is returning #t here.
> > The remaining forms return #f. I would expect all of them
> > to return true, based on my naive understanding of the ***
> > operator.
>
> 'foo has to match every step of the path. It sounds
> like you want
>
> ('foo (_ *** '(bar 1)))
>
Wonderful! This is working for the test cases I sent, but it
doesn't seem to work when I have a list where the first element
is also a list:
(pretty-print (map
(match-lambda
(('foo (_ *** '(bar 1))) #t)
(_ #f))
'((foo (bar 1))
(foo (a (bar 1)))
(foo (a (b (bar 1
; these three fail
(foo ((a (b (bar 1)
(foo (a ((b (bar 1)
(foo (a (b ((bar 1
I don't understand why the last three examples fail to match the
pattern here. I would expect them all to match, or if that weren't
true I'd expect all but the last one to match.
-Alan
--
.i ko djuno fi le do sevzi
___
Chicken-users mailing list
Chicken-users@nongnu.org
http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Sun, Jan 30, 2011 at 12:09 PM, Alan Post wrote:
>
> Alex, will you explain what I'd doing wrong here using
> tree searching patterns?
>
> (pretty-print (map
> (match-lambda
> (('foo *** '(bar 1)) #t)
> (_ #f))
> '((foo (bar 1))
> (foo (a (bar 1)))
> (foo (a (b (bar 1
> (foo (a (b (c (bar 1
>
> Only the first form |(foo (bar 1))| is returning #t here.
> The remaining forms return #f. I would expect all of them
> to return true, based on my naive understanding of the ***
> operator.
'foo has to match every step of the path. It sounds
like you want
('foo (_ *** '(bar 1)))
--
Alex
___
Chicken-users mailing list
Chicken-users@nongnu.org
http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Sat, Jan 29, 2011 at 11:23:54AM +0900, Alex Shinn wrote:
> So by deliberately limiting match we force people
> to write faster code. At the same time, it's more
> verbose code - if you really want a match as powerful
> as prolog you could implement it and deal with the
> fact that it can be very slow in some cases. And in
> that case you will eventually need to add a way to
> explicitly commit matches (i.e. "cut" in prolog) for
> decent performance.
>
> [I'm not completely consistent in this, though,
> because the tree patterns I added do in fact
> require more complex searching and backtracking.
> But tree searches require this in general.]
>
Alex, will you explain what I'd doing wrong here using
tree searching patterns?
(pretty-print (map
(match-lambda
(('foo *** '(bar 1)) #t)
(_ #f))
'((foo (bar 1))
(foo (a (bar 1)))
(foo (a (b (bar 1
(foo (a (b (c (bar 1
Only the first form |(foo (bar 1))| is returning #t here.
The remaining forms return #f. I would expect all of them
to return true, based on my naive understanding of the ***
operator.
-Alan
--
.i ko djuno fi le do sevzi
___
Chicken-users mailing list
Chicken-users@nongnu.org
http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] matchable egg usage question
On Fri, Jan 28, 2011 at 2:21 PM, Alan Post wrote: > I'm trying to use the matchable egg to detect #!key parameters in > functions I've constructed. I have functions that accept multiple > #!key parameters, and I'm not sure how to make the matchable egg > match |(func ... mykey: myvalue ...)|. That is, how to get the > matchable egg to match two parameters anywhere in an input list. Why not use Chicken's builtin #!key handling? (apply (lambda (#!key key1 key2) ;; code using key1 and key2 ...) (list key1: val1 key2: val2)) > This is what I've got so far. I am interested in whether the > #!key paramater 'a' is set to #t: OK, the original point of this style of pattern matching was it was simple and fast - it does a simple linear match against each possible pattern so is as fast as using low-level destructuring and checking (faster if the match library can eliminate common sub-patterns). As soon as you introduce any ambiguity in how a pattern can match the whole process becomes a search algorithm, with backtracking in the general case. So whereas the pattern (a b c) is constant time (O(m) in the pattern size), (a b c ...) is linear (O(n) in the input size), which is fine, but (a b c ... d ...) is O(n^2) in the input size depending on where you choose to split between c and d. And (a b c ... d ... e ...) is O(n^3), etc. Most of the time when you want to use this sort of pattern, you don't want backtracking - you want c to match as many elements as it can and then "commit," and take the rest of the list as d. So if the match doesn't let you express the expensive patterns, you have to iterate over one c at a time: (let lp ((ls ls) (c-ls '()) (match ls ((c . rest) (lp (cdr ls) (cons c c-ls))) (else ;; match d's in remaining ls ...))) This is O(n), and is the same sort of idiom many complex syntax-rules libraries use. So by deliberately limiting match we force people to write faster code. At the same time, it's more verbose code - if you really want a match as powerful as prolog you could implement it and deal with the fact that it can be very slow in some cases. And in that case you will eventually need to add a way to explicitly commit matches (i.e. "cut" in prolog) for decent performance. [I'm not completely consistent in this, though, because the tree patterns I added do in fact require more complex searching and backtracking. But tree searches require this in general.] -- Alex ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
[Chicken-users] matchable egg usage question
I'm trying to use the matchable egg to detect #!key parameters in functions I've constructed. I have functions that accept multiple #!key parameters, and I'm not sure how to make the matchable egg match |(func ... mykey: myvalue ...)|. That is, how to get the matchable egg to match two parameters anywhere in an input list. This is what I've got so far. I am interested in whether the #!key paramater 'a' is set to #t: (use matchable) (pretty-print (map (match-lambda ((_ 'a: #t . _) '(0 #t)) ((_ ... 'a: #t) '(1 #t)) (_ #f)) '((foo) (foo bar) (foo a: #f) (foo a: #f b: #t) (foo a: #f b: #t c: #t) (foo a: #f c: #t b: #t) (foo b: #t a: #f c: #t) (foo b: #t c: #t a: #f) (foo a: #t) (foo a: #t b: #t) (foo a: #t b: #t c: #t) (foo a: #t c: #t b: #t) (foo b: #t a: #t c: #t) (foo b: #t c: #t a: #t (exit) This works for every case except when the #!key I want to match appears in the middle of a list of arguments, as happens in the second-to-last case I'm trying to match. Is there a way to make match work in this case? What pattern should I add to match values anywhere in the list, not just the front and end? -Alan -- .i ko djuno fi le do sevzi ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
