Mercurial > lasercutter

     1 ;;  Copyright (c) Stephen C. Gilardi. All rights reserved.  The use and

     2 ;;  distribution terms for this software are covered by the Eclipse Public

     3 ;;  License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) which can

     4 ;;  be found in the file epl-v10.html at the root of this distribution.  By

     5 ;;  using this software in any fashion, you are agreeing to be bound by the

     6 ;;  terms of this license.  You must not remove this notice, or any other,

     7 ;;  from this software.

     8 ;;

     9 ;;  lazy-seqs

    10 ;;

    11 ;;  == Lazy sequences ==

    12 ;;

    13 ;;  primes - based on the "naive" implemention described in [1] plus a

    14 ;;           small "wheel" which eliminates multiples of 2, 3, 5, and

    15 ;;           7 from consideration by incrementing past them. Also inspired

    16 ;;           by code from Christophe Grand in [2].

    17 ;;

    18 ;;  fibs   - all the Fibonacci numbers

    19 ;;

    20 ;;  powers-of-2 - all the powers of 2

    21 ;;

    22 ;;  == Lazy sequence functions ==

    23 ;;

    24 ;;  (partition-all, shuffle moved to clojure.core)

    25 ;;  (rand-elt moved to clojure.core/rand-nth)

    26 ;;  (rotations, moved to seq_utils.clj)

    27 ;;  (permutations and combinations moved to combinatorics.clj)

    28 ;;

    29 ;;  [1] http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    30 ;;  [2] http://clj-me.blogspot.com/2008/06/primes.html

    31 ;;

    32 ;;  scgilardi (gmail)

    33 ;;  Created 07 June 2008

    34 

    35 (ns 

    36   ^{:author "Stephen C. Gilardi",

    37      :doc "

    38 ==== Lazy sequences ====

    39 

    40  primes - based on the \"naive\" implemention described in [1] plus a

    41           small \"wheel\" which eliminates multiples of 2, 3, 5, and

    42           7 from consideration by incrementing past them. Also inspired

    43           by code from Christophe Grand in [2].

    44 

    45  fibs   - all the Fibonacci numbers

    46 

    47  powers-of-2 - all the powers of 2

    48 

    49  ==== Lazy sequence functions ====

    50 

    51  (partition-all, shuffle moved to clojure.core)

    52  (rand-elt moved to clojure.core/rand-nth)

    53  (rotations, rand-elt  moved to seq_utils.clj)

    54  (permutations and combinations moved to combinatorics.clj)

    55 

    56  [1] http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

    57  [2] http://clj-me.blogspot.com/2008/06/primes.html

    58 "}

    59   clojure.contrib.lazy-seqs

    60   (:use clojure.contrib.def))

    61 

    62 ; primes cannot be written efficiently as a function, because

    63 ; it needs to look back on the whole sequence. contrast with

    64 ; fibs and powers-of-2 which only need a fixed buffer of 1 or 2

    65 ; previous values.

    66 (defvar primes

    67   (concat 

    68    [2 3 5 7]

    69    (lazy-seq

    70     (let [primes-from

    71 	  (fn primes-from [n [f & r]]

    72 	    (if (some #(zero? (rem n %))

    73 		      (take-while #(<= (* % %) n) primes))

    74 	      (recur (+ n f) r)

    75 	      (lazy-seq (cons n (primes-from (+ n f) r)))))

    76 	  wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2

    77 			6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6

    78 			2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]

    79       (primes-from 11 wheel))))

    80   "Lazy sequence of all the prime numbers.")

    81 

    82 (defn fibs

    83   "Returns a lazy sequence of all the Fibonacci numbers."

    84   []

    85   (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

    86 

    87 (defn powers-of-2

    88   "Returns a lazy sequence of all the powers of 2"

    89   []

    90   (iterate #(bit-shift-left % 1) 1))
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 21 Aug 2010 06:25:44 -0400
parents
children