Será esta uma maneira correta de escrever a função foldr Haskell?

Question

Eu estava fazendo os exercícios da seção de yaht recursiva tipo de dados , e encontrou escrevendo a função listFoldr um pouco difícil (principalmente porque eu realmente não entendo a diferença entre foldl e foldr em primeiro lugar). Quando eu finalmente percebi exatamente como a função foldr trabalhado, decidi que uma simples troca de argumentos da função seria tudo o que seria necessário para mudar minha função listFoldl para uma função listFoldr:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

Esta parece trabalho (eu fiz mais testes do que isso):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

Mas a solução dada para o exercício é muito diferente da minha. Sua listFoldl é exatamente a mesma que a minha, mas olhar para o seu listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Qual a solução melhor, a minha ou a deles? É um deles incorreta? (Em meus testes, ambos acabam com o mesmo resultado ...)

Answer 1

Eu acho que você está processando os elementos da 'ordem oposta', e assim o seu não está certo.

Você deve ser capaz de demonstrar isso com um exemplo onde 'questões de ordem'. Por exemplo, algo como

listfoldr f "" ["a", "b", "c"]

em que 'f' é uma função ao longo das linhas de

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

onde '@' é um operador de corda-de acréscimo (I esquecer o que está em Haskell). O ponto é apenas para 'instrumento' a função para que você possa ver o que encomendá-lo está sendo chamado com os vários argumentos.

(Note que este não apareceu no seu exemplo, porque a matemática "4-1-2-3" yields a mesma resposta como "4-3-2-1".)

Answer 2

A sua solução é definitivamente incorreto. Você simplesmente implementou um foldl em que a função f leva argumentos na ordem inversa. Por exemplo do que está errado, foldr (:) [] é suposto ser uma função de identificar em listas, mas a sua função inverte a lista. Há muitas outras razões pelas quais a sua função não é foldr, como a forma como foldr funciona em listas infinitas e seu não. É pura coincidência que eles são o mesmo no seu exemplo, porque 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). Eu acho que você deve começar a partir do zero e olhar como foldr é suposto trabalho.

Answer 3

O seu é quebrado. Experimente-o com algo que não acabar com um único resultado numérico.

eg: listFoldr (++) "a" ["b", "c", "d"]

Você está processando na direção errada.

Answer 4

Em uma lista [x1, x2, ..., xk], seu listFoldr calcula

 f xk (... (f x2 (f x1 i)) ...)

enquanto foldr deve calcular

 f x1 (f x2 (... (f xk i) ...))

(Em comparação, foldl calcula

f (... (f (f i x1) x2) ...) xk

Essencialmente, listFoldr f = foldl (flip f).)

Você é um caso de teste é lamentável, porque

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

Quando você está testando funções como estes, não deixe de passar em uma f que é não-comutativa e não associativa (ou seja, o argumento e ordem de aplicação matéria), assim você pode ter certeza de que a expressão é avaliada corretamente. Claro, subtração é não-comutativa e não associativo e você acabou azarão.