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
172
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
96
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,408
2
votes
1
answer
115
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
267
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
153
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
186
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
136
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
175
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
258
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
194
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
8
votes
0
answers
192
views
Significant overhead implementing Catalan numbers with histomorphism
I'm exploring recursion-schemes recently and want to find some use cases for histomorphism - for which I think Catalan numbers could be a fun one (I'm aware there are better ways to implement Catalan ...
- 3,431
6
votes
2
answers
213
views
`refold :: Functor s => (a -> s a, a) -> (s b -> b) -> b` as a morphism between universal types
Various recursion scheme boil down to specific instantiation of refold
refold :: Functor s => (s b -> b) -> (a -> s a) -> a -> b
refold f g = go where go a = f (fmap go (g a))
What ...
- 9,845
10
votes
1
answer
378
views
How to use recursion-schemes to `cata` two mutually-recursive types?
I started with this type for leaf-valued trees with labeled nodes:
type Label = String
data Tree a = Leaf Label a
| Branch Label [Tree a]
I have some folds I'd like to write over this ...
- 93k
3
votes
1
answer
285
views
How is this hylo solution to the "coin-change" problem designed?
I came across a nice post on SO by @amalloy while looking for hylomorhism examples, that illustrate recursion scheme (RS) usage with useful discussion and full implementation:
{-# LANGUAGE ...
- 31
4
votes
3
answers
235
views
Is this some kind of morphism in the recursion-schemes?
I implemented Euclid's algorithm in the following way at first.
euclid x 0 = x
euclid x y = euclid y (x `mod` y)
The algorithm is tail-recursion, and I expect that it can be intuitively written with ...
- 95
4
votes
3
answers
605
views
Using recursion schemes in Haskell for solving change making problem
I'm trying to understand histomorphisms from this blog on recursion schemes. I'm facing a problem when I'm running the example to solve the change making problem as mentioned in the blog.
Change ...
- 655
-2
votes
2
answers
344
views
Non-tail recursive function that returns the last element in list without using reverse?
Im trying to make a non-tail recursive function returns the last element of a list without using reverse, map, iteration, mutation of any sort (built in or user-built). So far I have successfully made ...
4
votes
0
answers
161
views
Composing non-distributive monads in recursion-schemes
One of my favourite things about the recursion schemes in Haskell are the generalised morphisms (gcata etc.) that allow interleaving (co-)monadic computations with recursion, using a monad transformer ...
- 2,428
5
votes
1
answer
290
views
Haskell monadic parser with anamorphisms
My problem is how to combine the recursive, F-algebra-style recursive type definitions, with monadic/applicative-style parsers, in way that would scale to a realistic programming language.
I have ...
- 152
-5
votes
1
answer
228
views
How to convert recursive algorithm to dynamic programming? [closed]
I have this algorithm:
static int findMaxRec(int[] w, int[] v, int W, int n)
{
int max = int.MinValue;
int res;
for (int i = 0; i < n; i++)
{
if (w[i] <= W)
{
...
- 1,548
-1
votes
1
answer
165
views
How to solve this indirect recursion error? [duplicate]
#include <iostream>
#include <stdio.h>
using namespace std;
void funB(int n){
if (n>1){
cout<<n<<" ";
funA(n/2);
}
}
void funA(int m)
{
if (m>0)...
2
votes
2
answers
287
views
Recursion scheme allowing dependencies between recursive calls (an ordered catamorphism?)
I'm interested in a higher-order way (recursion scheme) to write recursive code in which there might be dependencies between recursive calls.
As a simplified example, consider a function that ...
- 474
2
votes
1
answer
146
views
Is it possible to create efficient recombining trees using (co)recursion?
By co-recursion I mean unfolding a tree, such as with anamorphism from Ed Kmett's recursion-schemes
By re-combining trees I mean graphs that share structure. For example, a binomial option pricing ...
- 2,428
1
vote
1
answer
62
views
How do I write a CV-Coalgebra in Idris2?
In Haskell, I can write
data CoAttr f a
= Automatic a
| Manual (f (CoAttr f a))
but Idris doesn't seem to allow such fix-point types with data. They do work with record, i.e. I can write
record ...
- 8,934
2
votes
0
answers
138
views
How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F? [closed]
The well-known Church encoding of natural numbers can be generalized to use an arbitrary functor F. The result is the type, call it C, defined by
data C = Cfix { run :: forall r. (F r -> r) -> ...
- 3,357
1
vote
1
answer
57
views
Morphism where the algebra receives the item's position
Which one is the appropriate morphism (recursion scheme) to use when the given item's position (index, or path) is required in the transformer function?
A simple example would be transforming a list [&...
- 20.4k
1
vote
1
answer
298
views
Recursion schemes with mutually recursive types in Scala
Given the following data types:
sealed trait Expression
final case class Add(a: Expression, b: Expression) extends Expression
final case class Block(statements: List[Statement], result: Expression) ...
- 892
5
votes
0
answers
251
views
Recursion scheme for tree-like structure
I'm trying to build the following recursion scheme:
{-# LANGUAGE DeriveFunctor #-}
import Data.Functor.Foldable
import Control.Comonad
import Control.Comonad.Cofree
data Term a = Str String | Array [...
9
votes
1
answer
423
views
Fix and Mu isomorphic
In the recursion-schemes package the following types are defined:
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
Are they isomorphic? If so, how do you prove it?
- 9,038
2
votes
0
answers
140
views
Using recursive types vs parameterized types with recursion schemes in practice in Haskell
I've recently looked up some guides on recursion schemes in Haskell, however most articles don't go much beyond implementing the basic infrastructure required for these concepts.
Given a recursive ...
6
votes
1
answer
223
views
How to update a structure with recursion schemes?
In recursion schemes, how can I construct something with type definition like (Recursive t, CoRecursive t) -> t -> ? -> t
I try to use recursion-schemes to update nodes. Taking list as an ...
- 406
6
votes
2
answers
352
views
How can I walk this type with a recursion scheme instead of explicit recursion?
Consider this code:
import Data.Maybe (fromMaybe)
data MyStructure = Foo Int | Bar String MyStructure | Baz MyStructure MyStructure | Qux Bool Bool MyStructure MyStructure deriving(Eq,Show)
...
6
votes
1
answer
299
views
Infinite recursive types in Coq (for Bananas and Lenses)
I'd like to see a Coq version of the Bananas, Lenses, etc. They are built up in the excellent series of blog posts at sumtypeofway Introduction to Recursion schemes
However, the blog post is in ...
- 5,898
2
votes
1
answer
564
views
Top-down recursion schemes
Can we define a recursion scheme (without losing any of their generality) that constructs the value top-down, instead of bottom-up?
This would be quite helpful as I've seen plenty of times where the ...
- 643
7
votes
2
answers
435
views
Can I write `foldr` (or `foldMap`) in terms of 'recursion schemes' `cata`?
I recently read about recursion schemes where catamorphisms are described as analogous to generalized foldr.
Is is possible to write an instance of Foldable (via either foldr or foldMap) in terms of ...
- 1,354
3
votes
2
answers
183
views
How to fold data structures from non-tail recursive algorithms?
I have a variadic lifting function that allows for flat monadic chains without deeply nested function composition:
const varArgs = f => {
const go = args =>
Object.defineProperties(
...
user5536315
4
votes
1
answer
201
views
Express a futumorphism specialized to lists as an imperative loop
I've been trying to translate this recursive Haskell implementation of a futumorphism specialized to Lists
futuL :: (a -> Maybe (b, ([b], Maybe a))) -> a -> [b]
futuL f x = case f x of
...
user5536315
2
votes
2
answers
606
views
What is the type of apomorphism specific to list and how is it implemented?
I am learning recursion schemes and it has proven very helpful to me to implement them specific to the list type. However, I got stuck on apomorphisms.
Here is an implementation of tails in terms of ...
user5536315
5
votes
3
answers
365
views
Catamorphism that allows looking at part of the final result
Is there a name for a recursion scheme that's like a catamorphism, but that allows peeking at the final result while it's still running? Here's a slighly contrived example:
toPercents :: Floating a =&...
1
vote
2
answers
379
views
A recursion scheme from Int -> Int?
The foldr identity is
foldr (:) []
More generally, with folds you can either destroy structure and end up with a summary value or inject structure in such a way that you end up with the same output ...
- 529
3
votes
1
answer
2k
views
How to define the fibonacci sequence using a fold for natural numbers?
I am currently learning folds in the sense of structural recursion/catamorphisms. I implemented power and factorial using a fold for natural numbers. Please note that I barely know Haskell, so the ...
user5536315
0
votes
4
answers
807
views
Generate lexicographic series efficiently in Python
I want to generate a lexicographic series of numbers such that for each number the sum of digits is a given constant. It is somewhat similar to 'subset sum problem'. For example if I wish to generate ...
- 77
3
votes
1
answer
414
views
Learning recursion schemes in Haskell by TicTacToe
Looking around, I noticed that recursion schemes are quite a general concept and I wanted to learn by experiencing it first hand. So I started implementing a minimax algorithm for TicTacToe. Here is a ...
- 5,106
1
vote
1
answer
106
views
Exhibiting the relationship between hylo and hyloM
I'm told the following functions are equivalent in power
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo f g = h where h = f . fmap h . g
hyloM :: (Traversable g, ...
- 2,846
7
votes
3
answers
717
views
How does compiler figure out fixed point of a functor and how cata work at leaf level?
I feel like understanding the abstract concept of fixed point of a functor, however, I am still struggling to figure out the exact implementation of it and its catamorphism in Haskell.
For example, ...
- 191