Haskell (:) et (++) différences

Je suis désolé pour une question comme ça. Je ne suis pas trop sûr au sujet de la différence de la : et ++ opérateur en Haskell.

x:y:[] = [x,y]

aussi 

[x] ++ [y] = [x,y]

comme pour la fonction d'inversion qui se pose cette question, pour moi,

reverse ::[a]->[a]
reverse [] = []
reverse (x:xs) = reverse(xs)++[x]

Pourquoi ne pas les travaux suivants?

reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

donnant une erreur de type.

  • Comme une note de côté, vous pouvez (et devriez) appel sans utiliser de parenthèses: reverse (x:xs) = reverse xs ++ [x], ou vous allez trébucher lorsque vous travaillez avec des fonctions à plusieurs arguments.
  • Ne pas appeler des fonctions comme func(arg). Pauvre Haskell. Toujours faire appel à des fonctions comme func arg. Code avec claire des espaces rend plus confiant et plus lisible le code.
  • func arg est en effet plus correct Haskell que func(arg) mais je dirais f(x) est plus lisible que f x en général car elle correspond à la majorité des autres langues, et aussi la manière mathématique de la spécification d'une fonction. Donc, je dirais "plus confiant et plus lisible" est une question d'opinion.
InformationsquelleAutor DarthVader | 2009-11-30
  1. 69

    La : opérateur est connu comme le "contre" de l'opérateur et est utilisé pour ajouter un élément de tête de une liste. Donc [] une liste et x:[] est préfixant x à la liste vide faire la liste [x]. Ensuite, si vous le contre y:[x] vous vous retrouvez avec la liste [y, x] qui est le même que y:x:[].

    La ++ opérateur est la liste de l'opérateur de concaténation qui prend deux listes d'opérandes et "combiner" en une seule liste. Donc, si vous avez la liste [x] et la liste [y] vous pouvez concaténer comme ceci: [x]++[y] pour obtenir [x, y].

    Avis que : prend un élément et une liste de tout ++ prend deux listes.

    Que de votre code qui ne fonctionne pas.

    reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]

    L'inverse de la fonction renvoie une liste. Depuis le : opérateur ne prend pas une liste comme premier argument et puis reverse(xs):x est pas valide. Mais reverse(xs)++[x] est valide.

    InformationsquelleAutor Vincent Ramdhanie
  2. 20

    : conses un élément à une liste.

    ++ ajoute deux listes.

    L'ancien a type

    a -> [a] -> [a]

    tandis que le second est de type

    [a] -> [a] -> [a]
    • Pour le Lisp-vocabulaire-remise en cause, les "contre" construit une nouvelle liste de nœud et l'ajoute à la tête de la liste.
    InformationsquelleAutor Brian
  3. 11

    Concaténation (++)

    Peut-être que je pense profondément dans cette mais,
    comme je le comprends, si vous essayez de concaténer
    les listes à l'aide de (++) par exemple:

    [1, 2, 3] ++ [4, 5]

    (++) est de parcourir compléter la liste de gauche.
    En prenant un coup d'oeil à la code de l' (++) rend
    d'autant plus clair.

    (++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

    Ainsi, il serait souhaitable d'éviter d'utiliser (++), car à chaque appel
    reverse(xs)++[x] la liste devient de plus (ou moins, selon
    sur le point de vue. De toute façon, le programme n'a qu'à traverser un autre
    liste à chaque appel)

    Exemple:

    Permet de dire que je les mettre en œuvre inverse, comme proposé par concaténation.

    reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]

    L'inversion d'une liste [1, 2, 3, 4] devrait ressembler à quelque chose comme ceci:

    reversex [1, 2, 3, 4]
