Home Original page

Why don't people like lisp?

Joe Marshall jrm at ccs.neu.edu
Fri Oct 24 11:03:11 EDT 2003 
ddarius at hotpop.com (Darius) writes:

> pythagoreanTriples n =
>     [ (opposite,adjacent,hypotenuse) |
>         opposite   <- [1..n],
>         adjacent   <- [1..n],
>         hypotenuse <- [1..n],
>         opposite^2 + adjacent^2 == hypotenuse^2]
>
> {- or with alternative syntax
> pythagoreanTriples n = do
>     opposite   <- [1..n]
>     adjacent   <- [1..n]
>     hypotenuse <- [1..n]
>     guard (opposite^2 + adjacent^2 == hypotenuse^2)
>     return (opposite,adjacent,hypotenuse)
> -}
>
>> and (pythagorean-triples 10)
>> would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
>
> *Main> pythagoreanTriples 10
> [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
>
> Oops!  Wrong language.  Also forgot to extend the language. *sigh* I
> can't do anything right.

Yes, the suggestion was extending the language to support
nondeterminism.  That particular problem was illustrative, but it can
obviously be solved via nested looping.

I think this one may be more difficult:

In a directed graph a `k-simple' path is a path from a vertex U to a
vertex V that does not contain any vertex more than K times.  A simple
non-deterministic algorithm for enumerating the k-simple paths between
two verticies is this:

(defun k-simple-paths (u v k)
  (if (= (node-visits u) k) (fail))
  (local (incf (node-visits u)))
  (either (progn (unless (eq u v) (fail)) (list u))
          (cons u (k-simple-paths (a-member-of (node-children node)) v k))))

(defun a-member-of (x)
  (if (null x) (fail))
  (either (car x) (a-member-of (cdr x))))

The LOCAL macro arranges for the side effects in its body to be undone
upon failure.  Assume that a node is a structure with a field that can
be used to count visits and a field that contains a list of children.

> (posted mostly for my own amusement though I am interested in how the
> rangeOfRanges example is handled)

I'll try it out when I get home.  My work computer does not have
Screamer installed.
More information about the Python-list mailing list