Le problème dans
((((a ++ b) ++ c) ++ d) ++ e) ++ f
est le site de nidification. Les applications de l' (++) sont de gauche imbriqués, et qui est mauvais, droit de la nidification
a ++ (b ++ (c ++ (d ++ (e ++f))))
ne serait pas un problème. C'est parce qu' (++) est défini comme
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
donc, pour trouver l'équation de l'utilisation, de la mise en œuvre doit plonger dans l'arborescence d'expression
(++)
/ \
(++) f
/ \
(++) e
/ \
(++) d
/ \
(++) c
/ \
a b
jusqu'à ce qu'il détermine si l'opérande de gauche est vide ou pas. Si elle n'est pas vide, sa tête est prise et on fait barboter le sommet, mais la queue de l'opérande de gauche est restée intacte, de sorte que lorsque l'élément suivant de la concaténation est de rigueur, la même procédure recommence.
Lorsque les concaténations sont de droite imbriquées, l'opérande gauche de l' (++) est toujours au top, et la vérification de la vacuité/jaillissant de la tête sont en O(1).
Mais quand les concaténations sont de gauche imbriqués, n couches de profondeur, pour atteindre le premier élément, n des nœuds de l'arbre doit être parcouru pour chaque élément du résultat (en provenance de la première liste, n-1 pour ceux qui viennent de le deuxième, etc.).
Permettez-nous de considérer a = "hello" dans
hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f
et nous voulons les évaluer en take 5 hi. Alors d'abord, il doit être vérifié si l'
(((a ++ b) ++ c) ++ d) ++ e
est vide. Pour cela, il doit être vérifié si l'
((a ++ b) ++ c) ++ d
est vide. Pour cela, il doit être vérifié si l'
(a ++ b) ++ c
est vide. Pour cela, il doit être vérifié si l'
a ++ b
est vide. Pour cela, il doit être vérifié si l'
a
est vide. Ouf. Ce n'est pas le cas, nous pouvons faire émerger de nouveau, l'assemblage
a ++ b = 'h':("ello" ++ b)
(a ++ b) ++ c = 'h':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)
et pour l' 'e', il faut le répéter, et pour l' 'l's trop...
Dessin d'une partie de l'arbre, le phénomène de propagation qui va comme ceci:
(++)
/ \
(++) c
/ \
'h':"ello" b
devient première
(++)
/ \
(:) c
/ \
'h' (++)
/ \
"ello" b
et puis
(:)
/ \
'h' (++)
/ \
(++) c
/ \
"ello" b
tout le chemin du retour vers le haut. La structure de l'arbre qui devient le droit de l'enfant de le top-niveau (:) enfin, est exactement la même que la structure de l'arbre d'origine, à moins que la gauche de la liste est vide, lorsque le
(++)
/ \
[] b
les nœuds est effondré juste b.
Donc, si vous avez laissé imbriquées les concaténations de courtes listes, la concaténation devient quadratique parce que pour obtenir la tête de la concaténation est un O(imbrication de la profondeur) de l'opération. En général, la concaténation de gauche imbriquée
(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1
est - O(sum [i * length a_i | i <- [1 .. d]]) d'évaluer pleinement.
Avec la différence, les listes (sans le newtype wrapper pour la simplicité de l'exposition), il n'est pas important de savoir si les compositions sont de gauche imbriquée
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)
droite ou imbriqués. Une fois que vous avez parcouru le site de nidification pour atteindre l' (a ++)que (++) est hissé en haut de l'arborescence d'expression, afin d'obtenir à chaque élément de l' a est de nouveau en O(1).
En fait, l'ensemble de la composition est réassociées avec la différence les listes, dès que vous avez besoin de le premier élément,
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f
devient
((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))
et après cela, chaque liste, qui est à l'opérande de gauche de haut-niveau (++) après la liste ci-dessus a été consommé.
La chose importante est que l'ajoutant la fonction (a ++) pouvez commencer à produire son résultat sans l'inspecter son argument, de sorte que la réassociation de
($)
/ \
(.) f
/ \
(.) (e ++)
/ \
(.) (d ++)
/ \
(.) (c ++)
/ \
(a ++) (b ++)
via
($)---------
/ \
(.) ($)
/ \ / \
(.) (d ++) (e ++) f
/ \
(.) (c ++)
/ \
(a ++) (b ++)
pour
($)
/ \
(a ++) ($)
/ \
(b ++) ($)
/ \
(c ++) ($)
/ \
(d ++) ($)
/ \
(e ++) f
n'a pas besoin de savoir quelque chose au sujet de la composée des fonctions de la liste définitive f, donc c'est juste un O(depth) de réécriture. Puis le haut-niveau
($)
/ \
(a ++) stuff
devient
(++)
/ \
a stuff
et tous les éléments de l' a peut être obtenu en une seule étape. Dans cet exemple, où nous avons eu pur gauche de la nidification, une seule réécriture est nécessaire. Si, au lieu de (par exemple) (d ++) la fonction, dans ce lieu avait été de gauche de la composition imbriquée, (((g ++) . (h ++)) . (i ++)) . (j ++), le niveau supérieur de la réassociation laisserait qui intacte et ce serait réassociées quand il devient l'opérande de gauche de haut-niveau ($) après toutes les listes précédentes ont été consommés.
Le travail total nécessaire pour toutes les reassociations est - O(number of lists), de sorte que le coût global pour la concaténation est - O(number of lists + sum (map length lists)). (Cela signifie que vous pouvez apporter de mauvaises performances dans ce domaine aussi, par l'insertion d'un lot de profondément de gauche imbriquée ([] ++).)
L'
newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }
instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
juste enveloppe de sorte qu'il est plus facile à manipuler de façon abstraite.
DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++))
Notez qu'il est efficace uniquement pour les fonctions qui n'ont pas besoin de vérifier leur argument de commencer à produire de sortie, si des fonctions arbitraires sont enveloppés dans DiffLists, vous n'avez pas une telle efficacité des garanties. En particulier, l'ajout d'une ((++ a), enveloppé ou non) peut créer de gauche imbriqués les arbres de (++) lorsque l'on compose à droite-imbriquées, de sorte que vous pouvez créer l' O(n²) de concaténation de comportement que si l' DiffList constructeur est exposée.
