More functional way to do this?

Question

This post of mine discusses Thomson's paradox, and simulates it in Clojure. The state function returns the state of the lamp at time = t.

(defn thomsons-lamp []
  (iterate (fn [[onoff dur]]
             [(not onoff) (/ dur 2)])
           [true 1])) 

(defn state [t]
  (let [t-vals (map second (thomsons-lamp))]
    (loop [i 1]
      (if (<= t (apply + (take i t-vals)))
        ((comp first last) (take i (thomsons-lamp)))
        (recur (inc i))))))

How do I define a cleaner state function (preferably without loop/recur)?

Answer 1

The only sins here are

• Unnecessary quadratic complexity in state
• Evidence of floating point usage and error in your blog post. The code as written should be using ratios -- (state 2) should not terminate...

Reduce/reduced would be a good candidate for your state function.

(defn thomsons-lamp []
  (map vector (iterate not true) (iterate #(* 1/2 %) 1)))

(defn state [t]
  (reduce (fn [[s1 t1] [s2 t2]] 
            (if (>= t1 t) (reduced s1) [s2 (+ t1 t2)]))
          (thomsons-lamp)))

Answer 2

A one-line solution in Clojure

In Clojure, though not in ClojureScript, we can express the state function as a series of pure function applications:

(defn state [t]
  (-> t rationalize / biginteger .bitLength odd?))

or, without using the threading macro

(defn state [t]
  (odd? (.bitLength (biginteger (/ (rationalize t))))))

Let's test it:

(map (juxt identity state) [1 0.7 0.5 0.4 0.3 0.2])
; ([1 true] [0.7 true] [0.5 false] [0.4 false] [0.3 false] [0.2 true])

Taking it step by step:

(defn state [t]
  (-> t
      rationalize ; convert to a ratio to avoid losing precision using floating point
      /           ; take the reciprocal
      biginteger  ; round down (if need be) to a java.math.BigInteger 
      .bitLength  ; take its length in bits (a method, not a Clojure function)
      odd?        ; ask whether odd
      ))

How does it work?

Instead of testing where the given number t fits in the series of toggle-points

1 1/2 1/4 1/8 ...

we test where 1/t (that's (/ t) in Clojure) fits in the series of inverted toggle-points

1 2 4 8 ... 

which, in binary, is

1 10 100 1000 ... 

which are the smallest numbers with

1 2 3 4 ... 

binary digits.

Applying BigInteger/bitLength tells us how many binary digits 1/t has - rounding down has no effect. This is the number of terms of series 1 2 4 8 ... that 1/t reaches. So the answer is whether this number is odd.