reversex [2, 3, 4]               ++ [1]
reversex [3, 4]           ++ [2] ++ [1]
reversex [4]       ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
         [] ++ [4] ++ [3] ++ [2] ++ [1]
         [4]       ++ [3] ++ [2] ++ [1]
         [4, 3]           ++ [2] ++ [1]
         [4, 3, 2]               ++ [1]
         [4, 3, 2, 1]

    Queue de la Récursivité à l'aide de l'opérateur cons (:)!!!

    Une méthode pour traiter les piles d'appels est par l'ajout d'une accumulateur.
    (il n'est pas toujours possible d'ajouter simplement un accumulateur. Mais la plupart de la
    fonctions récursives on traite sont primitive récursive et peut donc
    être transformé en queue de fonctions récursives.)

    Avec l'aide de l'accumulateur, il est possible de faire de cet exemple
    travail, à l'aide de l'opérateur cons (:).
    L'accumulateur -- ys dans mon exemple, il s'accumule le résultat courant et est transmis en tant que paramètre. En raison de l'accumulateur nous sommes maintenant en mesure
    pour utiliser le contre opérateur à accumuler le résultat en ajoutant le
    à la tête de notre liste initiale à chaque fois.

    reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys     = ys

    Il y a une chose à noter ici.

    L'accumulateur est un argument supplémentaire. Je ne sais pas si Haskell
    fournit les paramètres par défaut, mais dans ce cas, il serait bien,
    parce que vous serait toujours appeler cette fonction avec une liste vide
    comme l'accumulateur comme suit: reverse' [1, 2, 3, 4] []

    Il y a beaucoup de littérature sur la queue de la récursivité et je suis
    certes, il y a beaucoup de questions similaires sur
    StackExchange /StackOverflow. Veuillez me corriger si vous trouvez des erreurs.

    Salutations,

    EDIT 1:

    Sera Ness souligné quelques-uns des liens vers de bonnes réponses pour ceux d'entre vous qui sont intéressés:

    EDIT 2:

    Ok.
    Grâce à dFeuer et de ses corrections, je crois que je comprends Haskell
    un peu mieux.

    1.Le $! est au-delà de ma compréhension. Dans tous mes tests, il semble
    faire empirer les choses.

    2.Comme dFeuer a souligné:
    Le thunk représentant l'application de (:) à x et y est sémantiquement identique à x:y mais prend plus de mémoire. Donc, c'est spécial pour l'opérateur cons
    (et paresseux constructeurs) et il n'est pas nécessaire de forcer les choses en aucune façon.

    3.Si j'ai plutôt sumUp Entiers d'une liste à l'aide d'une très fonction similaire,
    une évaluation rigoureuse par BangPatterns ou la seq fonction
    va empêcher la pile de la croissance de la trop grande si elle est utilisée de manière appropriée. par exemple:

    sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y      = y

    Avis le bang en face de y. Je l'ai essayé dans ghci et il
    prend moins de mémoire.

    • Haskell jamais paresseusement les retards de l'application d'un paresseux constructeur (car il n'y a jamais aucun avantage à le faire), donc il n'y a pas de besoin, et pas d'avantage, pour forcer ces résultats manuellement. Vous pouvez même finir par ralentir les choses en forçant les choses qui sont déjà évalués!
    • Je ne suis pas trop sûr de Haskell en termes de rigueur. wiki.haskell.org/Performance/Accumulating_parameter bien que ne suggèrent que l'on devrait envisager l'utilisation de l'évaluation stricte de l'accumulateur: "Nous avons besoin de résoudre un petit problème en ce qui concerne le dépassement de pile. La fonction s'accumulent (1 + acc) thunks que nous passons en bas de la liste. En général, il est logique de faire de votre accumulateur paramètres strict, puisque sa valeur sera nécessaire à la fin."
    • GHC généralement des retards fonction de l'application et de la correspondance de modèle, mais pas paresseux constructeur de l'application. La raison en est que thunk représentant l'application de (:) à x et y est sémantiquement identique à x:y mais prend plus de mémoire. Les constructeurs sont spéciales. Stricte les constructeurs ne sont pas si spécial.
    • Ok... je suis confus ici. Pouvez-vous fournir une source à lire sur le sujet? Autant je comprends Haskell est non-strictes et ne serait pas évaluer les arguments passés... ou est-ce GHC spécifiques.
    • Il est GHC spécifique, mais je m'attends à la même chose de grave Haskell mise en œuvre. L'application d'un constructeur ne fait pas de calculer quoi que ce soit. Ni x ni y doit être évaluée afin d'obtenir x:y.
    • Donc, vous dites que tous les $! ne est la force paresseux constructeur d'application?
    • Pas en général, non. Prenons un peu de recul. Jusqu'à ce que vous obtenez à micro-optimisation, vous avez seulement besoin de s'inquiéter à propos de les thunks "pile" en face d'une valeur. C'est ce qui peut arriver avec foldl (+) sans optimisation--vous obtenez un résultat qui est une grande chaîne de thunks vous avez besoin de force pour arriver à la somme. Avec reverse, le pire que vous pourriez jamais obtenir serait thunk-cons-thunk-cons.... C'est un assez bon résultat sur son propre!
    • Mais le point que je faisais avant, c'est que si je l'appelle f (g x y) généralement, GHC permettra de créer un thunk représentant g x y et de thunk pour f. Mais si g est un paresseux constructeur (c'est à dire, un constructeur dont la définition n'utilise pas !), GHC s'appliquent g directement, et de transmettre le résultat à f. La sémantique est identique, mais il est plus rapide et permet d'économiser la mémoire.
    • avez-vous vu stackoverflow.com/questions/13879260/..., stackoverflow.com/questions/14938584/..., etc.?
    • Je n'ai pas. Mais ce sont vraiment de bonnes réponses. Thx
    • un autre est stackoverflow.com/questions/13042353/..., à environ $! etc. --- pour vraiment tester la consommation de mémoire, de compiler avec -O2 et test d'exécuter le fichier exécutable autonome, toujours (comme appname +RTS -s).
    • J'aime qu'en Haskell c'est tellement naturel pour pointer vers le code source de la ++ fonction, il est rare que vous verriez qu'avec d'autres langues, à mon avis, par exemple, je n'ai jamais pensé à regarder à l'intérieur de la définition de concat en JavaScript ou vu quelqu'un ou quelque JS livres jamais vous recommandons de vous renseigner à la source

    InformationsquelleAutor Nima Mousavi
  4. 3

    cons a tendance à être un constructeur de type de l'exploitant. l'exemple ici est : peut être utilisé dans de let..in.. expresion mais ++ n'est pas

    let x : xs = [1, 2, 3] in x -- known as type deconstructing

    sera de retour 1 mais

    let [x] ++ [y, z] = [1, 2, 3] in x

    retournera une erreur Variable not in scope x

    Pour le rendre facile, pensez à cons comme ce

    data List a = Cons a (List a) -- is equvalent with `data [a] = a:[a]`

    https://en.wikibooks.org/wiki/Haskell/Other_data_structures

    En outre, si vous souhaitez inverser un tableau à l'aide des inconvénients. Voici un exemple, la connaissance est pris de Prolog

    import Data.Function

reversex1 [] = []
reversex1 arr = reversex arr []

reversex [] arr = arr
reversex (x:xs) ys = reversex xs (x:ys)

main = do
    reversex1 [1..10] & print
    InformationsquelleAutor Clite Tailor