Programmation fonctionnelle: qu'est ce qu'une "mauvaise"liste?

je pense qu'il est plus facile d'expliquer cela en utilisant Scheme.

une liste est Une chaîne de paires qui se terminent par une liste vide. En d'autres termes, une liste se termine par une paire dont le cdr est ()

(a . (b . (c . (d . (e . ()))))) 

;; same as

(a b c d e)

une chaîne de paires qui ne se termine pas dans la liste vide est appelée une liste incorrecte. Notez que la mauvaise liste n'est pas une liste. La liste et les notations en pointillés peuvent être combinées pour représenter des listes inappropriées, comme le montrent les notations équivalentes suivantes:

 (a b c . d)
 (a . (b . (c . d)))

un exemple d'erreur habituelle qui conduit à la construction d'une liste incorrecte est:

scheme> (cons 1 (cons 2 3))
(1 2 . 3)

Notez le point dans (12 . 3)---c'est comme le point (2 . 3), en disant que le cdr d'une paire pointe à 3, Pas une autre paire ou '(). C'est, c'est une mauvaise liste, et pas seulement une liste de paires. Il ne correspond pas à la définition récursive d'une liste, parce que quand nous arrivons à la deuxième paire, son cdr n'est pas une liste--c'est un entier.

Scheme a imprimé la première partie de la liste comme si c'était une liste normale liée au cdr, mais quand il est arrivé à la fin, il ne pouvait pas le faire, donc il a utilisé "point notation."

vous ne devriez généralement pas avoir à vous soucier de la notation des points, parce que vous devriez utiliser des listes normales, pas une liste incorrecte. Mais si vous voyez un point inattendu quand Scheme imprime une structure de données, c'est une bonne supposition que vous avez utilisé cons et lui a donné une non-liste comme sa deuxième argument -- quelque chose en dehors d'une autre paire ou ().

Scheme fournit une procédure pratique qui crée des listes appropriées, appelées list . list peut prendre n'importe quel nombre d'arguments, et construit une liste appropriée avec ces éléments dans cet ordre. Vous n'avez pas à vous rappeler de fournir la liste vide---la liste se termine automatiquement de cette façon.

Scheme>(list 1 2 3 4)
(1 2 3 4)

Courtoisie: An Introduction au schéma

la définition d'une liste dans Erlang est donnée dans le manuel - spécifiquement la Section 2.10

En Erlang, la seule chose que vous devez savoir sur une mauvaise listes est de savoir comment les éviter, et la façon de le faire est très simple - il est tout à la première chose que vous allez construire votre liste. Les listes suivantes créent toutes des listes appropriées:

A = [].
B = [term()].
C = [term(), term(), term()].

dans tous ces cas le syntaxe assure qu'il y a une queue cachée "vide" qui correspond à "[] sorte de à la fin....

ainsi, les opérations suivantes produisent toutes une liste appropriée:

X = [term() | A].
Y = [term() | B].
Z = [term() | C]. 

ce sont toutes des opérations qui ajoutent une nouvelle tête à une liste appropriée.

ce qui rend utile est que vous pouvez alimenter chacun de X , Y ou Z dans une fonction comme:

func([], Acc)      -> Acc;
func([H | T], Acc) -> NewAcc = do_something(H),
                      func(T, [NewAcc | Acc]).

et ils déchireront la liste et se termineront sur la clause supérieure quand le caché liste vide à la queue est tout ce qui reste.

le problème vient quand votre liste de base a été mal faite, comme cela:

D = [term1() | term2()]. % term2() is any term except a list

Cette liste n'est pas ont le cachés liste vide comme le terminal de la queue, il a un terme...

D'ici vers le bas est mince comme Robert Virding a souligné dans les commentaires

alors comment écrire une clause de terminal pour ça?

ce qui le rend exaspérant est que il n'y a aucun moyen de voir si une liste est inappropriée en l'inspectant... imprimez ce fichu truc qui a l'air bon... Donc, vous vous retrouvez créer une liste de base incorrecte, faire quelque chose sur elle, la passer autour, et puis soudainement kabloowie vous avez un accident miles d'où l'erreur est et vous tirez vos cheveux et crier et crier...

mais vous devrait utiliser le dialyzer pour renifler ces petites bêtes pour vous.

à la Suite de Le commentaire de Robert j'ai essayé d'imprimer une liste incorrecte et, voici, il est évident:

