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