functional programming in terms of Set
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 -&gt; Bool) -&gt; 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.