Best In Class - The Blog

My thoughts on FP, Business, Sales and more. Thanks for reading along.

For reasons that I must have mentioned either in tweets or in some old blogposts, I love Clojure. But I’m also very fond of both Haskell and J so Im going to go through some solutions for trivial problems in all three languages simultaneously.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Clojure

In Clojure this problem can be expressed very much like you how you would mentally approach the task:

(->> (range 1000)
     (filter #(or (zero? (mod % 3)) 
                  (zero? (mod % 5))))
     (reduce +))

Haskell

Haskell has great syntax for building lists with filters:

Prelude> [x | x <- [1..5]] -- No filter
[1,2,3,4,5]
    
Prelude> [x | x <- [1..5], x >= 2] -- Single filter
[2,3,4,5]

So bearing that in mind, the Haskell solution also reads like plain english:

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

X is populated with a list of numbers in the range 1…999, these are filtered using two predicates.

J

Since our final contestant isn’t a functional language but an array language, its solution looks a bit different. For me, J is mostly for fun so a lot of the time I’ll write something that works and then proceed to rewrite it 50 times. Here’s one such example:

+/(((0=3|/1+i.1000-1) +. (0=5|/1+i.1000-1)) * (1+i.1000-1))

At first glance its pretty obvious that the first two chunks build the list of numbers that are divisible by either 3 or 5 and these are then fed to the final list of numbers. The reason for the multiplication (instead of sum) becomes obvious once you understand how the lists are built:

0=3|/1+i.10

This is read as:

0=

Zero is matched against the elements on the righthand side, returning true/false.

3|/ 

The | means residue/modulo and / is insertion, meaning | is inserted between the elements of the following list, so in Clojure terms (reduce #(= mod % #) …).

1+i.10

This is simply a list of 10 integers starting a 1.

Since we’re testing with 0= this will return either true or false:

   0=3|/1+i.10
0 0 1 0 0 1 0 0 1 0

Since a hit does not give us the value but only a 1, we need to multiply these ones by their index in i.1000. The solution could more succintly be written as:

+/(*(3|])+.&(0=[)5|])1+i.1000-1

The new operators used are [ and ] which basically mean “rightside argument” and “leftside argument” somewhat like % in Clojure. In addition you need to know that +. means OR and that & is simply used to compose two operations. The result of this combination is multiplied (the first *) with the list on the righthand side. What that does is that it enables us to call sum +/ on the resulting list. It doesn’t exactly read like plain english and in a trivial example like this, simply redeffing some names in Clojure makes them almost equal in length:

