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 co
On 10 May 1998, Carl R. Witty wrote:
> > > qsort [] = []
> > > qsort (x:xs) = let (a,b) = foldr (\y -> (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:
> Ok, clearly I was wrong about list concatenation, but I think I have now
> figured out what was bothering me about Ralf's objection to the of ++.
>
> The argument that the use of ++ in qsort means too many traversals of the
> list makes sense if ++ is strict (or you are using a non-lazy languag
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 xs,foldr
On Sat 09 May, 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!).
Have we? I don't see this, unless the list
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 the two passes may mean
> that some variables can longer fit in r
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)))
Ralf Hinze wrote:
> > > > o it uses (++) to catenate the results of the recursive calls (note that
> > > > (++) takes time proportional to the length of its first argument).
Ok, clearly I was wrong about list concatenation, but I think I have now
figured out what was bothering me about Ralf's o
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))) ([],[]) xs
>in qsort a ++ [x] ++ qsort b
where (#) is
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 th
On 8 May 1998, Carl R. Witty wrote:
> > > Is it necessary that the compiler do this? It strikes me that when the
> > > compiler encounters a function that requires multiple comprehensions of
> > > the same list, it should be smart enough to consolidate them into a single
> > > loop (which would
On 07-May-1998, S. Alexander Jacobson <[EMAIL PROTECTED]> 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
At 20:21 +1000 98/05/08, Fergus Henderson wrote:
>On 07-May-1998, S. Alexander Jacobson <[EMAIL PROTECTED]> wrote:
>> On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote:
>> > > o it uses (++) to catenate the results of the recursive calls (note that
>> > > (++) takes time proportional to the l
Fergus Henderson <[EMAIL PROTECTED]> writes:
> On 07-May-1998, S. Alexander Jacobson <[EMAIL PROTECTED]> wrote:
> > On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote:
(in reference to the following code)
> quicksort []= []
> quicksort (x:xs) = quicksort [y | y <- xs, yy>=x]
> > > > o
At 15:04 -0400 98/05/07, S. Alexander Jacobson wrote:
>> > o it uses (++) to catenate the results of the recursive calls (note that
>> > (++) takes time proportional to the length of its first argument).
>
>This also seems wierd. Concatenation is a frequent enough operation on
>lists. Give suc
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]
> > > o it uses (++) to catenate the results of the recursive calls (note that
> > > (++) takes time proportional to the length of its first argument).
>
> This also seems wierd. Concatenation is a frequent enough operation on
> lists. Give such frequency, shouldn't the internal representatio
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
> comp
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)
> Also it misses a few useful optimizations, such as median-of-three
> partitioning. For descriptions of that and other ways to speed
> up quicksort, see Sedgewicks "Algorithms in C" or "Algorithms in Pascal"
> (I'm afraid Sedgewick didn't write an "Algorithms in Haskell" ;-).
Median of three mo
> The tutorial defines:
>
> quicksort []= []
> quicksort (x:xs) = quicksort [y | y <- xs, yy>=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 included in the tutorial in orde
I want to thank Fergus Henderson and Ralf Hineze for their illuminating
comments on qsort, but I was really more focused on what we can expect
from Haskell compilers. They describe what seem like a lot of gotcha's
that don't need to be there.
On 07-May-1998, Ralf Hinze <[EMAIL PROTECTED]> wrote
The tutorial defines:
quicksort []= []
quicksort (x:xs) = 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.
Is quicksort defined this way because Haskell compilers know how to
23 matches
Mail list logo
