| On the Semantics of Nested Datatypes (2000) | |||||||||||||||
Abstract | |||||||||||||||
| Introduction Nested datatypes were introduced in [1] as recursively dened parameterised datatypes in which the parameter of the datatype changes in the recursive call. For example, the Nest datatype, which represents perfectly balanced binary trees, can be dened in Haskell by data Nest a = Nil j Cons(a; Nest (a; a)) (1) The standard semantic denition of recursively dened datatypes is as initial algebras in the category Set of sets and total functions [6]. It was shown in [1] that this theory is inadequate to describe nested datatypes. Instead, one solution proposed there was to dene them as initial algebras in the functor category Nat(Set), with objects all endofunctors on Set and arrows all natural transformations between them. It was observed, however, that this approach had not been vali | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||