Racket - gregorymorrison/euler1 GitHub Wiki
Racket, introduced in 1994, is a variant of Scheme, which itself is a minimal version of lisp. Racket is a Functional language, in which the basic language construct is the list, and the basic computational operation is the function. It uses a completely different computational model than the standard Von Neumann model used by imperative and object-oriented languages, in which you write your program as a list of discrete steps for the machine to follow. Instead, functional languages use Church‘s Lambda calculus, in which programs are constructed as a collection of functions which are applied to other things (primitives and other functions) to produce results.
The lambda calculus allows you to perform any computation using only three functions - map, filter, and fold. It takes only these three operations to make a language Turing-Complete. Now, the fact that a language has only three operations means that it takes very little time to understand, but it's also a red flag for being overly low-level (see Turing Tarpit). The imperative language Brainfuck is considered unusable despite having a relative abundance of eight instructions.
However, there is an important difference. You see, the lambda calculus operations are higher-order functions, which mean that they take in functions as input and return functions as output. Imperative languages like Brainfuck build programs from the bottom up - one Brainfuck operation can only increment a pointer or output a byte. Functional languages like Racket build up from the top down - one Racket instruction can literally do anything, including redefining the language itself. This simplicity-plus-power is part of what gives functional languages their appeal.
A fourth function, lambda, is also included, which allows for creation of anonymous functions. In the early days of lisp it was needed for the creation of local variables; it's mainly syntactic sugar now.
Scheme is largely an academic language, with the goal of minimalism for pedagogical illustration. Racket is a "batteries included" version of Scheme, including an IDE, GUI tools, web server, package manager, etc., Still, it doesn't veer too far ideologically from its older brother, and omits many of the base functional operations you'd expect to find in a language, such as a range function, list slice, and bizarrely even map, filter, and fold. Scheme expects you to roll your own. Um, okay, let's write our own library with functions we'll use later. The last function, mod-3-5, is specific to our problem, Euler1:
#lang racket
(provide map)
(define (map f lst)
(if (empty? lst)
empty
(cons (f (first lst)) (map f (rest lst)))))
(provide filter)
(define (filter pred lst)
(if (empty? lst)
empty
(if (pred (first lst))
(cons (first lst) (filter pred (rest lst)))
(filter pred (rest lst)))))
(provide fold)
(define (fold f accum lst)
(if (empty? lst)
accum
(fold f (f accum (first lst)) (rest lst))))
(provide range)
(define (range low high)
(cond
((> low high) empty)
(else (cons low (range (+ low 1) high)))))
(provide slice)
(define (slice lst start end)
(drop (take lst end) start))
(provide mod-3-5)
(define (mod-3-5 n)
(if (or (= (modulo n 3) 0) (= (modulo n 5) 0)) #t #f))
Now, let's get to work. Here's our first example of Euler1. It's a straight application of map, then filter, then fold. Map here is admittedly stupid - it takes a number and returns itself; it's included only for illustration:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (euler1 x)
(fold+ 0
(filtermod-3-5
(map (lambda (x) x)
(range 0 x)))))
(printf "~a\n" (euler1 999))
Notice that we are not maintaining any state to solve our problem. No loops, no variables, no mutable state. We simply call map, filter, and fold, and get the solution. This is an important part of the solution of the concurrency problem - how do you keep threads from stepping on each other's states? By eliminating mutable state!
Here’s a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic – it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation – there are instead only functions which return values. The other main point is that this recursion uses tail call optimization – it’s written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (euler n acc)
(if (= n 0)
acc
(if (mod-3-5 n)
(euler (- n 1) (+ acc n))
(euler (- n 1) acc))))
(define (euler1 x)
(euler x 0))
(printf "~a\n" (euler1 999))
Although Racket is a functional language, and that last version is idiomatic of functional languages like Standard ML – no mutability, it’s not really idiomatic of Lisp. Lisp is all about lists. Here’s a more idiomatic version in which we pass around a list generated up front, peeling off and using the first value in each recursive call:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (mod-3-5-n n)
(if (mod-3-5 n) n 0))
(define (euler lst acc)
(if (not (empty? lst))
(euler (rest lst) (+ acc (mod-3-5-n (first lst))))
acc))
(define (euler1 n)
(euler (range 0 n) 0))
(printf "~a\n" (euler1 999))
Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler1() returns euler1() calculated on the half of the list before the pivot element, euler1() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (mod-3-5-n n)
(if (mod-3-5 n) n 0))
(define (euler lst)
(if (not (empty? lst))
; find the midpoint of the list
(let ((pivot (ceiling (/ (length lst) 2))))
(+
; return a value for the middle element
(mod-3-5-n (list-ref lst (- pivot 1)))
; plus euler on the first half of the list
(euler (slice lst 0 (- pivot 1)))
; plus euler on the last half of the list
(euler (slice lst pivot (length lst)))))
0 ; else return 0
)
)
(define (euler1 n)
(euler (range 0 n)))
(printf "~a\n" (euler1 999))
Here’s a version in which I define my own map/filter/reduce functions using lambdas, and then simply apply them using Racket's built-in function composition. Map’s only purpose here obviously is for illustration, since it returns itself:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (myMap lst)
(map (lambda (x) x) lst))
(define (myFilter lst)
(filter mod-3-5 lst))
(define (myFold lst)
(fold + 0 lst))
(define (euler1 x)
((compose myFold myFilter myMap) (range 0 x)))
(printf "~a\n" (euler1 999))
One of Lisp’s greatest claims to fame is its regular syntax. It may appear illegible at first, but Lisp is not designed for human-readability – it’s designed for machine-readability. Unlike other languages where your code is written as a bunch of text, Lisp is written as collection of syntax symbols having a regular grammar. Lisp also has a precompilation stage called macros which generate and substitute code using user-defined routines, allowing you to extend the language arbitrarily. What does all this mean? Since I’m a macro novice myself, I’ll borrow some material from this StackOverflow answer. Let’s say you’re fond of the Python lisp comprehension syntax:
S = [x for x in range(1000) if x%3==0 or x%5==0]
Well, Racket doesn’t have anything like that, but don’t despair – Racket lets you roll your own! The macro stage takes source tokens as input, transforms it, and then returns syntax that replaces the original tokens. Here I've defined two different versions of lcomp - one that takes a filter and one that does not. I'm only using the second one but am including both to illustrate overloading of a macro definition by wildcard. I’ve colored the function parameters and arguments passed in for ease of illustration. Notice we do nothing with the tokens for, in, and conditional - they exist merely as part of our list comprehension’s grammar:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define-syntax lcomp
(syntax-rules ()
[(lcomp expression for var in mylist)
(for/list ([var mylist]) expression)]
[(lcomp expression for var in mylist conditional test)
(for/list ([var mylist] #:when test) expression)]))
(printf "~a\n"
(fold + 0
(lcomp x for x in (range 0 999) if (mod-3-5 x))))
It actually took me much longer than I'd like to admit to get this code to work. Basically, you're going to have to read the documentation and get friendly with the admittedly nice debugging IDE. Racket has a tool to let you step through the macro expansion, which produced the following result from my source (including Racket's highlighting):
(module euler1 racket
(#%module-begin
(require "util.rkt")
(define-syntax lcomp
(syntax-rules ()
[(lcomp expression for var in mylist) (for/list ([var mylist]) expression)]
[(lcomp expression for var in mylist conditional test)
(for/list ([var mylist]) #:when test) expression)]))
(printf
"~a\n"
(fold + 0 (for/list ([x (range 0 999)] #:when (mod-3-5 x)) x)))))
Finally, here’s an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation. Racket sucks at making long math expressions legible outside of an IDE, so I’ve attempted to clarify it with indentation:
#lang racket
;; Euler1 in Racket
(require "util.rkt")
(define (mySum n size)
(* n
(floor
(/
(+
(expt (floor (/ size n)) 2)
(floor (/ size n)))
2))))
(define (euler1 size)
(- (+ (mySum 3 size) (mySum 5 size)) (mySum 15 size)))
(printf "~a\n" (euler1 999))
To execute all this code, install Racket. There is no version for the yum package manager, so download and install from http://racket-lang.org/. Then, simply add racket to your path and execute:
$ racket euler1.rkt
233168
$