Alguém poderia explicar essas funções Haskell para mim?

Question

Eu tenho dividido com Haskell no passado, e recentemente voltou para a sério, e eu estou lendo haskell mundo real. Alguns dos exemplos que eles brilhou, eu ainda não entendo. Tal para este:

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Eu não vejo como isso funciona, o que é uma verdade que está sendo adicionado também? Como é a recursão retornar algo que pode ser adicionado a? Eu não obtê-lo.

E aqui temos esta:

splitLines [] = []
splitLines cs =
       let (pre, suf) = break isLineTerminator cs
       in  pre : case suf of 
                   ('\r':'\n':rest) -> splitLines rest
                   ('\r':rest)      -> splitLines rest
                   ('\n':rest)      -> splitLines rest
                   _                -> []

isLineTerminator c = c == '\r' || c == '\n'

Como isso funciona, o que é pré realmente estar ligado também? Eu não ver como o resultado da expressão case é algo que pre podem ser concatenados para. Talvez eu só preciso de alguém para explicar a avaliação dessas funções em detalhes. Devo estar faltando alguma coisa muito importante.

Agradecemos antecipadamente!

EDIT: Eu sei, foi um copy-paste falhar. Desculpe.

EDIT 2: Parece que minha confusão era com o que essas funções eram realmente / retorno / Eu tenho tudo planejado agora. Graças para os caras respostas, finalmente clicado! Eu aprecio isso!

Answer 1

Quanto ao primeiro, que é uma maneira muito básica de recursão. No entanto, parece estar faltando uma parte:

myLength [] = 0

Ele funciona por escamação fora um elemento no momento da lista e adicionando um ao resultado. Para visualizar, considere a chamada

myLength [1,2,3]

que irá avaliar a:

1 + myLength [2,3]
1 + 1 + myLength [3]
1 + 1 + 1 + myLength []
1 + 1 + 1 + 0

que é 3.

Quanto ao segundo, bem, você já dividir a seqüência na próxima quebra de linha em duas partes: pré e suf. Agora, suf vai começar com qualquer um \ n ou um \ r, ou a \ r \ n. Queremos remover estes. Então, nós usamos correspondência padrão. Veja como a variável resto é essencialmente a variável suf menos a linha inicial pausa personagem (s).

Portanto, temos pré, que é a primeira linha, e descansar, que é o resto do texto. Portanto, a fim de continuar resto dividindo em linhas chamamos splitLines sobre ele de forma recursiva e concatenar o resultado para pré.

Para visualizar, dizer que você tem a string "foo \ NBAR \ r \ nbaz".

Assim, quando chamado, o resultado será:

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ]
foo : splitLines bar\r\nbaz

então splitLines é chamado novamente, eo resultado é expandido em:

[ pre => bar, suf => \r\nbaz, rest = baz ]
foo : bar : splitLines baz

, em seguida, mais uma vez:

[ pre => baz, suf => [], rest = [] ]
foo : bar : baz

que é o resultado final.

Answer 2

Eu acho que a definição de myLength perde o caso em que a lista está vazia:

myLength [] = 0
myLength (x:xs) = 1 + myLength (xs)

Com esta definição, o myLength de uma lista vazia é 0. O (x:xs) Desembala Patten uma lista para o primeiro item, a, e uma lista com o resto dos itens, xs. Se a lista tem um item, em seguida, xs é uma lista vazia, então o resultado é 1 + 0. E assim por diante.

A recursão é mais fácil de entender quando você olha para o caso base em primeiro lugar, e depois ver como cada nível de recursividade se baseia no resultado. (O caso base é o caso em que a função não chamar a si mesma. Se uma função recursiva não tem um caso base, a saída será infinito.)

No segundo exemplo, o caso de base (no último caso, no caso-statment) é também uma lista vazia. Assim pré serão sempre acrescentados a uma lista, que irá produzir um novo, lista, mais tempo.

Answer 3

Re: myLength (x:xs) = 1 + myLength (xs) - este é "metade" da definição de myLength, diz, por correspondência de padrões, que se o argumento tem uma cabeça e uma cauda, ??então o resultado é mais uma que a chamada cauda recursiva na cauda - é preciso haver outra metade para dizer que o resultado é 0 quando o argumento não pode igualar x:xs, ou seja, quando o argumento é uma lista vazia

.

No segundo caso, a possibilidade de diferentes padrões de correspondência é feito apenas um pouco mais epxlicit via case.

BTW, a preguiça não é uma questão-chave aqui - ML, com avaliação ansiosa, mas a correspondência de padrão muito parecido com Haskell, iria trabalhar de forma muito semelhante. Looks como correspondência de padrão é o que você realmente precisa retocar sobre.

Answer 4

Em primeiro lugar o primeiro exemplo deveria ser assim ( Editar: parece que você fixa-lo agora):

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Ele funciona assim: dizer que eu dar-lhe uma lista com três itens, ele retorna um mais o comprimento da cauda (que é um mais o comprimento da cauda (que é um mais o comprimento da cauda, ??(que é [] neste ponto), o qual é 1), que é w), que é 3 (a resposta final). Talvez parênteses aninhados irá ajudá-lo a compreendê-lo. ; -)

Answer 5

É instrutivo olhar para o que as assinaturas de tipo de funções seria. Eles podem ser:

myLength :: [a] -> Int

myLength, uma está a ser adicionado ao resultado da chamada recursiva para myLength, que é um Int, que por sua vez resulta em um Int.

splitLines :: [Char] -> [[Char]]

Em splitLines, pre (a [Char]) está sendo anexado ao resultado da instrução caso, que, de olhar para os casos, ou é o resultado de uma chamada recursiva para splitLines, que é [[Char]]; ou uma lista vazia. Em ambos os casos, antecedendo pre (a [Char]) irá resultar em uma [[Char]] por sua vez.