Skip to content

Functional Thinking

May 24, 2010

I ran across an interesting blog post the other day from Jeff Gortatowsky. He has been trying to learn clojure and was having a hard time thinking in a functional manner. It resonated with me because I’ve also found that aspect of clojure to the the most difficult to learn. For the most part, picking up the syntax has been easy but learning to program without actually mutating values is a lot harder.

As part of his learning process he presented an interesting little problem.

take a vector of intra-day stock prices for some particular stock (numbers) and determine the maximum profit you could have made buying that day and selling that day

I made the initial mistake of thinking that the problem involved finding a list of all possible best trades and summing them up. However after reading more carefully the problem only really calls for making a single best trade.

After a bit of thinking it seemed to me the way you’d go about solving this is to look at any given price, find the highest sell price available after that price. By looking at each price in this way you can find which is the best trade.

I gave this a shot myself but ended up with a solution that produced the correct value but had a bug so I won’t both you with the that code. More interesting are some of the solutions other people submitted to this problem.

The first solution is from Lee. I’ve reformatted it to make the structure more clear

(def prices [23, 24, 21, 23, 45, 33, 22, 1, 33, 4, 2, 23])

(defn prof [[p & r]]
  (if (boolean r)
    (cons (-
	   (apply max r)
	   p)
	  [(prof r)])
    -1))

If we run this we get the following results

(prof prices)

=> (22 (21 (24 (22 (-12 (0 (11 (32 (-10 (19 (21 -1)))))))))))

To get the actual answer we need to find the max:

(apply max (flatten (prof prices)))

which gives 32.

This solution isn’t really my favourite but it’s worth going through how it works.

They key to this is that it is recursive. It loops through each value in the list and finds the difference between that value and the maximum in the remainder in the list. Since these datastructures are immutable we end up with a nested list at the end of the computation which then has to be flattened and the maximum calculated.

Mac gives a solution I really like:

(reduce max (map - prices (reductions min prices)))

The function ‘reductions’ is from contrib seq-utils (it will be in core in 1.2 I believe) and I’d never actually run into it before. It turns out it is really useful. Lets take a look at the docs:

Returns a lazy seq of the intermediate values of the reduction (as per reduce) of coll by f, starting with init.

That sounds pretty cool but what does it mean? Lets take a look at what results it produces

(reductions min prices)

;; input: [23, 24, 21, 23, 45, 33, 1, 22, 33, 4, 2, 23]
;; output: (23 23 21 21 21 21 1 1 1 1 1 1)

You can see that it decends from the first number down to the smallest number as it encounters it.

That is pretty cool & all but how does it help us solve the problem? To answer that lets take a look at the next bit.

(map - prices (reductions min prices))

;; output: (0 1 0 2 24 12 0 21 32 3 1 22)

So what is going on here? What’s happening is that the min prices reduction is being subtracted from the prices. Just think that through for a while. The minimum prices reduction represents the smallest value we’ve seen at a particular point in the list. What we’re trying to calculate is the lowest price we can sell at (a min price) and a price we can by at (the current price).

It is a very clever solution and probably not something I would have thought of even if I did know about the reductions function.

Frode has another interesting solution (reformatted for clarity)

(defn calc-profit [prices]
  (first (reduce
	  (fn [[delta low] price]
	    [(max delta (- price low))
	     (min price low)])
	  [0 Integer/MAX_VALUE]
	  prices)))

This wasn’t too easy for me to see what was going on at first glance. We have a reduce that takes an anonymous function, an initial value and the list of prices. The key to understanding this is going to be the anonymous function. The first thing you can see is that it destructures the first parameter into ‘delta’ and ‘low’. The makes sense since the initial value is an array rather a number. The function also returns an array as well. This is a bit different from what I would have expected. Normally if you were to look at a more traditional reduce such as (reduce + [1 2 3]) we’re dealing with the same thing that is actually in the array – plain old numbers. By seeding the reduce with an array however you can use it to hold extra information as we go along and perform the calculation. In this case in the first slot we hold the maximum price differential we’ve seen so far between the current price and the lowest price we’ve seen. In the second slot we hold the lowest price we’ve seen. Once we are done we just take the first value and that is our best profit.

In many ways this is actually very much like the reductions solution. Very elegant although maybe not as clean looking on page.

So there you go. Proof that you can learn a lot from studing other peoples code.

Advertisements

From → Technical

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: