🚀 go-pugleaf

In his article jones-mark@cs.yale.edu (Mark Jones) 
efines the function swap as follows
>
>        swap []     = [ [] ]
>        swap (m:ms) = [ x:xs | x<-m, xs<-swap ms ]
>


It might not be clear to you all that its definition of swap coincides with 
my definition of swapM_L. 

Here is the necessary argumentation :


appM_L f [] = f []
appM_L f (m:ms) = appM (\x -> appM_L (f . (x:)) ms) m

swapM_L [] = unitM []
swapM_L (m:ms) = appM (\x -> appM_L (unitM . (x:)) ms) m
               = appM (\x -> appM (unitM . (x:)) (swapM_L ms)) m
               = appM (\x -> appM (\xs -> unitM (x:xs)) (swapM_L ms)) m


Comprehension notation is now defined as follows : (where bindM = flip appM)

[ t ]   <==>  unitM t
[ t | x<-m ]  <==>  bindM  m (\x -> unitM t) 
[ t | x<-m , y<-n ]  <==>  bindM m (\x -> bindM n (\y -> unitM t)) 

and so on ...

this means that

swapM_L [] = [ [] ]
swap M_L (m:ms) = [ x:xs |  x<-m , xs<- swapM_L ms]

the same as

swap [] = [ [] ]
swap (m:ms) = [ x:xs |  x<-m , xs<- swap ms]


BTW.

It should be clear by now that his way of defining a swap function
also works with other monads than the List monad.


Consider e.g. binary trees

data Tree a = Node a
            | Tree a :^: Tree a

swap (Node m) = [ Node x | x<-m ]
swap (mt :^: nt) = [ xt :^: yt | xt<-swap mt , yt<-swap nt ]


checking the axioms is another matter ...


Luc Duponcheel
Alcatel Bell Telephone, SE99
Francis Wellesplein 1,
B-2018 Antwerpen
Belgium

    \_        \_\_\_    \_   \_    \_\_\_    
     \_        \_    \_  \_   \_    \_   \_          
      \_        \_    \_  \_   \_    \_\_\_      __o   
       \_        \_   \_   \_   \_    \_       _`\<,_  
        \_\_\_\_  \_\_\_    \_\_\_\_   \_     (*)/ (*)