How to return a lazy sequence from a loop recur with a conditional in Clojure?

Question

Still very new to Clojure and programming in general so forgive the stupid question.

The problem is:

Find n and k such that the sum of numbers up to n (exclusive) is equal to the sum of numbers from n+1 to k (inclusive).

My solution (which works fine) is to define the following functions:

(defn addd [x] (/ (* x (+ x 1)) 2))
(defn sum-to-n [n] (addd(- n 1)))
(defn sum-to-k [n=1 k=4] (- (addd k) (addd n)))
(defn is-right[n k]
  (= (addd (- n 1)) (sum-to-k n k)))

And then run the following loop:

 (loop [n 1 k 2]
  (cond 
   (is-right n k) [n k]
   (> (sum-to-k n k) (sum-to-n n) )(recur (inc n) k)
   :else (recur n (inc k))))

This only returns one answer but if I manually set n and k I can get different values. However, I would like to define a function which returns a lazy sequence of all values so that:

(= [6 8] (take 1 make-seq))

How do I do this as efficiently as possible? I have tried various things but haven't had much luck.

Thanks

:Edit:

I think I came up with a better way of doing it, but its returning 'let should be a vector'. Clojure docs aren't much help...

Heres the new code:

(defn calc-n [n k]
(inc (+ (* 2 k) (* 3 n))))

(defn calc-k [n k]
(inc (+ (* 3 k)(* 4 n))))

(defn f
   (let [n 4 k 6]
      (recur (calc-n n k) (calc-k n k))))

(take 4 (f))

Answer 1

Yes, you can create a lazy-seq, so that the next iteration will take result of the previous iteration. Here is my suggestion:

(defn cal [n k]
   (loop [n n k k]
     (cond
       (is-right n k) [n k]
       (> (sum-to-k n k) (sum-to-n n) )(recur (inc n) k)
       :else (recur n (inc k)))))

(defn make-seq [n k]
  (if-let [[n1 k1] (cal n k)]
      (cons [n1 k1] 
            (lazy-seq (make-seq (inc n1) (inc k1))))))

 (take 5 (make-seq 1 2)) 
 ;;=>  ([6 8] [35 49] [204 288] [1189 1681] [6930 9800])

Answer 2

just generating lazy seq of candidatess with iterate and then filtering them should probably be what you need:

(def pairs
  (->> [1 2]
       (iterate (fn [[n k]]
                  (if (< (sum-to-n n) (sum-n-to-k n k))
                    [(inc n) k]
                    [n (inc k)])))
       (filter (partial apply is-right))))

user> (take 5 pairs)
;;=> ([6 8] [35 49] [204 288] [1189 1681] [6930 9800])

semantically it is just like manually generating a lazy-seq, and should be as efficient, but this one is probably more idiomatic

Answer 3

If you don't feel like "rolling your own", here is an alternate solution. I also cleaned up the algorithm a bit through renaming/reformating.

The main difference is that you treat your loop-recur as an infinite loop inside of the t/lazy-gen form. When you find a value you want to keep, you use the t/yield expression to create a lazy-sequence of outputs. This structure is the Clojure version of a generator function, just like in Python.

(ns tst.demo.core
  (:use tupelo.test )
  (:require [tupelo.core :as t] ))

(defn integrate-to [x]
  (/ (* x (+ x 1)) 2))
(defn sum-to-n [n]
  (integrate-to (- n 1)))
(defn sum-n-to-k [n k]
  (- (integrate-to k) (integrate-to n)))
(defn sums-match[n k]
  (= (sum-to-n n) (sum-n-to-k n k)))

(defn recur-gen []
  (t/lazy-gen
    (loop [n 1 k 2]
      (when (sums-match n k)
        (t/yield [n k]))
      (if (< (sum-to-n n) (sum-n-to-k n k))
        (recur (inc n) k)
        (recur n (inc k))))))

with results:

-------------------------------
   Clojure 1.10.1    Java 13
-------------------------------

(take 5 (recur-gen)) => ([6 8] [35 49] [204 288] [1189 1681] [6930 9800])

You can find all of the details in the Tupelo Library.

Answer 4

This first function probably has a better name from math, but I don't know math very well. I'd use inc (increment) instead of (+ ,,, 1), but that's just personal preference.

(defn addd [x]
  (/ (* x (inc x)) 2))

I'll slightly clean up the spacing here and use the dec (decrement) function.

(defn sum-to-n [n]
  (addd (dec n)))

(defn sum-n-to-k [n k]
  (- (addd k) (addd n)))

In some languages predicates, functions that return booleans, have names like is-odd or is-whatever. In clojure they're usually called odd? or whatever?. The question-mark is not syntax, it's just part of the name.

(defn matching-sums? [n k]
  (= (addd (dec n)) (sum-n-to-k n k)))

The loop special form is kind of like an anonymous function for recur to jump back to. If there's no loop form, recur jumps back to the enclosing function. Also, dunno what to call this so I'll just call it f.

(defn f [n k]
  (cond
    (matching-sums? n k) [n k]
    (> (sum-n-to-k n k) (sum-to-n n)) (recur (inc n) k)
    :else (recur n (inc k))))

(comment

  (f 1 2) ;=> [6 8]

  (f 7 9) ;=> [35 49]

  )

Now, for your actual question. How to make a lazy sequence. You can use the lazy-seq macro, like in minhtuannguyen's answer, but there's an easier, higher level way. Use the iterate function. iterate takes a function and a value and returns an infinite sequence of the value followed by calling the function with the value, followed by calling the function on that value etc.

(defn make-seq [init]
  (iterate (fn [n-and-k]
             (let [n (first n-and-k)
                   k (second n-and-k)]
               (f (inc n) (inc k))))
           init))

(comment

  (take 4 (make-seq [1 2])) ;=> ([1 2] [6 8] [35 49] [204 288])
  )

That can be simplified a bit by using destructuring in the argument-vector of the anonymous function.

(defn make-seq [init]
  (iterate (fn [[n k]]
             (f (inc n) (inc k)))
           init))

Edit: About the repeated calculations in f.

By saving the result of the calculations using a let, you can avoid calculating addd multiple times for each number.

(defn f [n k]
  (let [to-n (sum-to-n n)
        n-to-k (sum-n-to-k n k)]
    (cond
      (= to-n n-to-k) [n k]
      (> n-to-k to-n) (recur (inc n) k)
      :else (recur n (inc k)))))