ekmett / ekmett/hyperfunctions

What about other recursion schemes?

Open
#5 0 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.