Haskell Kernels and Scheme
I learned recently about a concept in Haskell called a kernel. Haskell is comprised of a number of syntactic conveniences that can be translated into a base syntax — a modified version of the lambda calculus. Learning about these kernels has helped me write more useful macros in Scheme, a sparse language that is also based on the lambda calculus.
The for macro below is inspired by list comprehensions
in Haskell wherein every element of one list is applied to every
element of n number of lists if an optional predicate
is satisfied. Within the Haskell kernel, a list comprehension is
revealed to be syntactic sugar over a monadic instance. The monad,
in this case, is nondeterminism, where all possible data
combinations are expressed as a list.
;; === macro ===
(define-syntax for
(syntax-rules (<- when)
;; base case
[(_ ([x <- mx]) expression)
(concat-map mx (lambda (x)
(list expression)))]
;; recursive case
[(_ ([x <- mx] [y <- my] ...) expression)
(concat-map mx (lambda (x)
(for ([y <- my] ...) expression)))]
;; base case with predicate
[(_ ([x <- mx]) (when predicate) expression)
(concat-map mx (lambda (x)
(if predicate
(list expression)
empty)))]
;; recursive case with predicate
[(_ ([x <- mx] [y <- my] ...) (when predicate) expression)
(concat-map mx (lambda (x)
(for ([y <- my] ...) (when predicate) expression)))]))
;; === monad ===
(define empty '())
(define concat-map
(lambda (xs fn)
(if (null? xs)
empty
(append (fn (car xs)) (concat-map (cdr xs) fn)))))
;; === example ===
(define binary '(0 1))
(define count-to-fifteen
(for ([bit-4 <- binary]
[bit-3 <- binary]
[bit-2 <- binary]
[bit-1 <- binary])
(list bit-4 bit-3 bit-2 bit-1)))
;; - evaluates ->
'((0 0 0 0) (0 0 0 1) (0 0 1 0) (0 0 1 1)
(0 1 0 0) (0 1 0 1) (0 1 1 0) (0 1 1 1)
(1 0 0 0) (1 0 0 1) (1 0 1 0) (1 0 1 1)
(1 1 0 0) (1 1 0 1) (1 1 1 0) (1 1 1 1)))