functional programming in terms of Set

I'm writing some notes about functional programming, so I'd want to describe some features of the category theory.

I visited wiki page about Category of Set, and I found this:

"The epimorphisms in Set are the surjective maps, the monomorphisms are the injective maps, and the isomorphisms are the bijective maps".

I'd want to explain Category theory it in term of computer science, so my question is:

• It's correct to consider only the category of Set?

• It's correct to consider only the category of Set when I explain functional

programming in term of Monoid/Functor/Algebraic Data/Product type and so

on?

I know that Category theory is not only Set, but It's important for me define a boundary where all my examples are correct on assumptions and definitions.

thanks
Mike.

You can use the category of sets as your model of how functional programming works as long as you do not allow general recursive definitions.

To see why general recursion is not valid in the category of sets, consider the following program (written in Haskell):

fix :: (Bool -> Bool) -> Bool
fix f = f (fix f)

If we interpret Bool as any set $B$ with at least two elements (for instance $B = \{0, 1, \bot\}$) then there will be a map $f : B \to B$ which does not have a fixed point (for instance $f(0) = 1$, $f(1) = \bot$, $f(\bot) = 0$). However, fix always computes fixed points.

You can use sets as long as all the recursive definitions are well-founded, i.e., the recursive calls always happen on strictly smaller arguments. Typical fold and map operations on lists and other inductively defined structures are like that.

To model recursion one has to change something. One possibility is to use domains which were invented precisely for this purpose.

StackExchange Computer Science Q#75494, answer score: 5