Haskell – 46 – tipi di dati algebrici ricorsivi- 2

Continuo da qui, copio qui, scrollare fino a “Generalised Syntax”.

Sintassi generalizzata
[Previously], we briefly discussed the generalised notation for algebraic data types enabled with the GADTs language pragma. In that generalised notation, Maybe is defined as

data Maybe a where
    Just     :: a -> Maybe a
    Nothing  ::      Maybe a

The data constructor Just can be viewed as a function that takes a value of type a and returns a Maybe a, and Nothing as a constant which returns a Maybe a value of any type a. In other words, the data constructors of a parametric data type are themselves parametric polymorphic functions — i.e., functions whose type signature contain unconstrained type variables, here the a.

Costruttori di tipo ricorsivo
Just like the Maybe type constructor, the list type constructor [] is parametric — i.e., it takes as a type argument the list’s element type. And although lists come with special, builtin syntax (the square bracket notation), we can define a data type that is functionally equivalent to standard Haskell lists. Standard Haskell lists come with two parametric polymorphic data constructors: [] :: [a], which returns an empty list of any type a, and (:) :: a -> [a] -> [a], which adds an element to the front of a list. The new and interesting point about lists is that the type of the second argument of the data constructor (:) is the list type itself — in other words, the definition of lists depends on itself. Hence, we call such types recursive (just as with functions whose definition depends on itself).

The following recursive data type definition corresponds functionally to that of the builtin list type. However, it uses two alphanumeric data constructor, Cons and Nil, instead of the builtin special syntax, [] and (:). (Strictly speaking, user-defined data constructors can be formed from infix symbols, starting with a colon character (:). However, [] is not in the realm of notation that can be used in user-provided definitions.)

data List a
  = Cons a (List a)
  | Nil

or, alternatively, in the generalised syntax

data List a where
  Cons :: a -> List a -> List a
  Nil  ::                List a

Conceptually, our new List type is the same as builtin lists, just without the syntactic sugar of the bracket notation. Hence, we need to write

Cons (Cons (Cons (Const 4 Nil) 3) 2) 1)

instead of the more compact [1, 2, 3, 4]. We can, however, use infix notation as with 1 : 2 : 3 : 4 : [] by enclosing Cons in backquotes:

1 `Cons` (2 `Cons` (3 `Cons` (4 `Cons` Nil)))

(We could even avoid the parentheses by using a suitable infix operator declaration to fix the associativity of Cons.)

So in practice, we will rarely find the need to define lists ourselves (and instead use the syntactically more convenient builtin ones). However, lists as a collection type are limited, and we will see that we can often do better with user-defined recursive data types of a different structure.


Posta un commento o usa questo indirizzo per il trackback.



Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: