From: A. Rogowski
Subject: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <3DEE0989.5090401@gik.pw.edu.pl>
Hi!
I've just started learning CL but I'm also interested in functional 
programming.
I've found an example of implementing quicksort algorithm in Haskell and 
C (http://www.haskell.org/aboutHaskell.html).
Below is the program written in Haskell.

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                  where
                    elts_lt_x   = [y | y <- xs, y < x]
                    elts_greq_x = [y | y <- xs, y >= x]

It's short and easy to understand. I've tried to write it the same way 
in Common Lisp. Here is my program:

(defun qsort-slist (x l p)
   (remove-if #'(lambda (e)
                  (funcall p e x)) l))

(defun qsort (l)
   (if (null l)
       nil
       (append (qsort(qsort-slist (car l) (cdr l) #'>))
               (list (car l))
               (qsort(qsort-slist (car l) (cdr l) #'<)))))

But this example does not use one of the key features of functional 
languages - lazy evaluation.
Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme 
has lazy lists)? Because it's hard to implement? Because it's not so 
important? Because it's easy to implement it in CL?

-- 
A. Rogowski
···@gik.pw.edu.pl     http://ajr.gik.pw.edu.pl

* No, I will not fix your computer. *

From: Marco Antoniotti
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <y6cadjlu6m9.fsf@octagon.valis.nyu.edu>
"A. Rogowski" <···@gik.pw.edu.pl> writes:

> Hi!
> I've just started learning CL but I'm also interested in functional
> programming.
> I've found an example of implementing quicksort algorithm in Haskell
> and C (http://www.haskell.org/aboutHaskell.html).
> Below is the program written in Haskell.
> 
> qsort []     = []
> qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
>                   where
>                     elts_lt_x   = [y | y <- xs, y < x]
>                     elts_greq_x = [y | y <- xs, y >= x]
> 
> It's short and easy to understand. I've tried to write it the same way
> in Common Lisp. Here is my program:
> 
> (defun qsort-slist (x l p)
>    (remove-if #'(lambda (e)
>                   (funcall p e x)) l))
> 
> (defun qsort (l)
>    (if (null l)
>        nil
>        (append (qsort(qsort-slist (car l) (cdr l) #'>))
>                (list (car l))
>                (qsort(qsort-slist (car l) (cdr l) #'<)))))
> 
> But this example does not use one of the key features of functional
> languages - lazy evaluation.

Have you tried the above in vanilla ML (SML or even Ocaml)?

> Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme
> has lazy lists)? Because it's hard to implement? Because it's not so
> important? Because it's easy to implement it in CL?

As a matter of fact it is relatively easy to achieve similar effects
in CL.  Check out the SERIES package at <http://series.sf.net>.

Cheers

-- 
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
715 Broadway 10th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.
From: Matthew Danish
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <20021204140035.I19796@lain.cheme.cmu.edu>
On Wed, Dec 04, 2002 at 02:56:25PM +0100, A. Rogowski wrote:
> But this example does not use one of the key features of functional 
> languages - lazy evaluation.

Haskell is one of the few functional languages to feature
lazy-evaluation rather than strict call-by-value.  The ML family of
languages (SML, OCaML, etc), as well as Scheme and CL, are the latter.

> Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme 
> has lazy lists)? Because it's hard to implement? Because it's not so 
> important? Because it's easy to implement it in CL?

Quite simply because you cannot have lazy evaluation in a language that
supports side-effects.  Haskell is a purely functional language with
monads, and can get away with it.  Common Lisp is not a purely
functional language and supports many kinds of programming paradigms, as
well as functional.  Characterizing Haskell and CL as being very similar
is a mistake.

Scheme does not have lazy lists, but has FORCE/DELAY constructs (trivial
to implement) which can be used to create such data-structures.

;; A better example of the canonical naive implementation of quick sort
;; This one is a lot more versatile than the examples given previously.
(defun quick-sort (list fn &key (key #'identity))
  (flet ((cull (f) (remove (funcall key (first list)) (rest list)
                           :test f :key key)))
    (when (consp list)
      (append (quick-sort (cull fn) fn :key key)
              (list (first list))
              (quick-sort (cull (complement fn)) fn :key key)))))

Someone else said, in this thread, that lazy-evaluation wouldn't benefit
quick-sort--well, that's not quite true.  It can benefit a great deal if
the delayed code is evaluated concurrently on other processors, as I
discovered in a small experiment recently.  Don't know if Haskell does
this though.

For kicks, here's a LOOP version which is slightly more efficient:

(defun quick-sort (list fn &key (key #'identity))
  (when (consp list)
    (loop with o = (funcall key (first list))   for ei in (rest list)   
          if (funcall fn (funcall key ei) o)  collect ei into low
          else  collect ei into high
          finally (return (append (quick-sort low fn :key key)
                                  (list (first list))
                                  (quick-sort high fn :key key))))))

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Drew McDermott
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <3DEE6A59.3090502@yale.edu>
A. Rogowski wrote:

> 
> But this example does not use one of the key features of functional 
> languages - lazy evaluation.

That's an odd statement to make in this context, given that the meaning 
of the qsort function appears to be identical regardless of whether the 
language has lazy semantics or not.

Let me qualify that: If the input list is infinite, then the non-lazy 
version will diverge, and the lazy version will not.  However, the lazy 
version may not return anything useful.   For instance, if there are an 
infinite number of elements < the first element, the output will be a 
lazy list of just those elements.  Correct, but when would you want that?

Of course, in principle if you don't need more than the first few 
elements of the list (finite or infinite), the lazy version saves you 
something by never generating the later ones.  However, this is a very 
big "in principle."  In practice, lazy languages are almost always much 
harder to implement efficiently than "eager" language.  That's why there 
are so few of them, even in the functional-programming world.

> Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme 
> has lazy lists)? Because it's hard to implement? Because it's not so 
> important? Because it's easy to implement it in CL?

It's easy to implement.  The idea of generating objects one by one 
instead of all at once is quite useful in some contexts, but the context 
  almost always dictates its own interface, which doesn't always look 
like a pipe the caller sucks objects out of.  Making this idea the 
default and burying it inside the list abstraction may make some 
programs look cool and concise, but has yet to be proven practical.

                -- Drew McDermott

P.S. We have big-time Haskell and ML partisans here at Yale.  I'm just a 
Lisp hacker, so they don't mind what I say.
From: A. Rogowski
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <3DEF4D26.5090503@gik.pw.edu.pl>
Drew McDermott wrote:
> A. Rogowski wrote:

>> But this example does not use one of the key features of functional 
>> languages - lazy evaluation.
> That's an odd statement to make in this context, given that the meaning 
> of the qsort function appears to be identical regardless of whether the 
> language has lazy semantics or not.

Yes. I wanted to show that I see you can write CL programs in the 
similar way to this shown in Haskell example if you want to.
But it was so easy because qsort does not make use of lazy eval.

-- 
A. Rogowski
···@gik.pw.edu.pl     http://ajr.gik.pw.edu.pl

* No, I will not fix your computer. *
From: Geoffrey Summerhayes
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <z1uH9.6889$rv5.927471@news20.bellglobal.com>
"A. Rogowski" <···@gik.pw.edu.pl> wrote in message ·····················@gik.pw.edu.pl...

Lots of comments...

>
> (defun qsort-slist (x l p)
>    (remove-if #'(lambda (e)
>                   (funcall p e x)) l))


You have a lot more choices for variables names than other languages
so it's much easier to self-document code with clearer, complete names:

(defun qsort-slist (pivot list test)
  (remove-if #'(lambda (item)
                 (funcall test item pivot)) list))

> (defun qsort (l)
>    (if (null l)
>        nil
>        (append (qsort(qsort-slist (car l) (cdr l) #'>))
>                (list (car l))
>                (qsort(qsort-slist (car l) (cdr l) #'<)))))

Shouldn't the second test be #'<= ? You may find the function COMPLEMENT
interesting.

You should take a look to see how SORT declares its argument list
and how flexible QSORT could be with very minor changes.

Minor style point-When dealing with lists, a fair number of people
prefer using '(), ENDP, FIRST, REST, instead of NIL, NULL, CAR, CDR
respectively to indicate they are working with lists and not just
cons cells. You'll come across both.

> But this example does not use one of the key features of functional
> languages - lazy evaluation.
> Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme
> has lazy lists)? Because it's hard to implement? Because it's not so
> important? Because it's easy to implement it in CL?
>

If you stick to lists, it would be more efficient to partition the list
than running remove-if on the list twice, see PUSH, VALUES, and MULTIPLE-VALUE-BIND
as hints on how to write PARTITION-LIST. Of course you won't get the same level of
delayed evaluation if you implement the delay.

http://www.norvig.com/paip/auxfns.lisp
-- search for delayed --

Test:
--------------
> (let ((x (delay (+ 3 2))))
    (print x)
    (print (if (delay-p x)(force x) x)) ; necessary if x can be other than a delay
    (print x)
    (print (force x)))

#S(DELAY VALUE #'(LAMBDA NIL (+ 3 2)) COMPUTED? NIL)
5
#S(DELAY VALUE 5 COMPUTED? T)
5
5
--------------

So if you just want to delay at the top-level it's fairly simple.

If you want to delay the sort all the way down, you'll have to write force versions
of qsort and the accessors you plan to use and probably alter delay and force to make
them more list friendly.

;;; Completely and totally untested - First attempt
;;; can't emphasize this enough - Caveat Emptor, YGWYPF, etc.

(defun force-first(list)
  (cond ((listp list) (first list))       ; regular list
        ((delay-list-p list)              ; delayed list
         (let ((forced (force-list list)))
           (if (and (listp forced)                 ; to the OP - is this sufficient?
                    (delay-list-p (first forced))) ; Why or why not?
               (force-first (first forced))
             forced)))
        (t (error "~S is not a list." list))))

The next thing to do, perhaps, is eliminate pesky already evaluated delays from a
list...

It does take work, it can be done, is it worth the effort? As always, it depends. :-)

--
Geoff
From: Friedrich Dominicus
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <87y975kdig.fsf@fbigm.here>
"A. Rogowski" <···@gik.pw.edu.pl> writes:

> 
> 
> (defun qsort-slist (x l p)
>    (remove-if #'(lambda (e)
>                   (funcall p e x)) l))
> 
> (defun qsort (l)
>    (if (null l)
>        nil
>        (append (qsort(qsort-slist (car l) (cdr l) #'>))
>                (list (car l))
>                (qsort(qsort-slist (car l) (cdr l) #'<)))))
> 
> But this example does not use one of the key features of functional
> languages - lazy evaluation.
Lazy evaluation is not a key feature of functional programming. There
are probably more functional non lazy languages around than lazy
ones. The point with functional programming is knitting functons
together. In the case of a sort it does not help you to have a lazy
language. You want the whole stuff sorted won't you?

The qsort examples is terse but surely not fast. You could check it I
bet with converoin list->array->list will it be faster than the shown
version. 

Regards
Friedrich
From: Hannah Schroeter
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <ast46e$9b5$1@c3po.schlund.de>
Hello!

Friedrich Dominicus  <·····@q-software-solutions.com> wrote:
>[...]

>language. You want the whole stuff sorted won't you?

Depends.

In the Heapsort algorithm, you can do the first step (building the
heap) in O(n) and find a minimum/maximum element in O(1). If you
perform a heapsort with lazy second step (extraction of the elements
in sorted order), and the consumer only pulls out k elements, you
have complexity O(n + k log n) instead of O(n log n), which *might*
be faster.

>The qsort examples is terse but surely not fast. You could check it I
>bet with converoin list->array->list will it be faster than the shown
>version. 

Or doing a list based merge sort, if the input and output are specified
to be lists at all.

>Regards
>Friedrich

Kind regards,

Hannah.
From: Friedrich Dominicus
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <87el8tlpcm.fsf@fbigm.here>
······@schlund.de (Hannah Schroeter) writes:

> 
> >The qsort examples is terse but surely not fast. You could check it I
> >bet with converoin list->array->list will it be faster than the shown
> >version. 
> 
> Or doing a list based merge sort, if the input and output are specified
> to be lists at all.
Well this is the "rigth thing" to do IMHO. Using algorithms which work
well for the choosen datastructure. And that's just what I wanted to
say. The shown algorithm is terst, but definitly does not deserve the
"quick" in it.

Regards
Friedrich
From: Erik Pearson
Subject: Re: Newbie question - Haskell, CL & lazy evaluation
Date: 
Message-ID: <3bf040a2.0212041751.17cfaac8@posting.google.com>
"A. Rogowski" <···@gik.pw.edu.pl> wrote in message news:<················@gik.pw.edu.pl>...
> Hi!
> I've just started learning CL but I'm also interested in functional 
> programming.
> I've found an example of implementing quicksort algorithm in Haskell and 
> C (http://www.haskell.org/aboutHaskell.html).
> Below is the program written in Haskell.
> 
> qsort []     = []
> qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
>                   where
>                     elts_lt_x   = [y | y <- xs, y < x]
>                     elts_greq_x = [y | y <- xs, y >= x]
> 
> It's short and easy to understand. I've tried to write it the same way 
> in Common Lisp. Here is my program:

Hi,

To address this point (i.e. short and clear) this version is perhaps a
little closer:

(defun qsort (l)
  (when l
    (append (qsort (remove (car l) (cdr l) :test #'<))
            (list (car l))
            (qsort (remove (car l) (cdr l) :test #'>=)))))

(also, minor issue, the original one didn't use >= but rather >, and
produced incorrect results with duplicate elements.)

Erik.

> 
> (defun qsort-slist (x l p)
>    (remove-if #'(lambda (e)
>                   (funcall p e x)) l))
> 
> (defun qsort (l)
>    (if (null l)
>        nil
>        (append (qsort(qsort-slist (car l) (cdr l) #'>))
>                (list (car l))
>                (qsort(qsort-slist (car l) (cdr l) #'<)))))
> 
> But this example does not use one of the key features of functional 
> languages - lazy evaluation.
> Here is my question: why doesn't CL have lazy evaluation (AFAIK scheme 
> has lazy lists)? Because it's hard to implement? Because it's not so 
> important? Because it's easy to implement it in CL?