Instantly share code, notes, and snippets.

# spockz/gist:48b976dd4148ad060ec1Secret Created Oct 1, 2012

 Dear all, **Update:** See the [reddit][reddit] and [stackoverflow.com][stack] as well. 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 [reddit]: http://www.reddit.com/r/haskell/comments/11ayds/observable_recursion_in_arrows/ [stack]: http://stackoverflow.com/questions/12838391/observable-recursion-or-binding-in-arrows