matiPlayground

object Solution {

  /**
    * Use these utility functions to solve the assignment.
    */
  def util =
    """
      (zip-with
        (lambda (f xs ys)
          (if (and (is-nil xs) (is-nil ys))
            nil
            (cons
              (f (head xs) (head ys))
              (zip-with f (tail xs) (tail ys))))))
      (map
        (lambda (f xs)
          (if (is-nil xs) nil
            (cons (f (head xs)) (map f (tail xs))))))
      (diff
        (lambda (xs ys)
          (if (is-nil xs)
            nil
            (if (is-nil ys)
              xs
              (if (num< (head xs) (head ys))
                (cons (head xs) (diff (tail xs) ys))
                (if (num= (head xs) (head ys))
                  (diff (tail xs) (tail ys))
                  (diff xs (tail ys))))))))
      (take
        (lambda (n xs)
          (if (num= n 0)
            nil
            (cons (head xs) (take (- n 1) (tail xs))))))
    """

  /**
    * Using these utilities, we can define a stream of natural numbers:
    */
  def nats =
    """
      (letrec ("""+util+"""
               (nats (cons 0 (map (lambda (x) (+ x 1)) nats))))
        nats)
    """

  /**
    * Write a program that returns a stream of even natural numbers.
    */

  // helper
  // def timesTwo = "(lambda (x) (* 2 x))"
  // def evens =
  //   s"""
  //   (let ((timesTwo (lambda (x) (* 2 x))))
  //   (map timesTwo nats)
  //   )
  //   """

  // def evens = """
  //     (letrec ("""+util+"""
  //              (evens (cons 0 (map (lambda (x) (* x 2)) evens))))
  //       nats)
  //   """

  def evens =
  """
      (letrec ("""+util+"""
               (evens (cons 0 (map (lambda (x) (+ x 2)) evens))))
        evens)
    """
  //  """
  //     (letrec ("""+util+"""
  //              (evensss (cons 0 (map (lambda (x) (* (+ x 1) 2)) evensss))))
  //       evensss)
  //   """

  /**
    * Use the the `evens`, `nats`, and `diff` functions to define a stream of
    * odd natural numbers.
    */
  def odds =
    """
      (letrec ("""+util+"""
               (nats (cons 0 (map (lambda (x) (+ x 1)) nats)))
               (evens (cons 0 (map (lambda (x) (+ x 2)) evens))))
        (diff nats evens))
    """

  /**
    * Define a function `multiples` that takes a number `n` as input and returns
    * a stream containing all multiples of `n`.
    */
  def multiples =

  """
  (letrec ("""+util+"""
               (nats (cons 1 (map (lambda (x) (+ x 1)) nats)))
               (mults (lambda (n) (map (lambda (x) (* x n)) nats)))
               )
        mults)
  """


// Alternative:

  // """
  //   (letrec ((zip-with
  //       (lambda (f xs ys)
  //         (if (and (is-nil xs) (is-nil ys))
  //           nil
  //           (cons
  //             (f (head xs) (head ys))
  //             (zip-with f (tail xs) (tail ys))))))
  //     (map
  //       (lambda (f xs)
  //         (if (is-nil xs) nil
  //           (cons (f (head xs)) (map f (tail xs))))))
  //     (diff
  //       (lambda (xs ys)
  //         (if (is-nil xs)
  //           nil
  //           (if (is-nil ys)
  //             xs
  //             (if (num< (head xs) (head ys))
  //               (cons (head xs) (diff (tail xs) ys))
  //               (if (num= (head xs) (head ys))
  //                 (diff (tail xs) (tail ys))
  //                 (diff xs (tail ys))))))))
  //     (take
  //       (lambda (n xs)
  //         (if (num= n 0)
  //           nil
  //           (cons (head xs) (take (- n 1) (tail xs))))))
  //     (mult (lambda (n) (cons n (map (lambda (x) (+ x n)) (mult n))))))

  //   mult)

  // """





  /**
    * Define a function that returns a stream of primes, using the sieve of Eratosthenes:
    * https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    *
    * Hint: you can use `nats`, `diff`, and `multiples`
    */
  def eratosthenes =


    """
 (letrec (
           (zip-with
        (lambda (f xs ys)
          (if (and (is-nil xs) (is-nil ys))
            nil
            (cons
              (f (head xs) (head ys))
              (zip-with f (tail xs) (tail ys))))))
      (map
        (lambda (f xs)
          (if (is-nil xs) nil
            (cons (f (head xs)) (map f (tail xs))))))
      (diff
        (lambda (xs ys)
          (if (is-nil xs)
            nil
            (if (is-nil ys)
              xs
              (if (num< (head xs) (head ys))
                (cons (head xs) (diff (tail xs) ys))
                (if (num= (head xs) (head ys))
                  (diff (tail xs) (tail ys))
                  (diff xs (tail ys))))))))
      (take
        (lambda (n xs)
          (if (num= n 0)
            nil
            (cons (head xs) (take (- n 1) (tail xs))))))
      (nats (cons 1 (map (lambda (x) (+ x 1)) nats)))
      (mults (lambda (n) (map (lambda (x) (* x n)) nats)))
      (sieve (lambda (er) (cons (head er) (sieve (diff er (mults (head er)))))))
      (primes (sieve (map (lambda (x) (+ x 1)) nats))))
        primes)
  """





}