On 10-May-1998, S. Alexander Jacobson [EMAIL PROTECTED] wrote:
On Fri, 8 May 1998, Fergus Henderson wrote:
Note that consolidating multiple passes into single passes is not
always a win. For example, if your machine has 10 available registers,
and each pass uses 8 of them, then combining
On May 10 (18:58 -0300), Mariano Suarez Alvarez wrote with possible deletions:
| [...]
| The same idea works in general: if E is some expression,
|
| E (foldr f1 b1 xs) (foldr f2 b2 xs)
| = let (a,b) = (foldr f1 b1 xs,foldr f2 b2 xs)
| in E a b
| = let (a,b) = (foldr f1 b1
On 10 May 1998, Carl R. Witty wrote:
qsort [] = []
qsort (x:xs) = let (a,b) = foldr (\y - (y ?: (x) # y ?: (=x))) ([],[]) xs
in qsort a ++ [x] ++ qsort b
f # g = \(x,y) - (f x,g y)
x ?: p = if p x then (x:) else id
qsort' [] = []
qsort' (x:xs) =
At 18:39 -0300 98/05/09, Mariano Suarez Alvarez wrote:
The problem is that something like (head (qsort [whatever])) is not strict
in the whole resulting sorted list, so merging the comprehensions is not a
win but a loss (a big loss: now we've got bottom!).
If the compiler could prove that the
Mariano Suarez Alvarez [EMAIL PROTECTED] writes:
qsort can be rewritten (by the compiler, ideally...) so that the list is
traverse once, without losing any laziness:
infix 5 #
infix 6 ?:
Define
qsort [] = []
qsort (x:xs) = let (a,b) = foldr (\y - (y ?: (x) # y ?: (=x)))
On 07-May-1998, Ralf Hinze [EMAIL PROTECTED] wrote:
I guess it is only included in the tutorial in order to demonstrate the
use of list comprehensions. You are right, the definition has several
drawbacks (besides the fact that quicksort (aka slowsort) is _really_ a
bad sorting algorithm).
On Thu 07 May, S. Alexander Jacobson wrote:
On 07-May-1998, Ralf Hinze [EMAIL PROTECTED] wrote:
o it traverses the list twice,
o it has a space leak (xs is alive until the second traversal is done),
Is it necessary that the compiler do this? It strikes me that when the
compiler
At 15:04 -0400 98/05/07, S. Alexander Jacobson wrote:
You recursively partition the list based on the first character not
already processed. So if you have a list like:
[alex,fergus,robert,allen,frank,ralf]
At the next stage you have:
[(a,[alex,allen]),(f,[fergus,frank]),(r,[robert,ralf])]
The tutorial defines:
quicksort []= []
quicksort (x:xs) = quicksort [y | y - xs, yx ] ++ [x] ++ quicksort [y | y - xs,
y=x]
This code strikes me as twice as slow as it could be because it seems to
requires two loops through the list on each recursive call.
I guess it is only