Montag, 28. März 2011

monads in R: sapply and foreach

Monads are a powerful way of structuring functional programs. They are used in functional languages like haskell or F# to define control flows (like handling concurrency, continuations, side effects such as input/output, or exceptions). Basically a monad is defined by a type and two functions, unit and bind. Alternatively one can define a monad using two other functions together with a data type, namely: join and fmap. In following I want to show some analogies between fmap and join and the functions sapply and c in R.

fmap is defined as a (higher-order) function that fulfills the following relations (in haskell and the . denotes function concatenation):

fmap id = id
fmap (f . g) = (fmap f) . (fmap g)

the definition in R is then:
fmap <- function(f) sapply(x,f)

for the join function the following has to be valid (also in haskell):

join . fmap join = join . join

this translates to the following code identities in R (read === as "is the same as"):
c( fmap(c)(x)) === c(sapply(x,c)) === c(x) === x

Therefore c and sapply define the list monad in R. Can we go one step further and define some notation like the "do" notation in haskell in R? I think this is already done. It is the foreach package.

foreach(x=a) %do% f(x)

is the exact translation of the corresponding haskell monadic "do" notation (again in haskell):

fmap f x = do r <- x return (f r)
join x = do a <- x a

and in R:
fmap(f)(x) === foreach(r=x) %do% f(r) === sapply(x,f)
join(x) === foreach(a=x) %do% a === c(x)

Now hat does this mean for the several foreach extensions (doMC, doMPI, doRedis, doSNOW)?
They are all implementations of monads in R. So it would be very interesting to port all the other monadic types from other functional programming languages to R.

Keine Kommentare: