Questions tagged [ct.category-theory]

Questions in category theory

Filter by
Sorted by
Tagged with
9 votes
2 answers

Closure ordinals for inductive types with function spaces

Functors built from finite products and sums have closure ordinal $\omega$, detailed nicely in this manuscript by Francois Metayer. i.e. we can reach the inductive type $nat := \mu X. 1 + X$ by ...
Andrew Cave's user avatar
17 votes
2 answers

A mathematical (categorical) description of type classes

A functional language can be viewed as a category where its objects are types and morphisms functions between them. How do type classes fit in this model? I assume we should only consider those ...
Petr's user avatar
  • 2,571
47 votes
2 answers

Explaining Applicative functor in categorical terms - monoidal functors

I'd like to understand Applicative in terms of category theory. The documentation for Applicative says that it's a strong lax ...
Petr's user avatar
  • 2,571
3 votes
1 answer

What can the Haskell package category-extras be used for?

See here. Has anyone attempted to use this to verify category theoretic proofs? Given the relationship between categories and graphs, are there some applications with respect to graph algorithms? What ...
Cameron Smith's user avatar
25 votes
3 answers

Regular languages from category-theoretical point of view

I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
Alexei Averchenko's user avatar
2 votes
2 answers

Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source) Wikipedia's definition (source) = It looks ...
hhh's user avatar
  • 71
20 votes
4 answers

Data Structure isomorphisms

Disclaimer: I am not a CS theorist. Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data ...
anon's user avatar
  • 203
4 votes
5 answers

Advantages and specific applications of massively parallel programming thesis idea

I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications. I'm searching for an application ...
Paul's user avatar
  • 43
12 votes
2 answers

Is there such a thing as a weak coalgebra homomorphism?

Given an endofunctor $F : Set \rightarrow Set$, we can define observation functions as functions that are polymorphic for any $F$-coalgebra, that is $obs$ is defined for any $F$-coalgebra $\langle A, ...
Francisco Mota's user avatar
-6 votes
1 answer

What function has the signature $ A \times \left ( B + C \right ) \rightarrow \left ( A \times B \right ) + \left ( A \times C \right ) $?

$ A \times \left ( B + C \right ) $ is isomorphic to $ \left ( A \times B \right ) + \left ( A \times C \right ) $, right? That means there's a function from one to the other and another function back....
Fox's user avatar
  • 1
15 votes
2 answers

Proof theory of biproducts?

A category has biproducts when the same objects are both the products and coproducts. Has anyone investigated the proof theory of categories with biproducts? Perhaps the best-known example is the ...
Neel Krishnaswami's user avatar
17 votes
2 answers

Category theory, computational complexity, and combinatorics connections?

I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, and there is an obvious correspondence between recursively (and polynomially) defined ...
Stefan Petrov's user avatar
12 votes
1 answer

When do coherence spaces have pullbacks and pushouts?

$\newcommand{\symp}{\Bumpeq}$ A coherence relation $\symp_X$ on a set $X$ is a reflexive and symmetric relation. A coherence space is a pair $(X, \symp_X)$, and a morphism $f : X \to Y$ between ...
Neel Krishnaswami's user avatar
10 votes
2 answers

Are there semi-decision procedures for this theory?

I have the following typed theory |- 1_X : X -> X f : A -> B, g : B -> C |- compose(g,f) : A -> C F, f : A -> B |- apply(F,f) : F(A) -> F(B) ...
quanta's user avatar
  • 221
11 votes
3 answers

What is a good Category Theory-Domain Theory dictionary?

When dealing with the domain theoretic categories (say CPO and $\omega$CPO), I frequently wish for a dictionary for the language of category theory in domain theory. That is, given a concept, say ...
Ohad Kammar's user avatar
  • 2,667
28 votes
2 answers

A category of NP-complete problems?

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, ...
Paul Allen Grubbs's user avatar
25 votes
2 answers

What is the folk model of linear logic?

Probably the most common application of linear types in PL is to use them to give languages which control aliasing (i.e., a linear value has a single pointer to it, more or less). But there's a ...
Neel Krishnaswami's user avatar
19 votes
3 answers

Reader, Writer monads

Let $C$ be a CCC. Let $(\times)$ be a product bifunctor on $C$. As Cat is CCC, we can curry $(\times)$: $curry (\times) : C \rightarrow(C \Rightarrow C)$ $curry (\times) A = \lambda B. A \times B$ ...
beroal's user avatar
  • 557
28 votes
2 answers

Bounded-input bijections of infinite sequences

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution. It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ ...
Colin McQuillan's user avatar
113 votes
7 answers

Solid applications of category theory in TCS?

I've been learning a few bits of category theory. It certainly is a different way of looking at things. (Very rough summary for those who haven't seen it: category theory gives ways of expressing all ...
Ryan Williams's user avatar
7 votes
1 answer

Maximal subcoalgebras of an $F+1$-coalgebra corresponding to an $F$-coalgebra

This context of this question is Rutten's Universal Coalgebra, used for modelling systems. I'm interested in finding a description of a functor between different types of coalgebras corresponding to ...
Dave Clarke's user avatar
  • 16.7k
6 votes
2 answers

Proof of a unique homomorphism from an initial object

What is the proof that there is only one homomorphism from an initial object to another object?
Jason Reich's user avatar

1 2