Xref: utzoo comp.lang.prolog:3150 comp.lang.functional:420
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ukc!icdoc!zmacx07
From: zmacx07@doc.ic.ac.uk (Simon E Spero)
Newsgroups: comp.lang.prolog,comp.lang.functional
Subject: Re: shuffling a list
Message-ID: <2246@gould.doc.ic.ac.uk>
Date: 7 Sep 90 17:13:51 GMT
References: <5056@daffy.cs.wisc.edu>
Sender: news@doc.ic.ac.uk
Reply-To: zmacx07@doc.ic.ac.uk (Simon E Spero)
Organization: Imperial College Department of Computing
Lines: 73

In article <5056@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:
>What is the best way to shuffle a list in a functional language?
>It is easy to shuffle an array fairly, and in Scheme I would use
>list->vector, shuffle the vector, and use vector->list.
>
>--
>Doug Quale
      ----- no relation to Dan?

This is a functional version written (mostly) in  lazy Hope+C, for use 
in implementations where sharing analysis can be performed. I haven't tried it
,mainly cause I don't know of any such implementation that's put all the bits
together- as a separate question, how many production FLs have sharing analysis
wired in? 
   Curious of Kensington

-------- cut to pieces here -------

dec shuffle : list(alpha) -> list(alpha);
dec shuffle : vector(alpha) -> vector(alpha);

--- shuffle l <= vectortolist (shuffle (listtovector l));

--- shuffle v <=
	let vsize == vectorlength(v)
	let newvec == map_vector(id,v) in
        let swap_em == 
		lambda 
		([],vec) => v
		(a::b,vec) =>
		 let (x,y) == (rand(vsize),rand(vsize)) in
		 let t == vref(vec,x) in
		 let t2 == vref(vec,y) in
    !force 'em!	 let dummy == t = t and t2 = t2 in
		 if dummy  then 
		           let vec2 == vset(vec,x,t2) in
		 	   swap_em(b,vset(vec2,y,t))
	  	  else      error([(999,"Reality fault: core dumped")])
	   	 in
	 swap_em(first(vsize/2,[]),newvec)


Notes: rand(x) is a magic function which returns a num of range 1..n
       Of course, in reality there's a lazy list that gets passed 
       around - close your eyes and use you're imagination :-)

       	vset(v,i,x) returns a copy of v with v[i] set to x. If no sharing 
       	analysis is done, then this code will end up creating vsize copies
       	of the array- not fun. However the way that this code is written, 
       	using two temp variables to avoid  problems when  x = y , and
       	the use of the copy newvec to localise all sharing problems to
       	this function, should be sufficient to bludgeon even the simplest
       	sharing analyser into action. 
        The main problem is in ensuring that the two calls to vref are 
	evaluated before the calls to vset. I can't think of any way to force `
	this without also forcing the values returned by those calls. As 
	a result, this algorithm is stricter than it ought to be. Is there
	any way around this?

       In each pass through swap_em, the orignal vector is not referenced 
       after a vset has been applied to it (at this stage an evaluation
       order can be defined. vref should be strict
       vset isn't provided in standard Hope+C - you can emulate it with
       perm_vector (like map_vector, only the function supplied is given
       an element's index as well as its value. 

	first is the function discussed ad nauseum in this forum - first(n,[])
	produces a list of  n bottoms (and why not).
--
zmacx07@uk.ac.ic.doc | sispero@cix.co.uk |    ..!mcsun!ukc!slxsys!cix!sispero
------------------------------------------------------------------------------
The Poll Tax.    | Saddam Hussein runs Lotus 123 on | DoC,IC,London SW7 2BZ
I'm Not. Are you?| Apple Macs.|   I love the smell of Sarin in the morning