3

Sou novo em programação em Haskell, e queria saber uma maneira de pegar o primeiro item de cada lista e botar em uma lista, depois com o segundo, depois com o terceiro e por aí vai... Um exemplo seria mais ou menos o seguinte:

Input: [[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]. 
Output: [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]. 

Sendo que não posso importar nada, só podendo usar o que tem no Prelude, procurei bastante na internet e até achei uma função que pegasse o primeiro item de cada lista, mas não era o suficiente para o problema.

1 Resposta 1

3

É possível criar uma função assim usando funções mais gerais, como map, fst, snd e splitAt, todas continas no Prelude.

primeiros :: [[a]] -> [[a]]
primeiros xs = helper1 ([], xs)

helper1 :: ([[a]],[[a]]) -> [[a]]
helper1 (hs, []) = hs
helper1 (hs, ls) = helper1 ((f2 . f1 $ ls) : hs, checaNull (f3 . f1 $ ls))
  where f1 y = map (splitAt 1) y
        f2 y = concat $ map fst y
        f3 y = map snd y
        checaNull [] = []
        checaNull ls@(x:xs) = if not (null x) then ls else checaNull xs

Esta é uma implementação simples, mas bastante ineficiente. É ineficiente porque

  • a cada vez que helper1 é chamada, a lista é percorrida duas vezes: uma vez em f2 . f1 $ ls e outra em f3 . f1 $ ls.
  • quanto maior for a lista de entrada, maior o tempo consumido por f2 devido a concat.

O resultado também sai um pouco diferente. Mudei o exemplo para mostrar a diferença:

*Main> lista = [[1,10,100,1000],[2,20,200,2000,2],[3,30,300,3000],[4,40,400,4000,4]]
*Main> primeiros lista
[[2,4],[1000,2000,3000,4000],[100,200,300,400],[10,20,30,40],[1,2,3,4]]

Se quiser inverter a ordem de saída, basta escrever helper1 (hs, []) = reverse hs como o primeiro padrão de helper1, o que aumenta o tempo de processamento, porque vai precisar percorrer toda a lista de saída.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .