Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!ncar!oddjob!uxc!uxc.cso.uiuc.edu!a.cs.uiuc.edu!m.cs.uiuc.edu!robison
From: robison@m.cs.uiuc.edu
Newsgroups: comp.lang.misc
Subject: Re: Random permutation algorithm
Message-ID: <5200017@m.cs.uiuc.edu>
Date: 22 Aug 88 18:25:00 GMT
References: <5200012@m.cs.uiuc.edu>
Lines: 27
Nf-ID: #R:m.cs.uiuc.edu:5200012:m.cs.uiuc.edu:5200017:000:1097
Nf-From: m.cs.uiuc.edu!robison    Aug 22 13:25:00 1988


The paper cited[1] deliberately specifies problems biased towards imperative
languages.  The authors are asking if applicative languages are inherently
slower than imperative languages (in the asymptotic sense).  Seven problems 
were specified for which the known imperative solutions are faster than
the known applicative solutions.  For example, another problem in the paper is:

	Problem: Array Transactions

	Description: Given n and sequence of k read/write operations to array
                     indexed 1,...,n, produce the sequence of results of the
		     read operations.  Let k>n.

This is solvable in O(k) time on an imperative machine, but the best known
on an applicative machine is O(k log n).  (The solution simulates the array
with an AVL tree.)

[1] Carl G. Ponder, Patrick C. McGeer, and Antony P-C. Ng,
    "Are applicative languages inefficient?", SIGPLAN Notices,
    vol. 23,6, June 1988, 135-139.


Arch D. Robison
University of Illinois at Urbana-Champaign
	
CSNET: robison@UIUC.CSNET
UUCP: {pur-ee,convex}!uiucdcs!robison
ARPA: robison@CS.UIUC.EDU (robison@UIUC.ARPA)