[clean-list] help
Fabien Todescato
f.todescato@larisys.fr
Fri, 2 Mar 2001 10:05:08 +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.
--------------InterScan_NT_MIME_Boundary
Content-Type: multipart/alternative;
boundary="----_=_NextPart_001_01C0A2F7.E1F63FE0"
------_=_NextPart_001_01C0A2F7.E1F63FE0
Content-Type: text/plain;
charset="iso-2022-jp"
-----Message d'origine-----
De : ZhangRuoyu [mailto:zhangry@comp.eng.himeji-tech.ac.jp]
Envoye : vendredi 2 mars 2001 03:38
A : clean-list@cs.kun.nl
Objet : [clean-list] help
I am a newer for Clean, and I am reading the tutorial (Functional
Programming in CLEAN) now.
Some Exercises in the books troubled me, here is one,
Write a list comprehension for generating all permutations of some input
list.
who can tell me how to solve this problem?
This is a copy of a mail I send some times ago. It echoes Jerzy's answers
mentioning non-determinism. I am aware it may not fit your concern about
solving an exercise with a simple technique, but it may sparkle in your mind
some increased interest about Clean, and functional programming.
Digging into the archives of the Clean-mailing list, you may be able to
find other mails with source code for the backtracking combinators.
Best regards, Fabien TODESCATO
In their famous paper "Efficient Parser Combinators", Pieter Koopmann and
Rinus Plasmeijer demonstrate the use of continuations instead of lists of
successes to implement backtracking in their parser combinators. 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.
It turns out that using such backtracking combinators provide in some cases
an elegant alternative when writing list functions. Consider the following
examples.
The selections function below computes for a given list all the possible
pairs of one element selected from the list, with the list of remaining
elements in the same order as they were in the original list.
selections :: [ x ] -> [ ( x , [ x ] ) ]
selections [x:xs] = [(x,xs):(map (\(x1,xs1)->(x1,[x:xs1])) (selections xs))]
selections [] = []
Based on that selections function we can write the permutations function
below that computes the permutations of a list :
permutations :: [ x ] -> [ [ x ] ]
permutations [] = [[]]
permutations xs = flatten ( map
( \ ( x , xs ) -> map
( \ xs -> [ x : xs ] )
( permutations xs )
)
( selections xs )
)
That code is probably not optimal as combinations of flatten and map can be
rewritten using foldr.
Now, using continuation-based monadic backtracking combinators we can write
Prolog-like code as follows :
member [ ] = null
member [ x : xl ] = unit x plus member xl
selection [ ] = null
selection [ x : xl ] = unit ( x , xl ) plus ( selection xl bind \ ( x_ , xl
) -> unit ( x_ , [ x : xl ] ) )
permutation [ ] = [ ]
permutation xl = selection xl bind \ ( x , xl ) -> permutation xl bind \ xl
-> unit [ x : xl ]
And we get :
selections :: [ x ] -> [ ( x , [ x ] ) ]
selections xl = findAll ( selection xl )
permutations :: [ x ] -> [ [ x ] ]
permutations xl = findAll ( permutation xl )
Not only is the code better looking, is is probably - I didn't check that -
more efficient as, as Koopmann and Plasmeijer explain, it avoids creating
intermediate data structures by using continuations instead.
------_=_NextPart_001_01C0A2F7.E1F63FE0
Content-Type: text/html;
charset="iso-2022-jp"
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-2022-jp">
<META content="MSHTML 5.00.2920.0" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT color=#0000ff face="Courier New" size=2><SPAN
class=531045408-02032001>
<BLOCKQUOTE
style="BORDER-LEFT: #0000ff 2px solid; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px; PADDING-LEFT: 5px">
<DIV align=left class=OutlookMessageHeader dir=ltr><FONT face=Tahoma
size=2>-----Message d'origine-----<BR><B>De :</B> ZhangRuoyu
[mailto:zhangry@comp.eng.himeji-tech.ac.jp]<BR><B>Envoyé :</B> vendredi 2
mars 2001 03:38<BR><B>À :</B> clean-list@cs.kun.nl<BR><B>Objet :</B>
[clean-list] help<BR><BR></DIV></FONT>
<DIV><FONT face=Arial size=2>I am a newer for Clean, and I am reading
the tutorial (Functional Programming in CLEAN) now.</FONT></DIV>
<DIV><FONT face=Arial size=2>Some Exercises in the books troubled me, here is
one,</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial size=2>Write a list comprehension for generating all
permutations of some input list. </FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial size=2>who can tell me how to solve this
problem?</FONT></DIV></BLOCKQUOTE></SPAN></FONT></DIV>
<DIV><FONT face="Courier New" size=2><SPAN class=531045408-02032001>This is a
copy of a mail I send some times ago. It echoes Jerzy's answers mentioning
non-determinism. I am aware it may not fit your concern about solving an
exercise with a simple technique, but it may sparkle in your mind some increased
interest about Clean, and functional programming.</SPAN></FONT></DIV>
<DIV><FONT face="Courier New" size=2><SPAN
class=531045408-02032001> Digging into the archives of the
Clean-mailing list, you may be able to find other mails with source code for the
backtracking combinators.</SPAN></FONT></DIV>
<DIV><FONT face="Courier New" size=2><SPAN
class=531045408-02032001></SPAN></FONT> </DIV>
<DIV><FONT face="Courier New" size=2><SPAN class=531045408-02032001>Best
regards, Fabien TODESCATO</SPAN></FONT></DIV><SPAN class=531045408-02032001>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>In their famous paper
"Efficient Parser Combinators", Pieter Koopmann and<SPAN
class=531045408-02032001> </SPAN>Rinus Plasmeijer demonstrate the use
of <SPAN class=531045408-02032001>c</SPAN>ontinuations instead of lists
of<SPAN class=531045408-02032001> </SPAN>successes to implement backtracking in
their parser combinators.<SPAN class=531045408-02032001> </SPAN>As a matter of
fact, it is possible to extract from their parser combinators<SPAN
class=531045408-02032001> </SPAN>the logic for continuation-based backtracking
and implement a<SPAN class=531045408-02032001> </SPAN>continuation-based
backtracking monad, instead of the standard list monad.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>It turns out that using such
backtracking combinators provide in some cases<SPAN class=531045408-02032001>
</SPAN>an elegant alternative when writing list functions. Consider the
following<SPAN class=531045408-02032001> </SPAN>examples.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>The selections function below
computes for a given list all the possible<SPAN class=531045408-02032001>
</SPAN>pairs of one element selected from the list, with the list of
remaining<SPAN class=531045408-02032001> </SPAN>elements in the same order as
they were in the original list.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>selections :: [ x ] -> [ (
x , [ x ] ) ]</FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">selections [x:xs]
= [(x,xs):(map (\(x1,xs1)->(x1,[x:xs1]))<SPAN class=531045408-02032001>
</SPAN></FONT></FONT></FONT><FONT color=#0000ff face="Courier New"
size=2>(selections xs))]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>selections [] =
[]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">Based on that
selections function we can write the permutations function<SPAN
class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT color=#0000ff
face="Courier New" size=2>below that computes the permutations of a list
:</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>permutations :: [ x ] -> [
[ x ] ]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>permutations [] =
[[]]</FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">permutations xs =
flatten<SPAN class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT
color=#0000ff face="Courier New" size=2>( map</FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>( \ ( x , xs ) -> map</FONT></FONT></FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>( \ xs -> [ x : xs ] )</FONT></FONT></FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>( permutations xs )</FONT></FONT></FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>)</FONT></FONT></FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>( selections xs )</FONT></FONT></FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New"><SPAN
class=531045408-02032001>
</SPAN>)</FONT></FONT></FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">That code is
probably not optimal as combinations of flatten and map can be<SPAN
class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT color=#0000ff
face="Courier New" size=2>rewritten using foldr.</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">Now, using
continuation-based monadic backtracking combinators we can write<SPAN
class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT color=#0000ff
face="Courier New" size=2>Prolog-like code as follows :</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>member [ ] =
null</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>member [ x : xl ] = unit x
plus member xl</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>selection [ ] =
null</FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">selection [ x :
xl ] = unit ( x , xl ) plus ( selection xl bind \ (<SPAN
class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT color=#0000ff
face="Courier New" size=2>x_ , xl ) -> unit ( x_ , [ x : xl ] )
)</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>permutation [ ] = [
]</FONT></DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">permutation xl =
selection xl bind \ ( x , xl ) -> permutation xl<SPAN
class=531045408-02032001> </SPAN></FONT></FONT></FONT><FONT color=#0000ff
face="Courier New" size=2>bind \ xl -> unit [ x : xl ]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>And we get :</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>selections :: [ x ] -> [ (
x , [ x ] ) ]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>selections xl = findAll (
selection xl )</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>permutations :: [ x ] -> [
[ x ] ]</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2>permutations xl = findAll (
permutation xl )</FONT></DIV>
<DIV><FONT color=#0000ff face="Courier New" size=2></FONT> </DIV>
<DIV><FONT size=2><FONT color=#0000ff><FONT face="Courier New">Not only is the
code better looking, is is probably - I didn't check that -<SPAN
class=531045408-02032001> </SPAN></FONT><FONT face="Courier New">more efficient
as, as Koopmann and <SPAN class=531045408-02032001>P</SPAN>lasmeijer
explain, it avoids creating<SPAN class=531045408-02032001> </SPAN></FONT><FONT
face="Courier New">intermediate data structures by using continuations
instead.</FONT></FONT></FONT></DIV></SPAN>
<DIV><FONT face="Courier New" size=2><SPAN
class=531045408-02032001></SPAN></FONT> </DIV></BODY></HTML>
------_=_NextPart_001_01C0A2F7.E1F63FE0--
--------------InterScan_NT_MIME_Boundary--