ekmett / ekmett/hyperfunctions
What about other recursion schemes?
- Dominant language
- Haskell
- Stars
- 17
- Forks
- 7
- PR merge metrics
- No merged PRs in 30d
Description
Like a Tree fold:
```Haskell
data Tree a = Fork (Tree a) a (Tree a) | Nil
deriving Show
foldTree :: Tree a -> (b -> a -> b -> c) -> c -> Hyper b c
foldTree t f n = foldTree'
(\l x r -> Hyper $ \k -> f (invoke k l) x (invoke k r))
(pure n)
t where
foldTree' f' n' t' = case t' of
Nil -> n'
Fork l x r -> f' (foldTree' f' n' l) x (foldTree' f' n' r)
buildTree :: (forall b c . (b -> a -> b -> c) -> c -> Hyper b c) -> Tree a
buildTree g = run (g Fork Nil)
zipTree :: Tree a -> Tree b -> Tree (a, b)
zipTree xs ys = run $ foldTree xs f Nil . foldTree ys g Nothing
where
f (Just (l, _, _)) x (Just (_, y, r)) = Fork l (x, y) r
f _ x (Just (l, y, r)) = Fork l (x, y) r
f (Just (l, y, r)) x _ = Fork l (x, y) r
f _ _ _ = Nil
g l y r = Just (l, y, r)
```
Can `hyperfunctions` be combined with `recursion-schemes`?
EDIT: To expand a bit on this. I don't think the example I gave is of much use it is a bit strange and can traverse over the subtrees multiple times. You could fix this by traversing over both trees in the same order (e.g. depth first or breadth first and form left to right or the other way around). I wonder if there are other more complicated zipping patterns for non-list data types that are actually used in practice.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.