In this work we show that data types of finite lists and finite binary trees with integers on leaves can in fact be defined as initial algebras. We can define lists and trees in Haskell effortlessly, as well as related functors and the mapping, essential in the proof of initial algebra. We notice great similarity between languages of mathematics and Haskell. Data types in Haskell can be seen as objects inside category, while functions can be seen as morphisms in between. We prove that data types of infinite lists and infinite trees are final coalgebras, while implementation in Haskell remains the same as before for the finite ones. Therefore there is a distinction between mathematics and Haskell, i.e. coincidence of initial algebra and final coalgebra in Haskell and obvious difference between the two in mathematics.
|
