🚀 go-pugleaf

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:

   Following a long and heated discussion on the topic in a local
   newsgroup in which the local ML experts have come up hands empty
   (surprising given this is Edinburgh), I'm looking for fully functional
   ways of solving certain permutation problems which imperative languages
   like C can solve in linear time.  In particular, I'd like to be able to
   compose and invert permutations and generate random ones in linear
   time.  If you don't like mixing "random" and "fully functional", you
   could always ask for a list of random numbers as input. For example, an
   equivalent of this C function would be the best part of a solution:

Use version arrays. They are an implementation of functional vectors,
and the kind of update that happens in an imperative algorithm can be
carried out in constant time. I think every functional language should
provide them, either as the default implementation of a vector, or,
at least, as another datatype. In SML, you can hack them yourself,
except that the type signature will include some weak types that
needn't be weak.

I doubt that you can do better than "n log n" if all you have is lists
and functional vectors with update by copying.

In general, you don't need special ideas ("do it by sorting") in order
to convert imperative algorithms to functional algorithms with a
logarithmic overhead. Instead, simply use a balanced tree to represent
arrays.  That will give you Theta(log n) time access and "update".

					Thomas.

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:

> I believe that Haskell has a way of offering read-only arrays accessible in
> O(1) time and that might go some way towards a solution (for example,
> they solve composition pretty neatly).

As do some recent implementations of ML.
-- 
				--Andrew Koenig
				  ark@europa.att.com

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:

  [ how do you efficiently permute an array in a pure functional way? ]

Assuming that the types "Updatable_Array/Updatable_Array_Action" are
provided in the implementation, then the following Haskell code might
work for the the example problem.

 >rand_permute :: Array Int Int -> Updatable_Array Int Int -> Array Int Int
 >rand_permute source = with_updatable_array b (initalise `and_then` permute)
 >  where initialise = for_all inds init
 >        permute    = for_all inds (\i -> swap i (source!i))
 >        b          = bounds source
 >        inds       = range b
 >        init i     = store i i

 >swap :: Int -> Int -> Updatable_Array_Action Int Int ()
 >swap i j =
 >  fetch i       `giving`   \tmp ->
 >  fetch j       `giving`   \new_i ->
 >  store i new_i `and_then`
 >  store j tmp

where the various implementation defined actions have the following
signatures :- 

 >fetch :: (Ix a) => a -> Updatable_Array_Action a b b
 >store :: (Ix a) => a -> b -> Updatable_Array_Action a b ()
 >giving :: (Ix a) => Updatable_Array_Action a b c
 >       -> (c -> Updatable_Array_Action a b d)
 >       -> Updatable_Array_Action a b d
 >and_then :: (Ix a) => Updatable_Array_Action a b c
 >         -> Updatable_Array_Action a b d
 >         -> Updatable_Array_Action a b d
 >for_all :: (Ix a) => [a] -> (a -> Updatable_Array_Action a b c)
 >                         -> Updatable_Array_Action a b c
 >with_updatable_array :: (Ix a) -> (a, a)
 >                     -> Updatable_Array_Action a b c -> Array a b

yours treading carefully,

bevan

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
>
>/* 
> * source and result are arrays of integers of length n.
> * For random permutations, source should be made up of a lot of
> * random numbers each between 0 and n-1.
> */
>
>void randpermute(source, result, n)
>int *source, *result, n;
>{
>	int i, tmp;
>	
>	for(i = 0; i < n; i++)
>		result[i] = i;
>	for(i = 0; i < n; i++) {
>		tmp = result[i];
>		result[i] = result[source[i]];
>		result[source[i]] = tmp;
>	}
>}
>

This C code does not solve the problem correctly.  It gives n**n
possible outcomes, and in general the number of permutations of n
objects, n!, does not divide n**n.  For example, it doesn't work
for n = 3 (try it!).
-- 
Doug Quale
quale@saavik.cs.wisc.edu

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
>/* 
> * source and result are arrays of integers of length n.
> * For random permutations, source should be made up of a lot of
> * random numbers each between 0 and n-1.
> */
>
>void randpermute(source, result, n)
>int *source, *result, n;
>{
>	int i, tmp;
>	
>	for(i = 0; i < n; i++)
>		result[i] = i;
>	for(i = 0; i < n; i++) {
>		tmp = result[i];
>		result[i] = result[source[i]];
>		result[source[i]] = tmp;
>	}
>}
>

