Category Archives: Lisp

Ibid.

During my interview with Gene Kim on for Functional Geekery, Episode 128, Gene talked about how he had a problem he was asking different people for how they would solve it nicely with a functional approach, to see how to improve his Clojure solution to be more idiomatic.

His problem was on “rewriting” Ibid. entries in citation references, to get the authors names instead of the Ibid. value, as Ibid. is a shorthand that stands for “the authors listed in the entry before this”.

As he was describing this problem, I was picturing the general pseudo-code with a pattern match in my head. To be fair, this has come from a number of years of getting used to thinking in a functional style as well as thinking in a pattern matching style.

The following Erlang code is a close representation to the pseudo-code that was in my head.

-module(ibid).

-export([ibid/1]).

ibid(Authors) ->
    ibid(Authors, []).

ibid([], UpdatedAuthors) ->
    {ok, lists:reverse(UpdatedAuthors)};
ibid(["Ibid." | _], []) ->
    {error, "No Previous Author for 'Ibid.' citation"};
ibid(["Ibid." | T], UpdatedAuthors=[H | _]) ->
    ibid(T, [H | UpdatedAuthors]);
ibid([H | T], UpdatedAuthors) ->
    ibid(T, [H | UpdatedAuthors]).

Running this in the Erlang shell using erl results in the following

> ibid:ibid(["Mike Nygard", "Gene Kim", "Ibid.", "Ibid.", "Nicole Forsgren", "Ibid.", "Jez Humble", "Gene Kim", "Ibid."]).
{ok,["Mike Nygard","Gene Kim","Gene Kim","Gene Kim",
     "Nicole Forsgren","Nicole Forsgren","Jez Humble","Gene Kim",
     "Gene Kim"]}
> ibid:ibid(["Ibid."]).
{error,"No Previous Author for 'Ibid.' citation"}

Throughout the editing of the podcast, I continued to think about his problem, and how I would approach it in Clojure without built-in pattern matching, and came up with the following using a cond instead of a pure pattern matching solution:

(defn
  update_ibids
  ([authors] (update_ibids authors []))
  ([[citation_author & rest_authors :as original_authors] [last_author & _ :as new_authors]]
    (let [ibid? (fn [author] (= "Ibid." author))]
      (cond
        (empty? original_authors) (reverse new_authors)
        (and (ibid? citation_author) (not last_author))
          (throw (Exception. "Found `Ibid.` with no previous author"))
        :else (recur
          rest_authors
          (cons
            (if (ibid? citation_author)
                last_author
                citation_author)
            new_authors))))))

And if we run this in the Clojure REPL we get the following:

user=> (def references ["Gene Kim", "Jez Humble", "Ibid.", "Gene Kim", "Ibid.", "Ibid.", "Nicole Forsgren", "Micheal Nygard", "Ibid."])

user=> (update_ibids [])
()
user=> (update_ibids ["Ibid."])
Execution error at user/update-ibids (REPL:8).
Found `Ibid.` with no previous author
user=> (update_ibids references)
("Gene Kim" "Jez Humble" "Jez Humble" "Gene Kim" "Gene Kim" "Gene Kim" "Nicole Forsgren" "Micheal Nygard" "Micheal Nygard")

That solution didn’t sit well with me (and if there is a more idiomatic way to write it I would love some of your solutions as well), and because of that, I wanted to see what could be done using the core.match library, which moves towards the psuedo-code I was picturing.

(ns ibid
  (:require [clojure.core.match :refer [match]]))


(defn
  update_ibids
  ([authors] (update_ibids authors []))
  ([orig updated]
    (match [orig updated]
      [[] new_authors] (reverse new_authors)
      [["Ibid." & _] []] (throw (Exception. "Found `Ibid.` with no previous author"))
      [["Ibid." & r] ([last_author & _] :seq) :as new_authors] (recur r (cons last_author new_authors))
      [[author & r] new_authors] (recur r (cons author new_authors)) )))

And if you are trying this yourself, don’t forget to add to your deps.edn file:

