58 questions
1
vote
2
answers
124
views
How to understand foldTree function?
I have been deeply studying foldTree function in Haskell, which is defined as follows:
foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
go (Node x ts) = f x (map go ts)
...
- 1,311
3
votes
1
answer
93
views
Böhm-Beraducci encoding of Fix
I have the fixed point functor defined as follows:
newtype Fix f =
Fix
{ unfix ::
f (Fix f)
}
I would like to define a function which takes a Fix f and gives its Böhm-Beraducci ...
- 4,236
2
votes
1
answer
146
views
Why I get error "The type variable 'a occurs inside 'a t" with enabled -rectypes flag
I would like to write catamorphism in OCaml for any endofunctor (in terms of types) as a functor (in terms of OCaml):
module type Functor = sig
type 'a t
(* ... *)
end
module Make(F : ...
- 33
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
12
votes
1
answer
333
views
How to implement fixed points of functors in Java
I recently discovered how to simulate higher order types in Java in a somewhat roundabout way like so
interface H<F, T> { }
Here H encodes a higher order type that takes a type parameter F ...
- 10.9k
0
votes
1
answer
113
views
How to use daggy for conditional rendering in React
Lets say I have four components and I want to conditionally render them depending on a type prop using daggy:
In this example type prop value can be the string a, b, c or d
here is a working ...
- 9,927
1
vote
2
answers
190
views
BST: how to define `insert` in terms of catamorphic fold?
I have a typical binary search tree data type:
data Tree a
= Empty
| Branch a (Tree a) (Tree a) deriving Show
and a catamorphism
foldt :: b -> (a -> b -> b -> b) -> Tree a -> b
...
- 371
4
votes
2
answers
131
views
Why do I need a list fold to actually deconstruct a tree with this tree catamorphism?
A catamorphism can either deconstruct a value
[1,2,3].reduce((acc, x) => acc + x, 0); // 6
or maintain the structure and act like the identity of the underlying type:
[1,2,3].reduce((acc, x) => ...
user5536315
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
300
views
Implementing a catamorphism for Expression Trees
I am trying to implement an expression tree in Haskell as follows:
data ExprTr a b =
Variable a
| Constant b
| Add (ExprTr a b) (ExprTr a b)
...
- 45
4
votes
2
answers
386
views
Initial algebra for natural numbers
I'm trying to make sure I understand the initial algebra and catamorphism concept using the basic case of natural numbers, but I'm definitely missing something (also my Haskell syntax might be a mess)....
- 543
11
votes
1
answer
405
views
What is the connection between primitive recursion and catamorphisms?
Using the following catamorphism for natural numbers I can implement various arithmetic algorithms whithout having to deal with recursion:
cataNat :: b -> (b -> b) -> Natural -> b
cataNat ...
user5536315
5
votes
0
answers
252
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 [...
1
vote
1
answer
82
views
Having trouble translating code from Haskell to SML
I am trying to translate the following piece of code from SML to haskell but I'm having a bit of trouble.
type List_alg x u = (u, x->u->u)
list_cata :: List_alg x u -> [x] -> u list_cata ...
- 35