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.
The yield 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 yield
(syntax-rules (<-)
;; base case
[(yield expression ([x <- mx]))
(concat-map mx (lambda (x)
(list expression)))]
;; recursive case
[(yield expression ([x <- mx] [y <- my] ...))
(concat-map mx (lambda (x)
(yield expression ([y <- my] ...))))]
;; base case with predicate
[(yield expression ([x <- mx]) predicate)
(concat-map mx (lambda (x)
(if predicate
(list expression)
empty)))]
;; recursive case with predicate
[(yield expression ([x <- mx] [y <- my] ...) predicate)
(concat-map mx (lambda (x)
(yield expression ([y <- my] ...) predicate)))]))
;; === monad ===
(define empty '())
(define concat
(lambda (xs)
(fold-right append '() xs)))
(define concat-map
(lambda (xs f)
(concat (map f xs))))
;; === example ===
(define binary '("0" "1"))
(define count-to-fifteen
(yield (string-append bit-4 bit-3 bit-2 bit-1)
([bit-4 <- binary]
[bit-3 <- binary]
[bit-2 <- binary]
[bit-1 <- binary])))
;; - evaluates ->
'("0000" "0001" "0010" "0011"
"0100" "0101" "0110" "0111"
"1000" "1001" "1010" "1011"
"1100" "1101" "1110" "1111")