{:deps
  {org.clojure/core.match {:mvn/version "0.3.0"}}

After the first couple of itches were scratched, Gene shared on Twitter Stephen Mcgill’s solution and his solution inspired by Stephen’s.

https://twitter.com/RealGeneKim/status/1201922587346866176

(Edit 2022-05-02 : I took out the Twitter embed and changed the embed to be an HTML link to Twitter if you are interested in seeing the post as it was pointed out that tracking cookies were being dropped by Twitter, in an effort to reduce cookies being dropped by this site.)

And then, just for fun (or “just for defun” if you prefer the pun intended version), I did a version in LFE (Lisp Flavored Erlang) due to it being a Lisp with built in pattern matching from being on the Erlang runtime.

(defmodule ibid
  (export (ibid 1)))


(defun ibid [authors]
  (ibid authors '[]))


(defun ibid
  ([[] updated]
    (tuple 'ok (: lists reverse updated)))
  (((cons "Ibid." _) '[])
    (tuple 'error "No Previous Author for 'Ibid.' citation"))
  ([(cons "Ibid." authors) (= (cons h _) updated)]
    (ibid authors (cons h updated)))
  ([(cons h rest) updated]
    (ibid rest (cons h updated))))

Which if we call it in LFE’s REPL gives us the following:

lfe> (: ibid ibid '["Mike Nygard" "Gene Kim" "Ibid." "Ibid." "Nicole Forsgren" "Ibid." "Jez Humble" "Gene Kim" "Ibid."])
#(ok
  ("Mike Nygard"
   "Gene Kim"
   "Gene Kim"
   "Gene Kim"
   "Nicole Forsgren"
   "Nicole Forsgren"
   "Jez Humble"
   "Gene Kim"
   "Gene Kim"))
lfe> (: ibid ibid '["Ibid."])
#(error "No Previous Author for 'Ibid.' citation")

If you have different solutions shoot them my way as I would love to see them, and if there looks to be interest, and some responses, I can create a catalog of different solutions similar to what Eric Normand does on his weekly challenges with his PurelyFunctional.tv Newsletter.

Functional Geekery

In a previous post I mentioned I had a new project in the works. I was a guest on the Ruby Rogues podcast and made an announcement there, but for those who didn’t catch that episode, I am now announcing Functional Geekery, a podcast about functional programming.

After some issues with getting the hosting setup properly, and working with the hosting provider’s support for a couple of issues, the first episode is ready to go live! I will be working on getting it in the iTunes store, and some of the other podcasting services, but in the meantime, you can find it online.

I am hoping to have a wide range of guests and topics, from Clojure, to Erlang, to JavaScript, to F#, as well as Scala, Haskell, and functional programming in languages like C# and Ruby. If you have any suggestions on shows, topics, or guests, check out the About Page on the site to submit ideas.

–Proctor

Clojure function has-factors-in?

Just another quick post this evening to share a new function I created as part of cleaning up my solution to Problem 1 of Project Euler.

Was just responding to a comment on Google+ on my update sharing the post Project Euler in Clojure – Problem 16, and I saw the commenter had his own solution to problem 1. In sharing my solution I realized that I could clean up my results even further, and added a function has-factors-in?. These updates have also been pushed to my Project Euler in Clojure Github repository for those interested.

(defn has-factors-in? [n coll]
  (some #(factor-of? % n) coll))

Where before I had:

(defn problem1
  ([] (problem1 1000))
  ([n] (sum (filter #(or (factor-of? 3 %) (factor-of? 5 %))) (range n))))

It now becomes:

(defn problem1
  ([] (problem1 1000))
  ([n] (sum (filter #(has-factors-in? % [3 5]) (range n)))))

This change makes my solution read even more like the problem statement given.

Your thoughts?

–Proctor

Project Euler in Clojure – Problem 16

Here is my solution to Problem 16 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 16 of Project Euler is:

What is the sum of the digits of the number 2^1000

This problem was straight forward since I already had the function digits-of defined from problem8. I was able to be very declarative in my problem, so much so, that it reads as the problem statement you are asked to solve.

(defn problem16
  ([] (problem16 1000))
  ([n] (sum (digits-of (expt 2 n)))))

As always, any feedback you have for me is greatly appreciated.

–Proctor

Project Euler in Clojure – Problem 15

Here is my solution to Problem 15 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 15 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:

Starting in the top left corner of a 22 grid,
there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

I started this problem, by trying to tracing and counting the routes through grids of 2×2, 3×3, and 4×4, and even setled in and did a 5×5 square. Having these numbers, and knowing I had two choices for ever position I was in, except for when the path got to the far edge and bottom, I had a hint at the growth rate of the problem. I tried some powers of 2 with the relationship of the numbers, and some factorials with the numbers. After seeing some possible relationships with the factorials that might be leading me in the right direction, I tried a number of permutation calculations, and the combination calculations. Having seen the numbers show up in different combination results, I then spent time back-calculating from those numbers into my ns, and found that the pattern seemed to match 2n Choose n.

The source code to this was the factorial function:

(defn factorial [n]
  (multiply (range 1M (inc (bigdec n)))))

And, I could have done it recursively, but I figured I would just operate against the sequence of numbers, especially now that the reducers are available in the Clojure 1.5-Alpha 3 release (at the time of this writing) of Clojure. After I get through a few more problems (of which I am working ahead of these posts), I am thinking it would be interesting to run the same Project Euler Problems against 1.4 and 1.5 using the reducers library, just substituting map/reduce for the reduce/combine functionality, and seeing how much effort it takes to move them over, as well as the differences in the timings of the different problems.

The other base function I needed was a combination function:

(defn combination [n k]
  (cond (zero? n) 0
        (zero? k) 1
        :else (/ (factorial n) (* (factorial (- n k)) (factorial k)))))

This function just does the basic calculation for combinations, from the formula:

\frac{n!}{\big((n-k)! * k!\big)}

With that, and my stumbling upon the matching of the fact that {2n}\choose{n} is the solution to the number of paths through the square the function problem15 is defined as:

(defn problem15
  ([] (problem15 20))
  ([n] (combination (+ n n) n)))

As always, any feedback you have for me is greatly appreciated.

–Proctor

Aspect Oriented Timing in C# with Castle Windsor

I was making some refurbishments on some reporting code in our application that used EF and was suffering from the Select N+1 problem. If truth, it was much worse, as it was an Select N+1 problem up to 6 levels deep depending on where the report was run from.

I was changing the code to use a denormalized view from the database, and then run a SQL Query using Entity Framework. When doing this I was asked to get the timings of the report, both against the new way, and the existing way.

As this is incidental to what I was really trying to do, I did not want to litter timing code, and logging mechanisms into classes that already existed. This smelled of Aspect Oriented Programming (AOP). While I had not done anything using AOP before, I knew that it was great for cross-cutting concerns like logging, timings, etc. Having been digging into Clojure and LISP recently, this also seemed like cases of the :before, :after and :around methods in Common LISP, or the similar behavior in Eiffel as pointed out in Bertrand Meyer’s Object Oriented Software Construction, not to mention the time function in Clojure which is a function whose single concern is simply the to manage capturing the timing a function passed into it. My hope was to simplify, or un-complect, the code, and keep those concerns separate.

In our project, we have Castle Windsor setup as the IOC container, and Windsor supports a type of Aspect Oriented Programming using something called Interceptors. I found documentation on setting it up on a post by Ayende, and one Andre Loker. The issue was some of the places I wanted to setup the capturing of the timings were in different areas than where the handlers were registered for Windsor.

After some hunting around, I managed to come up with being able to add an interceptor to an already registered component by using the following line of code, where the IReportingService is the class I want to time the method calls around, and the LogTimingInterceptor is the class that captures the timing of the method call and sends it to the logger:

container.Kernel.GetHandler(typeof(IReportingService)).ComponentModel.Interceptors.Add(new InterceptorReference(typeof(LogTimingInterceptor)));

Hope someone else can find this useful,
–Proctor

John Backus on the Assignment Statement

The assignment statement is the von Neumann bottle-neck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does.

John Backus, 1977
ACM Turing Award Lecture,
Communications of the ACM
August 1978, Volume 2, Number 8

Project Euler in Clojure – Problem 14

Here is my solution to Problem 14 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 14 of Project Euler is to find the starting number with the longest Collatz sequence, summarized from the problem page as:

The following iterative sequence is defined for the set of positive integers:
n -> n/2 (n is even)
n -> 3n + 1 (n is odd)
[...]
Which starting number, under one million, produces the longest chain?

The first function I needed was a function to get the next number in the Collatz sequence.

(defn next-collatz [n]
  (cond (<= n 1) nil
   	(even? n) (/ n 2)
        (odd? n) (+ (* 3 n) 1)))

This function mimics the above definition of the sequence, with the distinction of the check to see if the number is less than, or equal to, 1. While not strictly necessary, when I was generating numbers from the REPL, I noticed that the sequence never really terminates, but ends in a repeating sequence of 4 -> 2 -> 1 -> 4 -> 2 -> 1 ->.... This can be seen by running the following at the REPL.

(take 15 (iterate next-collatz 8))

Wich results in the sequence (8 4 2 1 4 2 1 4 2 1 4 2 1 4 2). I used the condition (<= n 1) as a guard condition to as a way to be able to terminate the sequence and make it finite. This could probably be removed at this point, as I did not even use the nil return as a check, except that it would serve as a reminder of the function when playing at the REPL.

The next function I defined was a function to get the count of the numbers in the sequence. I defined it this way in the hopes of trying to memoize the values, but I kept getting an OutOfMemoryException when I tried to use it so I took the memoization away.

(defn collatz-count-for [n]
  {:pre  [(pos? n)]}
  (if (= n 1) 1
      (inc (collatz-count-for (next-collatz n)))))

In this function, I decided I would add a precondition to the function requiring that the parameter to the function be positive. This way I could avoid having to try and generate a Collatz sequence for negative numbers, as they are outside the scope of this problem. The function first checks if the number to generate the sequence for is 1, and if so, the count of the sequence returns 1. For all other positive numbers, we get the length of the sequence for the next Collatz number in the sequence, and increment that value, and return that as the Collatz count.

As I was writing this up, I decided I would take another stab at this, and did some searching to try and find a way to change the memory allocation for the project in the REPL. I found the following post How to Set JVM Memory for Clojure REPL in Emacs, and added the following to my project.clj file.

:jvm-opts ["-Xmx768M"]

When I ran with the following memoized version of the collatz-count-for, it now runs much quicker than it did before. Previously it was a rough mental counting of about 10-15 seconds, and now the first time is runs was 2-3 seconds, and sub second on runs after that even.

(def collatz-count-for (memoize 
  (fn [n]
    {:pre [(pos? n)]}
    (if (= n 1) 1
      (inc (collatz-count-for (next-collatz n)))))))

The changes needed to memoize the function collatz-count-for is that the defn is now a def, which assigns the identifier of collatz-count-for to the result of passing a now nameless function, with the previous function body, to the function memoize. This allows the function body to remain the same, and only the declaration of the function has to now change.

With those pieces to the problem in place, we can now find the number that generates the longest Collatz sequence.

(defn problem14
  ([] (problem14 1000000))
  ([n] (first (reduce
                (fn [memo x]
                  (if (> (second x) (second memo)) x memo))
                (map #(vector % (collatz-count-for %)) (range 1 (inc n)))))))

I started by mapping over the numbers from 1 to 1000000, to create vectors representing the pair of the number and the sequence length for that number. An example of which results in the following sequence (shown to the first 10 numbers):

([1 1] [2 2] [3 8] [4 3] [5 6] [6 9] [7 17] [8 4] [9 20] [10 7] ...)

I then feed that sequence into reduce, with a function to find the pair with the largest sequence length by calling second on the vector, resulting in the pair of number and sequence length with the largest sequence length. And having found that vector, I use first to find what the number with the largest sequence length is.

This seems like it might be generic enough (idiomatic pattern) that I was missing something that was already defined to do the map and reduce on a structure like this, but I could not find anything. If anybody knows of anything I would love to see how that might be made more expressive.

–Proctor

Project Euler in Clojure – Problem 13

Here is my solution to Problem 13 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 13 of Project Euler is described as:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
[...]

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:


(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))

(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))
(defn problem13 []
  (let [numbers [37107287533902102798797998220837590246510135740250
                46376937677490009712648124896970078050417018260538
                74324986199524741059474233309513058123726617309629
                91942213363574161572522430563301811072406154908250
                23067588207539346171171980310421047513778063246676
                89261670696623633820136378418383684178734361726757
                28112879812849979408065481931592621691275889832738
                44274228917432520321923589422876796487670272189318
                47451445736001306439091167216856844588711603153276
                70386486105843025439939619828917593665686757934951
                62176457141856560629502157223196586755079324193331
                64906352462741904929101432445813822663347944758178
                92575867718337217661963751590579239728245598838407
                58203565325359399008402633568948830189458628227828
                80181199384826282014278194139940567587151170094390
                35398664372827112653829987240784473053190104293586
                86515506006295864861532075273371959191420517255829
                71693888707715466499115593487603532921714970056938
                54370070576826684624621495650076471787294438377604
                53282654108756828443191190634694037855217779295145
                36123272525000296071075082563815656710885258350721
                45876576172410976447339110607218265236877223636045
                17423706905851860660448207621209813287860733969412
                81142660418086830619328460811191061556940512689692
                51934325451728388641918047049293215058642563049483
                62467221648435076201727918039944693004732956340691
                15732444386908125794514089057706229429197107928209
                55037687525678773091862540744969844508330393682126
                18336384825330154686196124348767681297534375946515
                80386287592878490201521685554828717201219257766954
                78182833757993103614740356856449095527097864797581
                16726320100436897842553539920931837441497806860984
                48403098129077791799088218795327364475675590848030
                87086987551392711854517078544161852424320693150332
                59959406895756536782107074926966537676326235447210
                69793950679652694742597709739166693763042633987085
                41052684708299085211399427365734116182760315001271
                65378607361501080857009149939512557028198746004375
                35829035317434717326932123578154982629742552737307
                94953759765105305946966067683156574377167401875275
                88902802571733229619176668713819931811048770190271
                25267680276078003013678680992525463401061632866526
                36270218540497705585629946580636237993140746255962
                24074486908231174977792365466257246923322810917141
                91430288197103288597806669760892938638285025333403
                34413065578016127815921815005561868836468420090470
                23053081172816430487623791969842487255036638784583
                11487696932154902810424020138335124462181441773470
                63783299490636259666498587618221225225512486764533
                67720186971698544312419572409913959008952310058822
                95548255300263520781532296796249481641953868218774
                76085327132285723110424803456124867697064507995236
                37774242535411291684276865538926205024910326572967
                23701913275725675285653248258265463092207058596522
                29798860272258331913126375147341994889534765745501
                18495701454879288984856827726077713721403798879715
                38298203783031473527721580348144513491373226651381
                34829543829199918180278916522431027392251122869539
                40957953066405232632538044100059654939159879593635
                29746152185502371307642255121183693803580388584903
                41698116222072977186158236678424689157993532961922
                62467957194401269043877107275048102390895523597457
                23189706772547915061505504953922979530901129967519
                86188088225875314529584099251203829009407770775672
                11306739708304724483816533873502340845647058077308
                82959174767140363198008187129011875491310547126581
                97623331044818386269515456334926366572897563400500
                42846280183517070527831839425882145521227251250327
                55121603546981200581762165212827652751691296897789
                32238195734329339946437501907836945765883352399886
                75506164965184775180738168837861091527357929701337
                62177842752192623401942399639168044983993173312731
                32924185707147349566916674687634660915035914677504
                99518671430235219628894890102423325116913619626622
                73267460800591547471830798392868535206946944540724
                76841822524674417161514036427982273348055556214818
                97142617910342598647204516893989422179826088076852
                87783646182799346313767754307809363333018982642090
                10848802521674670883215120185883543223812876952786
                71329612474782464538636993009049310363619763878039
                62184073572399794223406235393808339651327408011116
                66627891981488087797941876876144230030984490851411
                60661826293682836764744779239180335110989069790714
                85786944089552990653640447425576083659976645795096
                66024396409905389607120198219976047599490197230297
                64913982680032973156037120041377903785566085089252
                16730939319872750275468906903707539413042652315011
                94809377245048795150954100921645863754710598436791
                78639167021187492431995700641917969777599028300699
                15368713711936614952811305876380278410754449733078
                40789923115535562561142322423255033685442488917353
                44889911501440648020369068063960672322193204149535
                41503128880339536053299340368006977710650566631954
                81234880673210146739058568557934581403627822703280
                82616570773948327592232845941706525094512325230608
                22918802058777319719839450180888072429661980811197
                77158542502016545090413245809786882778948721859617
                72107838435069186155435662884062257473692284509516
                20849603980134001723930671666823555245252804609722
                53503534226472524250874054075591789781264330331690]]
    (bigint (reduce str "" (take 10 (digits-of (sum numbers)))))))

Problem 13 was pretty straight-forward, as the problem, I took the list of the one-hundred numbers as a vector, and then called the function sum which has been used in a number of previous problems as well as the digits-of function which was created in my solution to Problem 8. With these two functions, to get the first 10 digits of the sum was to just call take on the result of calling digits-of on the sum of the numbers in the vector numbers.

The rest of the function is to make the output to the REPL nice. I take the individual digits and turn them into a string using reduce str "", and then call the function bigint to cast it to an integer value.

**Update**
I have posted my solution to Problem 14.
–Proctor