How can this imperative code be rewritten to be more functional?

Question

I found an answer to SO that explains how to write a randomly weighted drop system for a game. I would rather write this code in a more functional programming style, but I could not figure out how to do this for this code. Here I will write pseudo code:

R = (some random int); T = 0; for o in os T = T + o.weight; if T > R return o; 

How can this be written in a more functional style? I use CoffeeScript and underscore.js, but I would prefer this answer to be a language agnostic because I am having trouble thinking about it in a functional way.

Answer 1

Here are two more functional versions in Clojure and JavaScript, but the ideas here should work in any language that supports closure. Basically, we use recursion instead of iteration to do the same thing, and instead of breaking in the middle, we simply return the value and stop the recursion.

Original pseudo code:

 R = (some random int); T = 0; for o in os T = T + o.weight; if T > R return o; 

Clojure (objects are considered only as Clojure cards):

 (defn recursive-version [r objects] (loop [t 0 others objects] (let [obj (first others) new_t (+ t (:weight obj))] (if (> new_t r) obj (recur new_t (rest others)))))) 

JavaScript version (using underscore for convenience). Be careful because it can push the stack. This is conceptually the same as the Clojure version.

 var js_recursive_version = function(objects, r) { var main_helper = function(t, others) { var obj = _.first(others); var new_t = t + obj.weight; if (new_t > r) { return obj; } else { return main_helper(new_t, _.rest(others)); } }; return main_helper(0, objects); }; 

Answer 2

You can implement this with a fold (aka Array#reduce or Underscore _.reduce ):

SSCCE:

 items = [ {item: 'foo', weight: 50} {item: 'bar', weight: 35} {item: 'baz', weight: 15} ] r = Math.random() * 100 {item} = items.reduce (memo, {item, weight}) -> if memo.sum > r memo else {item, sum: memo.sum + weight} , {sum: 0} console.log 'r:', r, 'item:', item 

You can run it many times on coffeescript.org and see that the results make sense :)

At the same time, I find the bend a little far-fetched, since you must remember both the selected element and the accumulated weight between iterations, and it does not close when the element is found.

Perhaps you can consider the tradeoff between pure FP and the boredom of reimplementing the search algorithm (using _.find ):

 total = 0 {item} = _.find items, ({weight}) -> total += weight total > r 

Runnable example .

I find (not a pun) this algorithm is much more accessible than the first (and it should work better since it does not create intermediate objects and it performs a short circuit).

---

Update / side-note: the second algorithm is not "clean" because the function passed to _.find is not transparently transparent (it has the side effect of changing the external variable total ), but the whole algorithm is transparently transparent. If you have to encapsulate it in the findItem = (items, r) -> function, the function will be clean and will always return the same output for the same input. This is very important because it means that you can get the benefits of FP when using some designs other than FP (for performance, readability, or any other reason) under the hoods: D

Answer 3

I think that the main task is to randomly select "events" (objects) from the os array with a frequency determined by their respective weight s. The approach is to map (i.e., search) a random number (with a uniform distribution) onto the cumulative distribution function of the start function.

With positive weights, their total amount increases from 0 to 1. The code that you gave us is just looking from the end 0. To maximize speed on repeated calls, pre-calculate the amounts and organize events so that at first there are the largest weights.

It doesn’t really matter if you perform an iteration (loop) or recursion search. Recursion is good in a language that tries to be "purely functional" but does not help to understand the underlying mathematical problem. And this will not help you pack the task into a pure function. underscore functions are another way to package iterations, but don't change the main functions. Only any and all exit earlier when the target is found.

For a small os array, this simple search is enough. But with a large array, binary search will be faster. Looking in the underscore , I find that sortedIndex uses this strategy. From Lo-Dash (a underscore dropin): "Uses a binary search to determine the smallest index at which the value should be inserted into the array to maintain the sort order of the sorted array"

The main use of sortedIndex :

 os = [{name:'one',weight:.7}, {name:'two',weight:.25}, {name:'three',weight:.05}] t=0; cumweights = (t+=o.weight for o in os) i = _.sortedIndex(cumweights, R) os[i] 

You can hide the calculation of the total amount using a nested function, for example:

 osEventGen = (os)-> t=0; xw = (t+=y.weight for y in os) return (R) -> i = __.sortedIndex(xw, R) return os[i] osEvent = osEventGen(os) osEvent(.3) # { name: 'one', weight: 0.7 } osEvent(.8) # { name: 'two', weight: 0.25 } osEvent(.99) # { name: 'three', weight: 0.05 } 

---

In coffeescript, a Jed Clinger recursive search can be written as follows:

 foo = (x, r, t=0)-> [y, x...] = x t += y return [y, t] if x.length==0 or t>r return foo(x, r, t) 

The loop version using the same basic idea:

 foo=(x,r)-> t=0 while x.length and t<=r [y,x...]=x # the [first, rest] split t+=y y 

---

Tests for jsPerf http://jsperf.com/sortedindex assume that sortedIndex faster when os.length is around 1000, but slower than a simple loop when the length is greater than 30.