Hello Wolfgang,
thanks for you help! Your suggestion is so "obvious",
I seem to not have seen the wood for the trees *g*.
Adopted to graphs the result looks as follows:
-- primitive parser for edges, edge c need not be first element of list
edge::Edge->Grappa ()
edge c _ g | g=:=g1++c:g2 = ((),[],g1++g2)
where g1,g2 free
edge c (S _) g | c `notInGraph` g = ((),[c],g)
notInGraph c [] = success
notInGraph c (x:xs) | c=/=x = notInGraph c xs
I need to check notInGraph before assuming an edge, because I
want to consume the given edges first. Is this the right way to
ensure such constraints in Curry? This code works with MCC,
how can I realize this in PAKCS? Is there a more standard way?
Best regards and thanks again (also to you Nikolay),
Steffen
> The problem is that your (<*>) combinator does not really restrict
> the search space. For instance, given an expression
> (p1 <*> p2) <*> (p3 <*> p4)
> you allow for two errors in each of the parsers (p1 <*> p2) and
> (p3 <*> p4) and only cut solutions with more than two error in
> the combined parser, but only after all alternatives for
> (p3 <*> p4) have been tried. The solution, of course, is to make
> the upper limit of errors an additional argument of the parsing
> combinators, i.e.,
> (p1 <*> p2) maxerrs xs | p1 maxerrs xs=:=(xs',errs1) &
> p2 (maxerrs `minus` errs1) xs'=:=
> (xs'',errs2) =
> (xs'', errs1 `plus` errs2)
> where xs',errs1,xs'',errs2 free
>
> pSucceed _ xs = (xs,Z)
>
>
> char c _ (x:xs) | c=:=x = (xs,Z)
>
> char c (S _) xs = (xs,S Z)
>
> Incidentally, in order to avoid just another disappointment, I'd
> strongly suggest to use case expressions instead of unification,
> i.e.,
>
> (p1 <*> p2) maxerrs xs =
> case p1 maxerrs xs of
> (xs',errs1) ->
> case p2 (maxerrs `minus` errs1) xs' of
> (xs'',errs2) -> (xs'', errs1 `plus` errs2)
>
> The problem with unification in this particular example is that
> e1=:=e2 is defined to be satisfied only for equal data terms and
> therefore both of its arguments are evaluated to normal form.
> Unfortunately, this introduces an O(n^2) time complexity in the
> parser, where n is the length of the input string, when using
> expressions like
> p1 maxerrs xs=:=(xs',errs1)
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mo Feb 25 2008 - 16:46:10 CET