(arrian@localhost)5>A = [1, 2, 3, 4].
[1,2,3,4]
(arrian@localhost)5> B = [1, 2, 3 | 4].
[1,2,3|4]
(arrian@localhost)6> io:format("A is ~p~nB is ~p~n", [A, B]).
A is [1,2,3,4]
B is [1,2,3|4]

j'avais passé un certain temps à chercher une liste incorrecte une fois et m'étais convaincu qu'elle était invisible, bien ah ken noo !

Pour comprendre qu'une mauvaise liste, vous devez d'abord comprendre la définition d'une bonne liste.

spécifiquement ,la "découverte soignée" des listes est que vous pouvez représenter une liste en utilisant seulement des formes avec un nombre fixe d'éléments, à savoir:

;; a list is either 
;; - empty, or
;; - (cons v l), where v is a value and l is a list.

cette "définition de données" (en utilisant les termes de comment concevoir des programmes) a toutes sortes de nice properties. Une des plus belles est que si nous définissons le comportement ou la signification d'une fonction sur chaque "branche" de la définition des données, nous sommes garantis de ne pas manquer une affaire. De manière plus significative, des structures comme celle-ci conduisent généralement à de belles solutions propres récursives.

exemple classique de" longueur":

(define (length l)
  (cond [(empty? l) 0]
        [else (+ 1 (length (rest l))]))

bien sûr, tout est plus joli à Haskell:

length []    = 0
length (f:r) = 1 + length r

alors, qu'est-ce que cela a à voir avec des listes inappropriées?

Eh bien, une liste incorrecte utilise cette définition de données, à la place:

;; an improper list is either
;; - a value, or
;; - (cons v l), where v is a value and l is an improper list

Le problème est que cette définition conduit à l'ambiguïté. En particulier, les première et deuxième affaires se chevauchent. Supposons que je définisse "longueur" pour une liste irrégulière thusly:

(define (length l)
  (cond [(cons? l) (+ 1 (length (rest l)))]
        [else 1]))

le problème est que j'ai détruit la belle propriété que si je prends deux valeurs et les mettre dans une liste incorrecte avec (cons a b), le résultat a la longueur deux. Pour voir pourquoi, supposons que je considère les valeurs (cons 34) et (cons 45). Le résultat est (cons (cons 34) (cons 45)), qui peut être interprété soit comme la liste irrégulière contenant (cons 34) et (cons 45), ou comme la liste irrégulière contenant (cons 34), 4, et 5.

dans un langage avec un système de type plus restrictif (par exemple Haskell), la notion d'une "liste incorrecte" n'a pas tout à fait autant de sens; vous pourriez l'interpréter comme un type de données dont le cas de base a deux choses en elle, ce qui n'est probablement pas ce que vous voulez que ce soit.

je pense qu'il se réfère peut-être à une" paire de pointillés " dans le LISP, par exemple une liste dont la dernière cellule de cons a un atome, plutôt qu'une référence à une autre cellule de cons ou zéro, dans le cdr.

EDIT

Wikipedia suggère qu'une liste circulaire est également considérée comme inappropriée. Voir

http://en.wikipedia.org/wiki/Lisp_ (langue de programmation)

et rechercher "impropre" et vérifier les notes.

je dirais que l'implication d'une liste incorrecte est qu'un traitement récursif de la liste ne correspond pas à la condition de résiliation typique.

par exemple, dites que vous appelez ce qui suit sum , en Erlang, sur une liste incorrecte:

sum([H|T]) -> H + sum(T);
sum([]) -> 0.

alors il soulèvera une exception puisque la dernière queue n'est pas la liste vide, mais un atome.

dans Common Lisp impropre lists are defined as:

• en pointillés qui ont un "atome" terminal non nul.

exemple

  (a b c d . f)

ou

• listes circulaires

exemple

  #1=(1 2 3 . #1#)

Une liste est composée de cellules, chaque cellule composée de deux pointeurs. Première pointant vers l'élément de données, le second, à la cellule suivante, ou nulle à la fin de la liste.

si le second ne pointe pas vers une case (ou zéro), la liste est incorrecte. Les langages fonctionnels vous permettront très probablement de construire des cellules, vous devriez donc être en mesure de générer des listes inappropriées.

en Erlang (et probablement aussi dans D'autres langues FP) vous pouvez sauvegarder un peu de mémoire en stockant vos 2-tuples comme des listes inappropriées:

2> erts_debug:flat_size({1,2}).
3
3> erts_debug:flat_size([1|2]).
2

dans Erlang, une liste appropriée est celle où [H|T] .

H est à la tête de la liste et T est le reste de la liste à une autre liste.

une liste incorrecte n'est pas conforme à cette définition.