The Comonad.Reader

I've been transcoding a lot of Haskell to Scheme lately and one of the things that I found myself needing was a macro for dealing with Currying of functions in a way that handles partial and over-application cleanly.

I found a very elegant macro by Piet Delport that handles partial application, but that doesn't deal with the partial application of no arguments or that I'd like to also be able to say things like the following and have the extra arguments be passed along to the result.

 
(define-curried (id x) x)
(id + 1 2 3) ;;=> 6
 

This of course, becomes more useful for more complicated definitions.

 
(define-curried (compose f g x) (f (g x)))
(define-curried (const a _) a)
 

While I could manually associate the parentheses to the left and nest lambdas everywhere, Haskell code is rife with these sorts of applications. In the spirit of Scheme, since I couldn't find a macro on the internet that did what I want, I tried my hand at rolling my own.

 
;; curried lambda
(define-syntax curried
  (syntax-rules ()
    ((_ () body)
     (lambda args
         (if (null? args)
             body
             (apply body args))))
    ((_ (arg) body)
      (letrec
        ((partial-application
          (lambda args
            (if (null? args)
                partial-application
                (let ((arg (car args))
                      (rest (cdr args)))
                  (if (null? rest)
                      body
                      (apply body rest)))))))
        partial-application))
    ((_ (arg args ...) body)
     (letrec
       ((partial-application
         (lambda all-args
           (if (null? all-args)
               partial-application
               (let ((arg (car all-args))
                     (rest (cdr all-args)))
                 (let ((next (curried (args ...) body)))
                   (if (null? rest)
                       next
                       (apply next rest))))))))
       partial-application))))
 
;; curried defines
(define-syntax define-curried
  (syntax-rules ()
    ((define-curried (name args ...) body)
       (define name (curried (args ...) body)))
    ((define-curried (name) body)
       (define name (curried () body)))
    ((define-curried name body)
       (define name body))))

While Scheme is not my usual programming language, I love the power of hygienic macros.

I welcome feedback.

[Edit: updated to change the base case for define-curried and added the if to the base case of curried to be more consistent with the other cases per the second comment below]

I was asked to give two talks at the Boston Area Haskell User Group for this past Tuesday. The first was pitched at a more introductory level and the second was to go deeper into what I have been using monoids for lately.

The first talk covers an introduction to the mathematical notion of a monoid, introduces some of the features of my Haskell monoids library on hackage, and starts to motivate the use of monoidal parallel/incremental parsing, and the modification use of compression algorithms to recycle monoidal results.

The second talk covers a way to generate a locally-context sensitive parallel/incremental parser by modifying Iteratees to enable them to drive a Parsec 3 lexer, and then wrapping that in a monoid based on error productions in the grammar before recycling these techniques at a higher level to deal with parsing seemingly stateful structures, such as Haskell layout.

1. Introduction To Monoids (PDF)
2. Iteratees, Parsec and Monoids: A Parsing Trifecta (PDF)

Due to a late start, I was unable to give the second talk. However, I did give a quick run through to a few die-hards who stayed late and came to the Cambridge Brewing Company afterwards. As I promised some people that I would post the slides after the talk, here they are.

The current plan is to possibly give the second talk in full at either the September or October Boston Haskell User Group sessions, depending on scheduling and availability.

[ Iteratee.hs ]

I have updated the reflection package on hackage to use an idea for avoiding dummy arguments posted to the Haskell cafe mailing list by Bertram Felgenhauer, which adapts nicely to the case of handling Reflection. The reflection package implements the ideas from the Functional Pearl: Implicit Configurations paper by Oleg Kiselyov and Chung-chieh Shan.

Now, you no longer need to use big scary undefineds throughout your code and can instead program with implicit configurations more naturally, using Applicative and Monad sugar.

 
*Data.Reflection> reify (+)
    (reflect < *> pure 1 < *> (reflect < *> pure 2 < *> pure 3))
> 6
 

The Monad in question just replaces the lambda with a phantom type parameter, enabling the compiler to more readily notice that no instance can actually even try to use the value of the type parameter.

An example from the old API can be seen on the Haskell cafe.

This example can be made appreciably less scary now!

 
{-# LANGUAGE
     MultiParamTypeClasses,
     FlexibleInstances, Rank2Types,
     FlexibleContexts, UndecidableInstances #-}
import Control.Applicative
import Data.Reflection
import Data.Monoid
import Data.Tagged
 
newtype M s a = M a
 
instance Reifies s (a,a → a → a) ⇒ Monoid (M s a) where
    mempty = tagMonoid $ fst < $> reflect
    a `mappend` b = tagMonoid $
        snd < $> reflect < *> monoidTag a < *> monoidTag b
 
monoidTag :: M s a → Tagged s a
monoidTag (M a) = Tagged a
 
tagMonoid :: Tagged s a → M s a
tagMonoid (Tagged a) = M a
 
withMonoid :: a → (a → a → a) →
    (∀s. Reifies s (a, a → a → a) ⇒ M s w) → w
withMonoid e op m = reify (e,op) (monoidTag m)
 

And with that we can cram a Monoid dictionary -- or any other -- with whatever methods we want and our safety is assured by parametricity due to the rank 2 type, just like with the ST monad.

 
*> withMonoid 0 (+) (M 5 `mappend` M 4 `mappend` mempty)
9
 

[Edit: factored Tagged out into Data.Tagged in a separate package, and modified reflection to use that instead, with an appropriate version bump to satisfy the package versioning policy]