[clean-list] List Comprehensions...
Fabien Todescato
f.todescato@larisys.fr
Fri, 15 Dec 2000 14:12:27 +0100
This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.
------_=_NextPart_000_01C06698.B05B3490
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Dear Erik, and Cleaners,
You will find enclosed here the minimal sources for the monadic =
backtracking
combinators extracted from Plasmeijer and Koopman's paper "Efficient =
Parser
Combinators".
Below some standard list functions implemented using these combinators =
:
member :: ! [ x ] -> BKM y x
member [ x : xl ] =3D unit x plus member xl
member [ ] =3D null
selection :: [ x ] -> BKM y ( x , [ x ] )
selection [ x : xl ] =3D unit ( x , xl ) or selection xl bind \ ( x_ , =
xl ) ->
unit ( x_ , [ x : xl ] )
selection [ ] =3D null
permutation :: [ x ] -> BKM y [ x ]
permutation [ ] =3D unit [ ]
permutation xl =3D selection xl bind \ ( x , xl ) -> permutation xl =
bind \ xl
-> unit [ x : xl ]
product :: [ [ x ] ] -> BKM y [ x ]
product [ ] =3D unit [ ]
product [ xl : xll ] =3D member xl bind \ x -> product xll bind \ xl -> =
unit [
x : xl ]
selections :: [ x ] -> [ ( x , [ x ] ) ]
selections xl =3D findAll ( selection xl )
permutations :: [ x ] -> [ [ x ] ]
permutations xl =3D findAll ( permutation xl )
products :: [ [ x ] ] -> [ [ x ] ]
products xll =3D findAll ( product xll )
As you will guess from the sources, these combinators are intended to =
be
used when overloading monadic operators bind, unit, null and plus. As
explained in Graham's Hutton "Monadic Parser Combinators" article, you =
may
use such a scheme in order to compose monads in a modular manner. The
monadic parsers can be build by instanciating a state-transformer
transformer monad with the above backtracking monad.
This piece of software has been developed as part of a larger =
experimental
industrial project and is published by courtesy of my employer in order =
to
promote the use and techniques of Functional Programming. I cannot, =
however,
publish the monadic parser combinators and related libraries.
Fabien TODESCATO
-----Message d'origine-----
De : F.S.A.Zuurbier@inter.nl.net [mailto:F.S.A.Zuurbier@inter.nl.net]
Envoy=E9 : vendredi 15 d=E9cembre 2000 13:18
=C0 : clean-list@cs.kun.nl
Objet : Re: [clean-list] List Comprehensions...
Fabien Todescato wrote:
"As a matter of fact, it is possible to extract from their parser
combinators the logic for continuation-based backtracking and implement =
a
continuation-based backtracking monad, instead of the standard list =
monad."
Looks like you hit gold. I would be interested in a version of the
continuation parsers where you use these continuation-based =
backtracking
combinators.
Regards Erik Zuurbier
_______________________________________________
clean-list mailing list
clean-list@cs.kun.nl
http://www.cs.kun.nl/mailman/listinfo/clean-list
------_=_NextPart_000_01C06698.B05B3490
Content-Type: application/octet-stream;
name="monadicCombinators.dcl"
Content-Disposition: attachment;
filename="monadicCombinators.dcl"
// --------------------------------------------------------------------------------
// Project : LARISYS' Standard Functional Library
// Module : monadicCombinators
// Purpose : Overloaded combinators for monadic programming.
// Author : FT
// System : Clean Compiler 1.3.2 - Clean IDE 2.0
// --------------------------------------------------------------------------------
// This document is the exclusive property of LARISYS.
// This document may not be reproduced in any way whatsoever without prior written
// approval from LARISYS.
// --------------------------------------------------------------------------------
// (C) LARISYS 2000-2001
// --------------------------------------------------------------------------------
definition module monadicCombinators
class unit m :: x -> m x
class null m :: m x
class (bind) infixr 6 m :: ! ( m x ) ( x -> m y ) -> m y
class (plus) infixl 3 m :: ( m x ) ( m x ) -> m x
(om) infixr 6 :: ( y -> m z ) ( x -> m y ) -> ( x -> m z ) | bind m
(into) infixl 4 :: ( m x ) ( x -> y ) -> m y | bind , unit m
(when) infixl 5 :: ( m x ) ( x -> Bool ) -> m x | bind , unit , null m
------_=_NextPart_000_01C06698.B05B3490
Content-Type: application/octet-stream;
name="monadicBacktrackingCombinators.icl"
Content-Disposition: attachment;
filename="monadicBacktrackingCombinators.icl"
// --------------------------------------------------------------------------------
// Project : LARISYS' Standard Functional Library
// Module : monadicBacktrackingCombinators
// Purpose : Overloaded combinators for non-deterministic monadic programming.
// Author : FT
// System : Clean Compiler 1.3.2 - Clean IDE 2.0
// --------------------------------------------------------------------------------
// This document is the exclusive property of LARISYS.
// This document may not be reproduced in any way whatsoever without prior written
// approval from LARISYS.
// --------------------------------------------------------------------------------
// (C) LARISYS 2000-2001
// --------------------------------------------------------------------------------
implementation module monadicBacktrackingCombinators
import monadicCombinators
:: BKM y x = BKM ( ( AC y x ) ( XC y ) ( OC y ) -> [ y ] )
:: AC y x :== x ( XC y ) ( OC y ) -> [ y ]
:: XC y :== ( OC y ) -> [ y ]
:: OC y :== [ y ]
BKMnull :: BKM y x
BKMnull = BKM \ ac xc oc -> xc oc
BKMunit :: x -> BKM y x
BKMunit x = BKM \ ac -> ac x
(BKMbind) infixr 6 :: ( BKM z x ) ( x -> BKM z y ) -> BKM z y
(BKMbind) ( BKM b ) f = BKM \ ac -> b \ x -> let ( BKM g ) = f x in g ac
(BKMor) infixl 3 :: ( BKM x y ) ( BKM x y ) -> BKM x y
(BKMor) ( BKM b1 ) ( BKM b2 ) = BKM \ ac xc oc -> b1 ac ( \ oc -> oc ) ( b2 ac xc oc )
(BKMxor) infixl 3 :: ( BKM x y ) ( BKM x y ) -> BKM x y
(BKMxor) ( BKM b1 ) ( BKM b2 ) = BKM \ ac xc oc -> b1 ( \ x xc_ -> ac x xc ) ( \ oc -> b2 ac xc oc ) oc
BKMfindAll :: ( BKM x x ) -> [ x ]
BKMfindAll ( BKM b ) = b ( \ x xc oc -> [ x : xc oc ] ) ( \ oc -> oc ) [ ]
instance unit ( BKM y ) where unit x = BKMunit x
instance null ( BKM y ) where null = BKMnull
instance bind ( BKM y ) where (bind) x f = (BKMbind) x f
instance plus ( BKM y ) where (plus) x y = (BKMor) x y
------_=_NextPart_000_01C06698.B05B3490
Content-Type: application/octet-stream;
name="monadicBacktrackingCombinators.dcl"
Content-Disposition: attachment;
filename="monadicBacktrackingCombinators.dcl"
// --------------------------------------------------------------------------------
// Project : LARISYS' Standard Functional Library
// Module : monadicBacktrackingCombinators
// Purpose : Overloaded combinators for non-deterministic monadic programming.
// Author : FT
// System : Clean Compiler 1.3.2 - Clean IDE 2.0
// --------------------------------------------------------------------------------
// This document is the exclusive property of LARISYS.
// This document may not be reproduced in any way whatsoever without prior written
// approval from LARISYS.
// --------------------------------------------------------------------------------
// (C) LARISYS 2000-2001
// --------------------------------------------------------------------------------
definition module monadicBacktrackingCombinators
import monadicCombinators
:: BKM y x
BKMnull :: BKM y x
BKMunit :: x -> BKM y x
(BKMbind) infixr 6 :: ( BKM z x ) ( x -> BKM z y ) -> BKM z y
(BKMor) infixl 3 :: ( BKM x y ) ( BKM x y ) -> BKM x y
(BKMxor) infixl 3 :: ( BKM x y ) ( BKM x y ) -> BKM x y
BKMfindAll :: ( BKM x x ) -> [ x ]
instance unit ( BKM y )
instance null ( BKM y )
instance bind ( BKM y )
instance plus ( BKM y )
------_=_NextPart_000_01C06698.B05B3490--