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)?

That looks like a perfectly fine and functional way of going about this. There is nothing inherently un-functional about loop/recur. — Arthur Ulfeldt, May 01 '14 at 20:19
Well, the second function has unnecessarily quadratic complexity. It could be written fairly cleanly using reduce/reduced. — A. Webb, May 01 '14 at 21:33
More than a year ago, I came across your post and glanced over it briefly, with the intention to go through it more closely later. When I went back to find it, later, however, I could not remember the name of the paradox. No amount of googling got me anywhere. Today, I coincidentally came across the name Thomson's Lamp in a VSauce video on YouTube and googled "Thomson's Lamp Clojure", which brought me here! — kurofune, Dec 13 '15 at 21:18
I was wondering if you could help me by answering this: Since the experiment of switching the light leads to an infinite non-convergent mathematical series, how could a program simulate it? I am assuming that this is what you code do, I have no knowledge of functional programming. Thanks. — NoChance, Mar 06 '16 at 17:21
@NoChance the `iterate` function returns a lazy list, ie, a list whose elements are computed on demand. The code says how to generate the nth element, but a particular element is computed only when someone tries to access it. — divs1210, Jun 23 '17 at 19:23

score 3 · Accepted Answer · answered May 01 '14 at 21:41

3

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)))

answered May 01 '14 at 21:41

A. Webb

26,227
1
63
95

1

Regarding second bullet, I reckon you are using ClojureScript, eh? – A. Webb May 01 '14 at 21:51
ClojureScript, yes. In fact, it is awesome how easy it is to work on such a high level language in just your browser, without setting up any environment whatsoever. I knew the ratio/floating-point thing was causing a problem, but didn't care enough. Thank you for the answer! – divs1210 May 02 '14 at 08:06

Thumbnail · Answer 2 · 2014-05-06T08:53:18.617

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.

@divs1210 Thanks. I'm not sure that this solution is any faster in a [big theta](http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on) sense, but its constants are going to be a lot better - and it was fun to do. — Thumbnail, May 25 '14 at 02:49

More functional way to do this?

2 Answers2

Linked