Questions tagged [category-theory]

Category theory is a branch of abstract mathematics concerned with exposing and describing the underlying structure of logical and mathematical systems. Concepts from category theory have proven to be extremely effective as tools for structuring both the semantics of programming languages and programs themselves. Various category theoretic structures are used as tools for abstraction in programming, including functors, monads, and algebras.

category-theory
Filter by
Sorted by
Tagged with
922 votes
5 answers
242k views

A monad is just a monoid in the category of endofunctors, what's the problem?

Who first said the following? A monad is just a monoid in the category of endofunctors, what's the problem? And on a less important note, is this true and if so could you give an explanation (...
Roman A. Taycher's user avatar
25 votes
2 answers
5k views

Is monad bind (>>=) operator closer to function composition (chaining) or function application?

In many articles I have read that monad >>= operator is a way to represent function composition. But for me it is closer to some kind of advanced function application ($) :: (a -> b) -> ...
Sergii Vorobei's user avatar
424 votes
7 answers
69k views

What are free monads?

I've seen the term Free Monad pop up every now and then for some time, but everyone just seems to use/discuss them without giving an explanation of what they are. So: what are free monads? (I'd say I'...
David's user avatar
  • 8,345
70 votes
4 answers
3k views

Is there a monad that doesn't have a corresponding monad transformer (except IO)?

So far, every monad (that can be represented as a data type) that I have encountered had a corresponding monad transformer, or could have one. Is there such a monad that can't have one? Or do all ...
Petr's user avatar
  • 63.1k
23 votes
5 answers
1k views

Why Functor class has no return function?

From categorical point of view, functor is pair of two maps (one between objects and another between arrows of categories), following some axioms. I have assumed, what every Functor instance is ...
uhbif19's user avatar
  • 3,199
85 votes
5 answers
6k views

Monads as adjunctions

I've been reading about monads in category theory. One definition of monads uses a pair of adjoint functors. A monad is defined by a round-trip using those functors. Apparently adjunctions are very ...
Bartosz Milewski's user avatar
28 votes
3 answers
1k views

Is this property of a functor stronger than a monad?

While thinking about how to generalize monads, I came up with the following property of a functor F: inject :: (a -> F b) -> F(a -> b) -- which should be a natural transformation in both a ...
winitzki's user avatar
  • 3,239
31 votes
2 answers
5k views

What is Applicative Functor definition from the category theory POV?

I was able to map Functor's definition from category theory to Haskell's definition in the following way: since objects of Hask are types, the functor F maps every type a of Hask to the new type F a ...
arrowd's user avatar
  • 33.8k
29 votes
2 answers
2k views

To what extent are Applicative/Monad instances uniquely determined?

As described this question/answers, Functor instances are uniquely determined, if they exists. For lists, there are two well know Applicative instances: [] and ZipList. So Applicative isn't unique (...
Petr's user avatar
  • 63.1k
13 votes
1 answer
684 views

How much is applicative really about applying, rather than "combining"?

For an uncertainty-propagating Approximate type, I'd like to have instances for Functor through Monad. This however doesn't work because I need a vector space structure on the contained types, so it ...
leftaroundabout's user avatar
355 votes
4 answers
29k views

What does "coalgebra" mean in the context of programming?

I have heard the term "coalgebras" several times in functional programming and PLT circles, especially when the discussion is about objects, comonads, lenses, and such. Googling this term gives pages ...
missingfaktor's user avatar
38 votes
3 answers
6k views

Arrows are exactly equivalent to applicative functors?

According to the famous paper Idioms are oblivious, arrows are meticulous, monads are promiscuous, the expressive power of arrows (without any additional typeclasses) should be somewhere strictly ...
Cactus's user avatar
  • 27.3k
28 votes
5 answers
2k views

Where do values fit in Category of Hask?

So we have Category of Hask, where: Types are the objects of the category Functions are the morphisms from object to object in the category. Similarly for Functor we have: a Type constructor as the ...
Ankur's user avatar
  • 33.5k
24 votes
2 answers
2k views

Are there contravariant monads?

Functors can be covariant and contravariant. Can this covariant/contravariant duality also be applied to monads? Something like: class Monad m where return :: a -> m a (>>=) :: m a ->...
ZhekaKozlov's user avatar
  • 38.2k
16 votes
1 answer
658 views

Do monad transformers, generally speaking, arise out of adjunctions?

In Adjoint functors determine monad transformers, but where's lift?, Simon C has shown us the construction... newtype Three u f m a = Three { getThree :: u (m (f a)) } ... which, as the answers ...
duplode's user avatar
  • 34.2k
37 votes
2 answers
4k views

Difference between free monads and fixpoints of functors?

I was reading http://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.html where an abstract syntax tree is derived as the free monad of a functor representing a set of ...
Daniel's user avatar
  • 27.2k
35 votes
3 answers
2k views

Lax monoidal functors with a different monoidal structure

