We all know it's hard to think. One of my previous employers always famously said "Thinking is hard work. If it wasn't, everyone would be doing it.". So I just want to share something that happened to me this morning, to illustrate this point. And also how you shouldn't just always write down the first thing that comes to mind.
So, I had a list: [a,b,c,d,e]. I wanted to get the "pairs" in this list. So basically, I wanted a function f(l), that given [a,b,c,d,e] would give me [[a,b],[b,c],[c,d],[d,e],[e,a]]. I wanted to use this to draw lines, connecting a bunch of points. (Note: it is important that the last element in the list connects to the first, otherwise I'll have a gap in my line drawing)
So, the classical way to do this, would be to go ahead and code up something like:
This works. But it's not particularly elegant, and it has a special case for the last entry, which I don't like, and would like to avoid. Also, it's very specific - I can't easily change it to pair n and n+2, or n,n+1,n+2 for example (Not that I need it at the moment, but still, its a very *specific* implementation.
So then I thought, what about taking the list, and zipping f(x) = x, with f(x) = x + 1, over the length of the array. That would give me the indexes of the pairs. So, I would end up with a list like: [[0,1],[1,2],[2,3],...] etc. and then I could just use that list, and map over it to get the appropriate elements in the original list. I could even then zip additional lists as well, for eg. f(x) = x + 2, f(x) = x + 3 which will give me 4-element pairs. Nice.
Problem solved right? On further inspection - not really. There is still a MASSIVE edge case there at the end. In fact, with this solution, the edge case is probably even more difficult to manage then in the purely imperative form. So I decided, I'm not even gonna code up the solution like this, cos I haven't yet had enough caffeine to deal with this edge case mess.
So then I realised, that basically what I want to do, is "rotate" the original list, and zip the original one, with the rotated one. Yes, good old ROT-n. So I take my input list, rot-1 it, and then map the input list with this rotated list. This gives me _exactly_ what I want, and also solves the edge case problem for me very elegantly! I now also have the ability to pair an arbitrary number of elements from the list, by just rot-1'ing, then rot-2'ing, then rot-3'ing, and then zipping all these lists together. Very nice.
But now, I need a rot-n function. Javascript (or underscore) doesn't have one, so I'm gonna have to implement my own. Dammit, right? Remember those varsity excercises where we did rot-13 in like first year? Not really lus to implement this right now! And then, what will I gain, really? Then I could just my original implementation!
Then, I had a quick chat with Gary, and we came to the conclusion, that a rot-n list, is simply the concatenation of the tail of the list, from (n,length), with the head of the list from (0,n). This makes my job much, much easier. Turns out, rot-n in Javascript looks as follows:
So, armed with that, my original solution simply becomes:
Much nicer hey? And also, more general. And I sommer got a rot-n function out of the deal as well!
This was just my latest example of how it helped me to think things throught a bit before I start to write the solution. I'm very much a Just Do It guy, but it's good to sit back and think, you tend to get much more out of it then what you just intended to write.
I'm not that much experienced with Javascript and functional Java. I know I should be... but, I simply don't get the time. Algorithms I love of course! You could also use modulus to solve the above problem. Something along the lines of:
ReplyDeletevar f = function (l) { var paired = []; for (var i = 0; i < l.length; i++) { paired.push([l[i], l[(i+1) % l.length]]); } return paired;}It should work... I've only compiled and executed it on my wetware processor (which has a few bugs :)).
This is how the algorithm should look :) Examples in Scala and Haskell:
ReplyDeletescala> def rot[A](n: Int): List[A] => List[A] = l => l.drop(n) ++ l.take(n)rot: [A](n: Int)List[A] => List[A]scala> rot(2)(List(1,2,3,4))res12: List[Int] = List(3, 4, 1, 2)----- Prelude> let rot n xs = drop n xs ++ take n xs
Prelude> rot 2 [1,2,3,4]
[3,4,1,2]
Wow.... I hate disqus soooo much.... Lets try again:
ReplyDeletescala> def rot[A](n: Int): List[A] => List[A] = l => l.drop(n) ++ l.take(n)rot: [A](n: Int)List[A] => List[A]scala> rot(2)(List(1,2,3,4))res12: List[Int] = List(3, 4, 1, 2)
Prelude> let rot n xs = drop n xs ++ take n xsPrelude> rot 2 [1,2,3,4][3,4,1,2]
Damn, I wish I can understand all of that... I find mine easier to read though, but I guess it's simply a matter of knowing the language. *Sigh* so many computers, so many languages... so little time.
ReplyDeletescala> def rot[A](n: Int): List[A] => List[A] = l => l.drop(n) ++ l.take(n)
ReplyDeleterot: [A](n: Int)List[A] => List[A]
scala> rot(2)(List(1,2,3,4))
res12: List[Int] = List(3, 4, 1, 2)
And the Haskell:let rot n xs = drop n xs ++ take n xs
rot 2 [1,2,3,4]
[3,4,1,2]
This is hilarious :) Maybe it was written in Scala... *duck*
ReplyDeleteYeah, that will work.
ReplyDeleteBut I think the point of the post was more, how I like it when you re-use already available operations, like zip, in conjunction with something as simple as rotating a list (which is basically what the (i+1) % length does) to solve something which we've all probably solved 100's of times before.
Using zip/rot feels more like putting pieces of Lego together in a new way and getting a cool new result, than writing a specific piece of code to solve a very specific problem, is all I'm saying :)
I fully agree... reuse reuse.
ReplyDelete