- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Steffen Mazanek <steffen.mazanek_at_unibw.de>

Date: Mon, 25 Feb 2008 11:44:08 +0100

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

Date: Mon, 25 Feb 2008 11:44:08 +0100

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

_______________________________________________

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

*
This archive was generated by hypermail 2.3.0
: Mo Jan 27 2020 - 07:15:10 CET
*