Implementar zip usando foldr

StackOverflow https://stackoverflow.com/questions/235148

Pergunta

Atualmente estou no capítulo 4 do Real World Haskell, e eu estou tentando envolver minha cabeça em torno de implementação foldl em termos de foldr .

(Aqui está o seu código:) 

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Eu pensei em tentar implementar zip usando a mesma técnica, mas eu não parecem estar fazendo algum progresso. Será que é mesmo possível?

Foi útil?

Solução 

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

Como isso funciona: (passo foldr xs feito) retorna uma função que consome ys; assim que nós vamos para baixo na lista xs construção de uma composição aninhada de funções que cada um deles será aplicada à parte correspondente do ys.

Como chegar a ele: Eu comecei com a idéia geral (de semelhante exemplos visto antes), escreveu 

zip2 xs ys = foldr step done xs ys

, em seguida, preenchido em cada uma das seguintes linhas, por sua vez, com o que tinha a ser para fazer os tipos e valores saem direito. Era mais fácil de considerar os casos mais simples antes de as mais difíceis.

A primeira linha poderia ser escrito mais simplesmente como 

zip2 = foldr step done

como mattiast mostrou.

Outras dicas

A resposta já tinha sido dada aqui, mas não uma derivação (ilustrativa). Assim, mesmo depois de todos esses anos, talvez vale a pena adicioná-lo.

É realmente muito simples. Primeiro, 

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))

, portanto, por eta-expansão, 

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys

Como é evidente aqui, se f é não forçar na sua 2ª argumento , ele começa a trabalhar início em x1 e ys, f x1 r1 ys onde r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr f z [x2,x3,...,xn].

Assim, usando 

f x1 r1 [] = []
f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1

nós arranjamos para a passagem de informações da esquerda para a direita ao longo da lista, por chamando r1 com o descansar da lista de entrada ys1, foldr f z [x2,x3,...,xn] ys1 = f x2 r2 ys1, como o próximo passo. E é isso.

Quando ys é mais curto do que xs (ou o mesmo comprimento), o caso [] para incêndios f e o processamento pára. Mas se ys é maior do que xs seguida, caso f de [] não fogo e nós vamos chegar ao f xn final z aplicação (yn:ysn), 

f xn z (yn:ysn) = (xn,yn) : z ysn

Uma vez que chegamos ao final de xs, o zip processamento de parada obrigatória: 

z _ = []

E isso significa que o z = const [] definição deve ser usado: 

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Do ponto de vista f, r desempenha o papel de um continuação sucesso , que f chamadas quando o processamento é para continuar, depois de ter emitido o (x,y) par.

Assim r é "o que é feito com mais ys quando há mais xs" , e z = const [], o nil -Case em foldr, é "o que é feito com ys quando não há mais xs ". Ou f pode parar por si só, retornando [] quando ys está esgotado.

Observe como ys é usado como um tipo de valor acumulando, que é passado da esquerda para a direita ao longo da lista xs, de uma invocação de f para o próximo ( "acumular" ser passo, aqui, tirando um elemento cabeça dele ).

Naturalmente Isto corresponde à esquerda dobra, onde um passo de acumulação é "aplicar a função", com z = id retornando o valor final acumulada quando "não há mais xs": 

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

Da mesma forma, para as listas finitas, 

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

E uma vez que a função combinando começa a decidir se quer continuar ou não, agora é possível ter esquerdo dobrar que podem parar mais cedo: 

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

ou um pular esquerda dobra, foldlWhen t ..., com 

    cons x r a = if t x then r (f a x) else r a

etc.

Eu encontrei uma maneira usando método bastante semelhante à sua: 

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Para os Haskellers não-nativos aqui, eu escrevi uma versão Esquema deste algoritmo para tornar mais claro o que está realmente acontecendo: 

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

Os resultados foldr em uma função que, quando aplicado a uma lista, irá devolver o fecho de correr da lista dobrada com a lista dada para a função. O Haskell esconde a lambda interna por causa da avaliação preguiçosa.

Para quebrá-lo ainda mais para baixo:

Tome zip na entrada: '(1 2 3) A func foldr é chamado com 

el->3, func->(lambda (a) empty)

Isso expande para: 

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

Se tivéssemos que voltar isto agora, nós teríamos uma função que leva uma lista de um elemento e retorna o par (3 elemento): 

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

Continuada, foldr agora chama func com 

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

Esta é uma func que leva uma lista com dois elementos, agora, e fecha-los com (list 2 3): 

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

O que está acontecendo? 

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a, neste caso, é (list 9 1) 

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

E, como você se lembra, f fecha seu argumento com 3.

E este continua etc ...

O problema com todas estas soluções para zip é que eles só dobre uma lista ou de outra, o que pode ser um problema se ambos são "bons produtores", na linguagem de fusão lista. O que você realmente precisa é uma solução que se dobra em ambas as listas. Felizmente, há um artigo sobre exatamente isso, chamado "Coroutining Folds com Hyperfunctions" .

