home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / function / 1478 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  2.0 KB
  1. Path: sparky!uunet!mcsun!ub4b!alcbel!ta7s49.alcbel.be
  2. From: ldup@ta7s49.alcbel.be (Luc Duponcheel)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re : for monad lovers only
  5. Message-ID: <1932@alcbel.be>
  6. Date: 18 Dec 92 09:30:22 GMT
  7. Sender: ldup@alcbel.be
  8. Organization: Alcatel Bell Telephone, Antwerpen, Belgium
  9. Lines: 73
  10.  
  11. In his article jones-mark@cs.yale.edu (Mark Jones) 
  12. efines the function swap as follows
  13. >
  14. >        swap []     = [ [] ]
  15. >        swap (m:ms) = [ x:xs | x<-m, xs<-swap ms ]
  16. >
  17.  
  18.  
  19. It might not be clear to you all that its definition of swap coincides with 
  20. my definition of swapM_L. 
  21.  
  22. Here is the necessary argumentation :
  23.  
  24.  
  25. appM_L f [] = f []
  26. appM_L f (m:ms) = appM (\x -> appM_L (f . (x:)) ms) m
  27.  
  28. swapM_L [] = unitM []
  29. swapM_L (m:ms) = appM (\x -> appM_L (unitM . (x:)) ms) m
  30.                = appM (\x -> appM (unitM . (x:)) (swapM_L ms)) m
  31.                = appM (\x -> appM (\xs -> unitM (x:xs)) (swapM_L ms)) m
  32.  
  33.  
  34. Comprehension notation is now defined as follows : (where bindM = flip appM)
  35.  
  36. [ t ]   <==>  unitM t
  37. [ t | x<-m ]  <==>  bindM  m (\x -> unitM t) 
  38. [ t | x<-m , y<-n ]  <==>  bindM m (\x -> bindM n (\y -> unitM t)) 
  39.  
  40. and so on ...
  41.  
  42. this means that
  43.  
  44. swapM_L [] = [ [] ]
  45. swap M_L (m:ms) = [ x:xs |  x<-m , xs<- swapM_L ms]
  46.  
  47. the same as
  48.  
  49. swap [] = [ [] ]
  50. swap (m:ms) = [ x:xs |  x<-m , xs<- swap ms]
  51.  
  52.  
  53. BTW.
  54.  
  55. It should be clear by now that his way of defining a swap function
  56. also works with other monads than the List monad.
  57.  
  58.  
  59. Consider e.g. binary trees
  60.  
  61. data Tree a = Node a
  62.             | Tree a :^: Tree a
  63.  
  64. swap (Node m) = [ Node x | x<-m ]
  65. swap (mt :^: nt) = [ xt :^: yt | xt<-swap mt , yt<-swap nt ]
  66.  
  67.  
  68. checking the axioms is another matter ...
  69.  
  70.  
  71. Luc Duponcheel
  72. Alcatel Bell Telephone, SE99
  73. Francis Wellesplein 1,
  74. B-2018 Antwerpen
  75. Belgium
  76.  
  77.     \_        \_\_\_    \_   \_    \_\_\_    
  78.      \_        \_    \_  \_   \_    \_   \_          
  79.       \_        \_    \_  \_   \_    \_\_\_      __o   
  80.        \_        \_   \_   \_   \_    \_       _`\<,_  
  81.         \_\_\_\_  \_\_\_    \_\_\_\_   \_     (*)/ (*)  
  82.  
  83.  
  84.