clojure: (r +(f #(or(z?(m % 3))(z?(m % 5)))(rn 1000)))
j:         +/ (*(3|]) +. &(0=[)5|]) 1+ i.1000 - 1

Problem 2

I completely lost my motivation for coding Haskell/J solutions for this problem, after reading this comment in the forum:

I estimate that I had written about 3 million lines
 of assembler code in my whole life. Now, code only
 when strictly necessary.

Phi (golden ratio) is the approximate ratio between
 two consecutive terms in a Fibonacci sequence.
The ratio between consecutive even terms approaches
 phi^3 (4.236068) because each 3rd term is even.
Use a calculator and round the results to the nearest
 integer when calculating the next terms:

 2,8,34,.. multiplying by 4.236068 each time: 144,610,
 2584,10946,46368,196418 & 832040

The sum is 1089154

My codeless regards,
Rudy.

Rosetta Code - Caesar Cipher

So, instead of the math heavy Euler problems lets try our hand with the Caesar Cipher

The key is an integer from 1 to 25. This cipher rotates the letters of the alphabet (A to Z). The encryption replaces each letter with the 1st to 25th next letter in the alphabet (wrapping Z to A). So key 2 encrypts “HI” to “JK”, but key 20 encrypts “HI” to “BC”.

Clojure

There are many ways to approach this simple problem, but think about the alphabet as an infinite stream of repeating characters. If thats the case then all we need to do is jump 26 characters into that stream and then we can freely move back and forth in the stream to de/encrypt. A stream like that is easily constructed in Clojure:

(def characters (map char (cycle (range 65 91))))

Using the lookup fn nth we can write a succint translate function:

 (defn translate
  ([offset s] (translate offset s 1))
  ([offset s modifier]
     (let [chars (map char (cycle (range 65 91)))
           offset (+ offset 26)
           s      (upper-case s)]
       (->> (remove #(= % \space) s)
            (map #(nth chars (+ (* offset modifier) (int %))))
            (apply str)))))


user> (translate 2 "The five boxing wizards jump quickly")
"IWTUXKTQDMXCVLXOPGSHYJBEFJXRZAN"
user> (translate 2 *1 -1)
"THEFIVEBOXINGWIZARDSJUMPQUICKLY"
user> (translate 22 "The five boxing wizards jump quickly")
"CQNORENKXGRWPFRIJAMBSDVYZDRLTUH"
user> (translate 22 *1 -1)
"THEFIVEBOXINGWIZARDSJUMPQUICKLY"

Haskell

The Haskell solution on Rosetta approaches the problem from a slightly different angle:

import Data.Char (ord, chr)
import Data.Ix (inRange)
 
caesar :: Int -> String -> String
caesar k = map f
  where
    f c
      | inRange ('a','z') c = tr 'a' k c
      | inRange ('A','Z') c = tr 'A' k c
      | otherwise = c
 
unCaesar :: Int -> String -> String
unCaesar k = caesar (-k)
 
-- char addition                                                                     
tr :: Char -> Int -> Char -> Char
tr base offset char = chr $ ord base + (ord char - ord base + offset) `mod` 26

It does pretty much what it says on the tin. Here’s a quick breakdown:

caesar :: Int -> String -> String

There are several ways to declare functions in Haskell and this one simply says that caesar is a function which takes an Int and a String and returns a String. In typical functional tradition we then map a function across out collection of characters:

      | inRange ('a','z') c = tr 'a' k c
      | inRange ('A','Z') c = tr 'A' k c
      | otherwise = c

This simply says that if the current item is a lowercase letter than translate it as such, ditto for upper case and for anything else (ie. space) then just return the unaltered version. This would look almost the same in Clojure.

Finally, we have the actual translation:

tr base offset char = chr $ ord base + 
                      (ord char - ord base + offset) `mod` 26

This is much like the Clojure version, except instead of constructing an infinite sequence the index is wrapped using modulo. The use of $ simply combines chr and ord much like & does in J and ord/chr equals int/char in the Clojure version.

J

A task such as this is one of the many examples where J really shines - Here goes:

cndx=: [: , 65 97 +/ 26 | (i.26)&+
caesar=: (cndx 0)}&a.@u:@cndx@[ {~ a.i.]

First, cndx is defined using the [: cap operator. The cap op lets us train several operations together following the rules outlined here. But since J evaluates from the right, we have to start there.

The rightmost operator is + which means “add to the argument”. In the definition of caesar we see that cndx is called with a single argument, a number, so in this case we’re adding to that number. The item we’re adding is (i.26), meaning a list of integers from 1 - 26. Now we can separate this part out and into the REPL:

   ((i.26)&+) 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
   ((i.26)&+) 10
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
 

As you can see, it simply displaces the offset. The next part adds the modulo operator for the wrapping:

   26 | ((i.26)&+) 10
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 1 2 3 4 5 6 7 8 9

In the next phase we come across one of the really cool features of an array-language, that we can add 2 integers to the entire rightside argument:

   65 97 +/ 26 | ((i.26)&+) 10
 75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90 65 66 67  68  69  70  71  72  73  74
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 97 98 99 100 101 102 103 104 105 106

Its difficult to see when we’re not in the REPL, but the above is actually 2 lists of the length 26 characters each. We can read the dimension using the $ operator:

   $ 65 97 +/ 26 | ((i.26)&+) 10
2 26

Now we have a sequence of upper+/lower-case letters and all we need to do is explain the first two components: [: ,

The [: can be viewed as syntactic sugar as it simply allows to to compose a more concise statement with less parens. The comma has a significant effect in that it flattens (ravels) the list into a single dimension list:

   , 65 97 +/ 26 | ((i.26)&+) 10
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 65 66 67 68 69 70 71 72 73 74 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 97 98 99 100 101 102 103 104 105 106
   $ , 65 97 +/ 26 | ((i.26)&+) 10
52

When starting to read tacit statements like cndx, I was recommended by J expert Tracy Harms to always start from the righthand side and to look for fork patterns. The pattern in cndx is:

cndxAlt=: vL3 vM3 (vL2 vM2 (vL1 vM1 vR1))

Here you see 3 forks with 3 components each (no other way) and broken down they’re:

 vL3=: [:
   vM3=: ,
   vL2=: 65 97"_
   vM2=: +/
   vL1=: 26"_
   vM1=: |
   vR1=: (i.26)&+

The [: prefix allows us to avoid the parens and the “_ are a different story.

I’ve walked you through the first part of the J solution pretty much like Tracy Harms walked me through it, but its beyond the scope of this evening to walk through caesar. If it turns out that more people than Tracy and I appreciate J, I’ll be happy to do it :)