Você precisa de um tipo auxiliar, uma hiperfunção, que é basicamente uma função que toma outra hiperfunção como seu argumento. 

newtype H a b = H { invoke :: H b a -> b }

Os hyperfunctions usadas aqui, basicamente, agir como uma "pilha" de funções comuns. 

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

Você também precisa encontrar uma maneira de colocar dois hyperfunctions juntos, de ponta a ponta. 

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

Isto está relacionado com push pela lei: 

(push f x) .#. (push g y) = push (f . g) (x .#. y)

Este acaba por ser um operador associativo, e esta é a identidade: 

self :: H a a
self = H $ \k -> invoke k self

Você também precisa de algo que desconsidera tudo na "pilha" e retorna um valor específico: 

base :: b -> H a b
base b = H $ const b

E, finalmente, você precisa de uma maneira de obter um valor fora de uma hiperfunção: 

run :: H a a -> a
run q = invoke q self

run cordas todas as funções pushed juntos, ponta a ponta, até que ela atinge um base ou loops infinitamente.

Então, agora você pode dobrar ambas as listas em hyperfunctions, usando funções que passam informações de um para o outro, e montar o valor final. 

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

A razão pela qual dobrando tanto em matéria listas é por causa de algo GHC faz chamado lista de fusão , que é falado em o GHC.Base módulo , mas provavelmente deve ser muito mais bem conhecido. Sendo um produtor boa lista e usando build com foldr pode evitar muita produção inútil e consumo imediato de elementos da lista, e pode expor ainda mais otimizações.

Eu tentei entender esta solução elegante mim mesmo, então eu tentei obter os tipos e avaliação de mim mesmo. Então, precisamos escrever uma função: 

zip xs ys = foldr step done xs ys

Aqui precisamos step derive e done, sejam eles quais forem. Lembre foldr 's digita, instanciado para listas: 

foldr :: (a -> state -> state) -> state -> [a] -> state

No entanto a nossa invocação foldr deve ser instanciado para algo como abaixo, porque temos de aceitar não um, mas dois argumentos da lista: 

foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]

Porque -> é direito associativo , isso é equivalente a: 

foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])

Nossos corresponde ([b] -> [(a,b)]) para tipo state variável na assinatura de tipo foldr original, portanto, temos de substituir todas as ocorrências de state com ele: 

foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
      -> ([b] -> [(a,b)])
      -> [a]
      -> ([b] -> [(a,b)])

Isto significa que os argumentos que passamos para foldr deve ter os seguintes tipos: 

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

Lembre-se que foldr (+) 0 [1,2,3] expande para: 

1 + (2 + (3 + 0))

Portanto, se xs = [1,2,3] e ys = [4,5,6,7], nossa invocação foldr se expandiria para: 

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

Isto significa que nossa construção 1 `step` (2 `step` (3 `step` done)) deve criar uma função recursiva que iria passar por [4,5,6,7] e fechar acima dos elementos. (Tenha em mente que, se uma das listas originais é mais longo, os valores em excesso são jogados fora). IOW, nossa construção deve ter o tipo [b] -> [(a,b)].

3 `step` done é o nosso caso base, onde done é um valor inicial, como 0 em foldr (+) 0 [1..3]. Nós não queremos zip nada depois de 3, pois 3 é o valor final de xs, por isso temos de terminar a recursão. Como você terminar a recursão sobre lista no caso base? Você retorna vazio lista []. Mas tipo de recordação done assinatura: 

done :: [b] -> [(a,b)]

Portanto, não podemos retornar apenas [], devemos retornar uma função que iria ignorar tudo o que recebe. Portanto, use const : 

done = const [] -- this is equivalent to done = \_ -> []

Agora vamos começar a descobrir o que step deve ser. Ele combina um valor do tipo a com uma função do tipo [b] -> [(a,b)] e retorna uma função do tipo [b] -> [(a,b)].

Em 3 `step` done, sabemos que o valor do resultado que mais tarde viria a nossa lista zipado deve ser (3,6) (sabendo de xs original e ys). Portanto 3 `step` done deve avaliar em: 

\(y:ys) -> (3,y) : done ys

Lembre-se, temos de voltar uma função, dentro do qual temos alguma forma fechar acima dos elementos, o código acima é o que faz sentido e typechecks.

Agora que nós assumimos como exatamente step deve avaliar, vamos continuar a avaliação. Veja como todas as medidas de redução do nosso foldr olhar de avaliação como: 

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

A avaliação dá origem a esta implementação da etapa (note que representam ys a esgotar-se de elementos cedo, retornando uma lista vazia): 

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

Assim, o zip função completa é implementada da seguinte forma: 

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

PS: Se você está inspirado pela elegância de dobras, leia Escrevendo foldl usando foldr e, em seguida, Graham Hutton do Um tutorial sobre a universalidade ea expressividade das vezes .

Uma abordagem simples: 

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top