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

[Alessandro Vermeulen]

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