[Haskell-cafe] Is inspectable recursion in Arrows possible?
Alessandro Vermeulen
a.vermeulen at students.uu.nl
Mon Oct 1 20:05:19 CEST 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
More information about the Haskell-Cafe
mailing list