111 questions
1
vote
1
answer
76
views
Left scan over Cofree-annotated ASTs
I need to extend the definition of left scan to Cofree structures, to accumulate annotations from the root of an annotated AST to the leaves, however I don't understand why my naive implementation ...
- 841
4
votes
2
answers
181
views
Chronomorphisms in Scala
I'm learning recursion patterns, but I can't figure out the usefulness of futumorphism and histomorphism.
The couple of Scala examples I found look very unconvincing. I also found Haskell examples, ...
- 107
-1
votes
1
answer
106
views
What is the difference between head and tail recursion when reversing a linked list?
I am learning about different recursive approaches for reversing a linked list in C++. I have implemented both head and tail recursion methods, but I'm unsure about their differences and which one is ...
- 11
2
votes
1
answer
71
views
Converting an ADT to use recursion schemes
I have this data structure, that I'd like to introduce recursion schemes to in order to attach metadata to nodes:
sealed trait Schema[A] extends Product, Serializable
sealed trait Collection[A] ...
- 7,418
2
votes
1
answer
122
views
Writing foldLeft equivalent for recursion schemes
This is a definition of foldr and foldl in terms of foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl :: (a -> b -> a)...
- 141
1
vote
1
answer
103
views
Modeling a dependent computation task?
I need to model a computation task and some sub-tasks depend on it:
First I run a task, if it fails then it's over. If it succeeds then run a bunch of sub-tasks(zero or many), any of them can fail or ...
- 13
5
votes
1
answer
278
views
Memoizing a recursion scheme
Is it possible to memoize a recursion scheme? If so, how would you?
For example, the following uses anamophism and catamorphism
newtype Fix f = In (f (Fix f))
deriving instance (Eq (f (Fix f))) => ...
- 141
1
vote
1
answer
158
views
Using a paramorphism inside of an apomorphism
I'm trying to use paramorphisms and apomorhisms (in haskell):
-- Fixed point of a Functor
newtype Fix f = In (f (Fix f)) ...
- 141
3
votes
1
answer
156
views
How to implement an anamorphism such that it can be build upon any value of the the return type (rather than just the base case)
I've got anamorphism defined as follows:
-- Fixed point of a Functor
newtype Fix f = In (f (Fix f))
deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (...
- 141
1
vote
1
answer
201
views
Lattice paths algorithm using recursion schemes
I'm playing around with some recursion schemes, namely catamorphisms and anamorphisms, and would like to try to implement a solution to the lattice paths algorithm as described below using them (taken ...
- 141
2
votes
1
answer
140
views
What do the generic type constraints ":<:" and ":+:" mean in this Scala example?
From this talk about nanopass compilers in 2017 (https://github.com/sellout/recursion-scheme-talk/blob/master/nanopass-compiler-talk.org) I found the code snippet below. In this code snipped, I see ...
- 1,535
2
votes
1
answer
177
views
Selectively recurse into left or right subtree of a binary tree using a catamorphism (or any recursion scheme)
I'm trying to implement a binary search tree (or set) using fixed points of functors. I've defined my fixed point as follows:
newtype Fix f = In (f (Fix f))
out :: Fix f -> f (Fix f)
out (In f)...
- 529
3
votes
2
answers
270
views
removing explicit recursion by replacing catamorphism
I have this AST data structure
data AST = Integer Int
| Let String AST AST
| Plus AST AST
| Minus AST AST
| Times AST AST
| Variable String
| ...
- 1,484
1
vote
1
answer
196
views
How can I avoid explicit recursion in this case?
I wound up with this skeleton:
f :: (Monad m) => b -> m ()
f x = traverse_ (f . g x) =<< h x -- how avoid explicit recursion?
g :: b -> a -> b
-- h :: (Foldable t) => b -> m (t ...
- 459
8
votes
1
answer
1k
views
Alpha Beta Pruning with Recursion Schemes
I'm trying to get more proficient with recursion schemes as they have so far been really helpful for turning gnarly explicit recursion code into something less spike-y. One of the other tools I tend ...
- 1,484