[Haskell-cafe] Is inspectable recursion in Arrows possible?

1 Oct 2012

      Dear all,

I am trying to find a way to translate normal recursive notation such
as the |fib| function below to an arrow, retaining as much of the
structure of the recursive notation as possible. In addition I would
like to inspect the arrow. For this I created a datatype containing a
constructor for each Arrow{..} class:

Fib:
...
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
My R datatype, the instances for this datatype consist of the mapping
to the appropriate constructor:
...
data R x y where
  -- Category
  Id       :: R a a
  Comp     :: R b c    -> R a b          -> R a c
  -- Arrow
  Arr      :: (a -> b) -> R a b
  Split    :: R b c    -> R b' c'        -> R (b,b') (c,c')
  Cache    :: (a -> a -> Bool) -> R a a
  -- ArrowChoice
  Choice   :: R b c -> R b' c' -> R (Either b b') (Either c c')
  -- ArrowLoop
  Loop     :: R (b, d) (c, d)  -> R b c
  -- ArrowApply
  Apply    :: R (R b c, b) c
Translating the |fib| function from above first resulted in the
following definition. It is not allowed however due to the proc n on
the RHS of the declaration for |fibz|. I know that the grammar of the
Arrow Notation prevents this, but what is the underlying reason for
this?
...
fib' :: (ArrowChoice r, ArrowLoop r) => r Int Int
fib' = proc x -> do
  rec fibz <- proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x
Rewriting the function above to use a let statement compiles. However,
here my second problem arises. I want to be able to inspect the
recursion where it happens. However, in this case |fibz| is an
infinite tree. I would like to capture the recursion into fibz, I
hoped the rec would help me with that in combination with |loop| but
maybe I am wrong?
...
fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib'' = proc x -> do
  let fibz = proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x
Basically, is it possible to observe this kind of recursion? (Perhaps
even within the boundaries of Arrow Notation) I could perhaps add
another constructor like fix.

Any thoughts on this?

Cheers,
Alessandro Vermeulen