Preciso entender como a Haskell representa dados para poder escrever bons programas Haskell?

Question

Estou aprendendo Haskell com um histórico de Java. Quando programo o Java, sinto que tenho um forte entendimento de como os objetos são dispostos na memória e as consequências disso. Por exemplo, eu sei exatamente como java.lang.String e java.util.LinkedList trabalho e, portanto, sei como devo usá -los. Com Haskell, estou um pouco perdido. Por exemplo, como (:) trabalhar? Devo me importar? Está especificado em algum lugar?

Answer 1

A resposta curta é não. Ao programar em Haskell, você deve pensar em suas estruturas de dados como objetos matemáticos puros e não se preocupar com a forma como eles são representados na memória. A razão para isso é que, na ausência de efeitos colaterais, não há realmente nada para Dados, exceto as funções que o criam e as funções que você pode usar para extrair as partes mais simples das quais foram construídas.

Para ver informações sobre construtores de dados como (:), ou qualquer outro termos, use o :type (ou apenas :t Para abreviar) comando dentro de ghci:

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

Que diz que o (:) Construtor (pronunciado "contras"), pega um valor de qualquer tipo e uma lista do mesmo tipo e retorna uma lista do mesmo tipo. Você também pode obter um pouco mais de informação usando o :info comando. Isso mostrará como é a definição de dados:

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

Isso diz isso (:) é o construtor que antecende um elemento para uma lista existente.

Eu também recomendo Hoogle não apenas por procurar as coisas pelo nome, mas por fazer o tipo reverso de pesquisa; Onde você conhece a assinatura da função que está procurando e deseja descobrir se alguém já o escreveu para você. Hoogle é bom porque fornece descrições e usos de exemplo.

Formas de dados indutivos

Eu disse acima que não é importante conhecer a representação de seus dados na memória ... você deve, no entanto, entender o forma dos dados com os quais você está lidando, para evitar decisões de desempenho inadequadas. Todos os dados em Haskell são indutivamente definidos, o que significa que possui uma forma semelhante a uma árvore que se desenrola sempre para externamente. Você pode dizer a forma dos dados observando sua definição; Não há realmente nada escondido em suas características de desempenho depois de saber como ler isso:

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

Como você pode ver na definição, a única maneira de obter um novo MyList é pelo Cons construtor. Se você usar este construtor várias vezes, acabará com algo aproximadamente dessa forma:

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

É apenas uma árvore sem galhos, essa é a definição de uma lista! E a única maneira de chegar a1 é sair de cada um dos Consestá por sua vez; Portanto, o acesso ao último elemento é Sobre), enquanto o acesso à cabeça é um tempo constante. Depois de fazer esse tipo de raciocínio sobre estruturas de dados com base em suas definições, você está definido.

Answer 2

A resposta curta é "não", você não precisa saber sobre os layouts de dados - um conhecimento de complexidade será útil.

Para escrever programas Haskell altamente otimizados, é essencial um bom conhecimento de trabalho da forma das estruturas de dados na pilha. Uma ferramenta para ajudar isso é "vácuo", que podem renderizar diagramas de estruturas de dados Haskell à medida que são dispostas.

Alguns exemplos:

$ view "hello"

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

Aqui está um pequeno vídeo de como usar a ferramenta: http://www.youtube.com/watch?v=x4-212umgy8