Applicative functors are well-known and well-loved among Haskellers, for their ability to apply functions in an effectful context. In category-theoretic terms, it can be shown that the methods of ...
Ben Millwood's user avatar
  • 6,873
31 votes
2 answers
4k views

What's the relationship between profunctors and arrows?

Apparently, every Arrow is a Strong profunctor. Indeed ^>> and >>^ correspond to lmap and rmap. And first' and second' are just the same as first and second. Similarly every ArrowChoice is ...
Petr's user avatar
  • 63.1k
29 votes
5 answers
4k views

Can a monad be a comonad?

I know what a monad is. I think I have correctly wrapped my mind around what a comonad is. (Or rather, what one is seems simple enough; the tricky part is comprehending what's useful about this...) ...
MathematicalOrchid's user avatar
27 votes
3 answers
3k views

Foldable, Monoid and Monad

Consider the following signature of foldMap foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m This is very similar to "bind", just with the arguments swapped: (>>=) :: ...
Clinton's user avatar
  • 22.8k
23 votes
3 answers
2k views

How are functors in Haskell related to functors in category theory?

For as far as I understand, a functor is a mapping between two categories, for example from objects in to objects in where and are categories. In Haskell there is Hask in which the objects are ...
user avatar
19 votes
1 answer
1k views

What is exactly an indexed functor in Haskell and what are its usages?

When studying functors in Haskell I came up with Functor.Indexed type of functor. This functor defines an operation called imap. I didn't understood its definition and imap signature: imap :: (a -> ...
MainstreamDeveloper00's user avatar
16 votes
1 answer
2k views

What is Representable used for in Haskell?

I am looking to understand what does Representable stand for in Haskell. The definition Representable endofunctors over the category of Haskell types are isomorphic to the reader monad and so ...
mkUltra's user avatar
  • 2,958
13 votes
4 answers
2k views

Why is `pure` only required for Applicative and not already for Functor? [duplicate]

Reading this Wikibook about Haskell and Category Theory basics, I learn about Functors: A functor is essentially a transformation between categories, so given categories C and D, a functor F : C -...
ruben.moor's user avatar
  • 1,915
12 votes
2 answers
2k views

Once I have an F-Algebra, can I define Foldable and Traversable in terms of it?

I have defined an F-Algebra, as per Bartosz Milewski's articles (one, two): (This is not to say my code is an exact embodiment of Bartosz's ideas, it's merely my limited understanding of them, and ...
Ignat Insarov's user avatar
11 votes
2 answers
3k views

What's the relation of fold on Option, Either etc and fold on Traversable?

Scalaz provides a method named fold for various ADTs such as Boolean, Option[_], Validation[_, _], Either[_, _] etc. This method basically takes functions corresponding to all possible cases for that ...
missingfaktor's user avatar
11 votes
2 answers
609 views

Don't understand notation of morphisms in Monoid definition

I'm trying to understand what Monoid is from a category theory perspective, but I'm a bit confused with the notation used to describe it. Here is Wikipedia: In category theory, a monoid (or monoid ...
Bogdan Vakulenko's user avatar
9 votes
3 answers
398 views

What is the general case of QuickCheck's promote function?

What is the general term for a functor with a structure resembling QuickCheck's promote function, i.e., a function of the form: promote :: (a -> f b) -> f (a -> b) (this is the inverse of ...
Jonathan Cast's user avatar
8 votes
3 answers
2k views

Do all Type Classes in Haskell Have a Category Theoretic Analogue?

Consider a type class whose members are of type * -> *. For example: the Functor typeclass. It is a well-known fact that, in Haskell, there is a correspondence between this typeclass and its ...
George's user avatar
  • 7,167
7 votes
3 answers
671 views

Why are Monoidal and Applicative laws telling us the same thing?

I have learnt about Monoidal being an alternative way to represent Applicative not so long ago. There is an interesting question on Typeclassopedia: (Tricky) Prove that given your implementations ...
Zhiltsoff Igor's user avatar
6 votes
1 answer
320 views

What should a "higher order Traversable" class look like?

In this answer I made up on the spot something which looks a bit like a "higher order Traversable": like Traversable but for functors from the category of endofunctors on Hask to Hask. {-# LANGUAGE ...
Benjamin Hodgson's user avatar
4 votes
1 answer
230 views

Is it possible to write join down for Arrows, not ArrowApply?

I tried writing down joinArr :: ??? a => a r (a r b) -> a r b. I came up with a solution which uses app, therefore narrowing the a down to ArrowApply's: joinArr :: ArrowApply a => a r (a r b) ...
Zhiltsoff Igor's user avatar
1 vote
1 answer
99 views

What is the analog of Category in programming

I found that there is an isomorphism between logic and programming, called Curry-Howard correspondence, so is there any such equivalence for Category theory, which helps to understand things like ...
dk14's user avatar
  • 22.3k
66 votes
4 answers
5k views

What is monoid homomorphism exactly?

I've read about monoid homomorphism from Monoid Morphisms, Products, and Coproducts and could not understand 100%. The author says (emphasis original): The length function maps from String to ...
softshipper's user avatar
  • 33.3k
54 votes
8 answers
4k views

What is a monad in FP, in categorical terms?

Every time someone promises to "explain monads", my interest is piqued, only to be replaced by frustration when the alleged "explanation" is a long list of examples terminated by some off-hand remark ...
Kerrek SB's user avatar
  • 470k
40 votes
3 answers
3k views

What are the adjoint functor pairs corresponding to common monads in Haskell?

In category theory, a monad can be constructed from two adjoint functors. In particular, if C and D are categories and F : C --> D and G : D --> C are adjoint functors, in the sense that there is a ...
Chris Taylor's user avatar
  • 47.2k
33 votes
2 answers
3k views

Can liftM differ from liftA?

According to the Typeclassopedia (among other sources), Applicative logically belongs between Monad and Pointed (and thus Functor) in the type class hierarchy, so we would ideally have something like ...
Doug McClean's user avatar
  • 14.4k
32 votes
3 answers
4k views

Are all Haskell functors endofunctors?

I'm a bit confused, and need someone to set me straight. Lets outline my current understanding: Where E is an endofunctor, and A is some category: E : A -> A. Since all types and morphisms in ...
Jonathan Sterling's user avatar
29 votes
5 answers
2k views

What are zygo/meta/histo/para/futu/dyna/whatever-morphisms?

Is there a list of them with examples accessible to a person without extensive category theory knowledge?
Fixpoint's user avatar
  • 9,739
28 votes
1 answer
5k views

Step by Step / Deep explain: The Power of (Co)Yoneda (preferably in scala) through Coroutines

some background code /** FunctorStr: ∑ F[-]. (∏ A B. (A -> B) -> F[A] -> F[B]) */ trait FunctorStr[F[_]] { self => def map[A, B](f: A => B): F[A] => F[B] } trait Yoneda[F[_], A] {...
Mzk Levi's user avatar
  • 814
21 votes
2 answers
405 views

Relation between `DList` and `[]` with Codensity

I've been experimenting with Codensity lately which is supposed to relate DList with [] among other things. Anyway, I've never found code that states this relation. After some experiments I ended up ...
raichoo's user avatar
  • 2,557
21 votes
2 answers
2k views

How does lifting (in a functional programming context) relate to category theory?

Looking at the Haskell documentation, lifting seems to be basically a generalization of fmap, allowing for the mapping of functions with more than one argument. The Wikipedia article on lifting ...
Nathan BeDell's user avatar
16 votes
1 answer
645 views

Open Type Level Proofs in Haskell/Idris

In Idris/Haskell, one can prove properties of data by annotating the types and using GADT constructors, such as with Vect, however, this requires hardcoding the property into the type (e.g. a Vect has ...
David Harrison's user avatar
16 votes
4 answers
2k views

What is the main difference between Free Monoid and Monoid?

Looks like I have a pretty clear understanding what a Monoid is in Haskell, but last time I heard about something called a free monoid. What is a free monoid and how does it relate to a monoid? Can ...
mkUltra's user avatar
  • 2,958
15 votes
1 answer
350 views

Structurally enforced Free Alternative, without left distributivity

There is a nice Free Alternative in the great free package, which lifts a Functor to a left-distributive Alternative. That is, the claim is that: runAlt :: Alternative g => (forall x. f x -> g ...
Justin L.'s user avatar
  • 13.6k
15 votes
2 answers
428 views

Where does the name "section" come from for a partially applied infix operator?

In Haskell, we use the term "section" to indicate a partially applied function used in infix position. For instance, for a function foo :: a -> b -> c and values x :: a and y :: b, we have the ...
chepner's user avatar
  • 515k
14 votes
2 answers
746 views

List based on right Kan extension

In the ``Kan Extensions for Program Optimisation'' by Ralf Hinze there is the definition of List type based on right Kan extension of the forgetful functor from the category of monoids along itself (...
Katty J.'s user avatar
  • 686
13 votes
1 answer
2k views

Use cases for adjunctions in Haskell

I have been reading up on adjunctions during the last couple of days. While I start to understand their importance from a theoretical point of view, I wonder how and why people use them in Haskell. ...
michid's user avatar
  • 10.7k
12 votes
3 answers
506 views

Is there any intuition to understand join two functions in Monad?

join is defined along with bind to flatten the combined data structure into single structure. From type system view, (+) 7 :: Num a => a -> a could be considered as a Functor, (+) :: Num a =&...
Kamel's user avatar
  • 1,866
12 votes
4 answers
2k views

What kind of morphism is `filter` in category theory?

In category theory, is the filter operation considered a morphism? If yes, what kind of morphism is it? Example (in Scala) val myNums: Seq[Int] = Seq(-1, 3, -4, 2) myNums.filter(_ > 0) // Seq[Int]...
Polymerase's user avatar
  • 6,611