• Download Gist
Literate Haskell

Dear all,

Update: See the reddit and 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 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.