🚀 go-pugleaf

>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.]