Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

If the definition of Initial Algebra is:

"An object is initial if there exists a unique morphism from the object to every object in the category"

Why do we need such object, and could any one give an example ?

share|improve this question
    
The quote only define "initial" not "initial algebra". –  Dave Clarke Jan 17 '13 at 12:05
    
Algebra is pair of (S,F) where S is a set and F is the functions on this set –  M.A Jan 17 '13 at 12:10
add comment

1 Answer

An initial algebra is an initial object in the category of $F$-algebras for a given endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$.

This construction is widely used to gives semantics to data-structures in (functional) programming languages. Intuitively, the functor $F$ captures the "shape" of the data-structure (e.g., $F(X) = 1 + A \times X$, with $A$ a fixed set for instance).

The underlying set $\mu F$ of the initial algebra $\langle \mu F, \alpha \rangle$ intuitively captures the set of syntactic expressions you can build by induction on the shape functor (e.g., for the previous functor with $A = \{a,b \}$, $\mu F = \{(1), (a,1), (b,1), (a,a,1), (a,b,1) \ldots \}$ is the set of finite lists of $A$-elements).

The initiality is the key property to construct inductive function (see catamorphism). Some excellent references on this topic:

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.