Ai-je besoin de comprendre comment Haskell représente les données pour être en mesure d'écrire de bons programmes Haskell?

Question

J'apprends Haskell à partir d'un langage Java. Lorsque je programme Java, je me sens comme je l'ai une bonne compréhension de la façon dont sont disposées en mémoire et les conséquences de cette objets. Par exemple, je sais exactement comment java.lang.String et le travail de java.util.LinkedList et donc je sais comment je devrais les utiliser. Avec Haskell, je suis un peu perdu. Par exemple, comment fonctionne-t-(:)? Je dois prendre soin? Est-il spécifié quelque part?

Answer 1

La réponse courte est non. Lors de la programmation en Haskell, vous devriez penser à vos structures de données comme des objets mathématiques pures et ne pas se soucier de la façon dont ils sont représentés dans la mémoire. La raison en est que, en l'absence d'effets secondaires, il n'y a vraiment rien données à l'exception des fonctions qui le créent et les fonctions que vous pouvez utiliser pour extraire les parties plus simples à partir de laquelle il a été construit .

Pour voir les informations sur les constructeurs de données comme (:), ou toute autre condition, utilisez le :type (ou tout simplement :t pour faire court) commande à l'intérieur GHCi:

:Prelude> :type (:)
(:) :: a -> [a] -> [a]

Que vous dit que le constructeur de (:) (prononcé « contre »), prend une valeur de tout type, et une liste du même type, et retourne une liste du même type. Vous pouvez également obtenir un peu plus d'informations en utilisant la commande :info. Cela va vous montrer ce que les regards de définition de données telles que:

Prelude> :info (:)
data [] a = ... | a : [a]   -- Defined in GHC.Types
infixr 5 :

Cela vous dit que (:) est le constructeur qui prepends un élément à une liste existante.

Je recommande également très Hoogle non seulement pour rechercher des choses par leur nom, mais pour faire le genre inverse de la recherche; où vous connaissez la signature de la fonction que vous recherchez et que vous voulez trouver si quelqu'un il est déjà écrit pour vous. Hoogle est agréable car elle donne des descriptions et des usages par exemple.

Formes de inductives

je l'ai dit plus haut qu'il est important de ne pas connaître la représentation de vos données en mémoire ... vous devriez cependant comprendre la forme des données que vous avez affaire, pour éviter de mauvaises performances les décisions. Toutes les données dans Haskell est définie inductivement, ce qui signifie qu'il a une forme semblable à arbre qui se déroule toujours vers l'extérieur récursive. Vous pouvez dire à la forme de données en regardant sa définition; il n'y a vraiment rien de caché sur ses caractéristiques de performance une fois que vous savez lire ceci:

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

Comme vous pouvez le voir dans la définition, la seule façon que vous pouvez obtenir une nouvelle MyList est par le constructeur de Cons. Si vous utilisez plusieurs fois ce constructeur, vous finirez avec quelque chose à peu près de cette forme:

(Cons a5 (Cons a4 (Cons a3 (Cons a2 (Cons a1 Nil)))))

Il est juste un arbre sans branches, c'est la définition d'une liste! Et la seule façon d'obtenir à a1 est en sautaient chacun des Conss à son tour; par conséquent, l'accès au dernier élément est O (n) , tandis que l'accès à la tête est la constante de temps. Une fois que vous pouvez faire ce genre de raisonnement sur les structures de données en fonction de leurs définitions, vous êtes tous ensemble.

Answer 2

Réponse courte est « non », vous ne devez savoir sur les présentations de données -. Une connaissance de la complexité sera utile si

Pour écrire des programmes Haskell hautement optimisés, une bonne connaissance pratique de la forme des structures de données dans le tas est essentiel, cependant. Un outil pour aider c'est « vide » , ce qui peut rendre des diagrammes de structures de données Haskell comme ils sont disposés.

Voici quelques exemples:

$ view "hello"

$ view (IntMap.fromList $ zip [1..10] [1..])

Voici une courte vidéo de la façon d'utiliser l'outil: http: // www. youtube.com/watch?v=X4-212uMgy8