An Ode to Arrows


Hai Liu and Paul Hudak


We study a number of embedded DSLs for autonomous ordinary
differential equations (autonomous ODEs) in Haskell.  A naive
implementation based on the lazy tower of derivatives is straightforward
but has serious time and space leaks due to the loss of sharing when
handling cyclic and infinite data structures.  In seeking a solution to fix
this problem, we explore a number of DSLs ranging from shallow to
deep embeddings, and middle-grounds in between.  We advocate a solution
based on arrows, an abstract notion of computation that offers
both a succinct representation and an effective implementation.  Arrows
are ubiquitous in their combinator style that happens to capture both
sharing and recursion elegantly.  We further relate our arrow-based DSL
to a more constrained form of arrows called causal commutative arrows,
the normalization of which leads to a staged compilation technique improving ODE performance by orders of magnitude.


  ,author="Hai Liu and Paul Hudak"
  ,title="An Ode to Arrows"
  ,booktitle="Proc. Practical Aspects of Declarative Languages"
  ,publisher="Springer Verlag LNCS 5937"