-
-
Save spockz/48b976dd4148ad060ec1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment