1

我正在处理 4clojure 问题，并且不断出现类似的问题。我将编写一个适用于除一个测试用例之外的所有测试用例的解决方案。它通常是检查惰性求值的那个。下面的解决方案适用于除最后一个测试用例之外的所有测试用例。我已经尝试了各种解决方案，但似乎无法让它停止评估，直到整数溢出。我阅读了 Joy of Clojure 中关于惰性序列的章节，但我很难实现它们。有没有我忘记的经验法则，比如不要使用循环或类似的东西？

; This version is non working at the moment, will try to edit a version that works
(defn i-between [p k coll]
  (loop [v [] coll coll]
     (let [i (first coll) coll (rest coll) n (first coll)]
        (cond (and i n)
          (let [ret (if (p i n) (cons k (cons i v)) (cons i v))]
            (recur ret coll))
          i
          (cons i v )
        :else  v))))

问题 132

好奇者的终极解决方案：

(fn i-between [p k coll]
  (letfn [(looper [coll]
     (if (empty? coll) coll
       (let [[h s & xs] coll 
          c (cond (and h s (p h s))
                   (list h k )
                  (and h s)
                   (list h )
                  :else (list h))]
          (lazy-cat c (looper (rest coll))))
   ))] (looper coll)))
4

1 回答 1

3

When I think about lazy sequences, what usually works is thinking about incremental cons'ing

That is, each recursion step only adds a single element to the list, and of course you never use loop.

So what you have is something like this:

(cons (generate first) (recur rest))

When wrapped on lazy-seq, only the needed elements from the sequence are realized, for instance.

 (take 5 (some-lazy-fn))

Would only do 5 recursion calls to realize the needed elements.

A tentative, far from perfect solution to the 4clojure problem, that demonstrates the idea:

(fn intercalate 
  [pred value col]
  (letfn [(looper [s head]
            (lazy-seq 
              (if-let [sec (first s)]
                (if (pred head sec)
                  (cons head (cons value (looper (rest s) sec)))
                  (cons head (looper (rest s) sec)))
               (if head [head] []))))]
    (looper (rest col) (first col))))

There, the local recursive function is looper, for each element tests if the predicate is true, in that case realizes two elements(adds the interleaved one), otherwise realize just one.

Also, you can avoid recursion using higher order functions

(fn [p v xs]
   (mapcat
    #(if (p %1 %2) [%1 v] [%1])
    xs
    (lazy-cat (rest xs) (take 1 xs))))

But as @noisesmith said in the comment, you're just calling a function that calls lazy-seq.

于 2013-11-07T02:25:30.983 回答