This C code does not solve the problem correctly.  The procedure
does not produce a random distribution because the number of possible
shuffles, n**n, is not divisible by the number of permutations, n!.

For instance, the output is skewed for n = 3 (try it!).
-- 
Doug Quale
quale@saavik.cs.wisc.edu

>Following a long and heated discussion on the topic in a local
>newsgroup in which the local ML experts have come up hands empty
>(surprising given this is Edinburgh), I'm looking for fully functional
>ways of solving certain permutation problems which imperative languages
>like C can solve in linear time.  In particular, I'd like to be able to
>compose and invert permutations and generate random ones in linear
>time.
Of course you can do it, it all depends on what primitive operations
you have available and what time they take.  Assuming that you
have updateable arrays with O(1) index and update it's trivial.
(The arrays can be packaged in any way you like to make them pure:
as a stream-to-stream function (lookup/index in, value out), as a
state monad, as version arrays, ...).  I don't consider having those
as primitive operations as cheating, all imperative languages have
them so why shouldn't we?

If, on the other hand, you only allow the pure lambda-calculus as
the programming language (with suger if you want), then I kind of doubt
that it can be done.  (Unless you have a constant time beta reduction
step and can come up with some clever coding of arrays.)

-- 

	-- Lennart Augustsson
[This signature is intentionally left blank.]

Quoting quale@spock.cs.wisc.edu (Doug Quale) in article <1993Jan10.080153.10321@daffy.cs.wisc.edu>:
>In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
>This C code does not solve the problem correctly.  It gives n**n
>possible outcomes, and in general the number of permutations of n
>objects, n!, does not divide n**n.  For example, it doesn't work
>for n = 3 (try it!).

Damn, you're right.  This is more than a little embarassing since I've
been standing by that code all last term.  However six does not divide
nine, so I guess I've got to modify it.  I think it'll work if I make a
slight change to the source array.  This time I'll prove it correct.

/* 
 * source and result are arrays of integers of length n.
 * For random permutations, source should be made up of a lot of
 * random numbers such that 0 <= source[i] <= i.
 */

void randpermute(source, result, n)
int *source, *result, n;
{
	int i;
	
	for(i = 0; i < n; i++) {
/*
 * Loop invariant: just before the test against n,
 * result[k] for 0 <= k < i is a permutation of the nat. numbers less than i
 * and the permutation is random if source is random as specified.
 * Proof below.
 */
		result[i] = result[source[i]];
		result[source[i]] = i;
	}
}

A permutation of length k is random if the probability of it being equal
to a given permutation gperm is 1/(k!).  Base case of the invariant: the
null permutation arises with probability 1 = 1/(0!).

Inductive step: supposing the invariant holds for i = k where k < n. 
After the execution of the next two source lines, is the subarray size
k+1 a permutation at all?  This divides into two subcases:

* source[k] = k

In this case, result[k] ends up being equal to k and the rest of the
array is unchanged; since the rest of the array is a permutation, this
is a permutation.

* source[k] < i

In this case, result[k] takes some value between 0 and k-1, and the
entry that used to hold that value now holds k.  Since the rest of the
array was a permutation, all the values between 0 and k are still
present and the new subarray is also a permutation.

Now, consider the element h in gperm such that gperm[h] = k.  In order
for the resulting subarray to equal gperm, two conditions must hold:
result[k] must equal h, and the old subarray before the loop stepped
around must be equal to gperm except that result[h] must equal gperm[k].
The probability of these two is 1/(k+1) and 1/(k!) respectively, so the
probability that the new subarray is gperm is 1/((k+1)!) as required.

Sorry if this isn't very clear but it's 3am where I am.  For people who
want to know what all this C is doing in comp.lang.functional, I asked
if the thing that this C function does in linear time can be done in a
pure functional style in linear time.  Except that I got the C wrong. 
Apologies, and thanks to Doug Quale for pointing it out.
  __                                   _____
\/ o\ Paul Crowley   pdc@dcs.ed.ac.uk  \\ //
/\__/ Trust me. I know what I'm doing.  \X/