Lavorare su un elenco di elenchi in Haskell

Question

Sono un po 'un principiante di Haskell, quindi sto lottando un po' con le cose di tipo rigoroso, mi chiedo solo se qualcuno può aiutarmi con una funzione che sto cercando di costruire . Fondamentalmente, ci vuole un elenco di liste, ad esempio:

[[1,2,3], [7,6,8], [0,3,4]] 

e li somma in una lista tradurre le liste successive per il numero di posizioni lungo esso è. Quindi, lavorando sulla lista esempio sarebbe effettivamente fare qualcosa di simile:

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]] 

Ecco la mia funzione attuale (che ottiene digitare errori):

addLists :: [[Integer]] -> [Integer] 
    addLists [[]] = [] 
    addLists [[x]] = [x] 
    addLists [x:xs] = zipWith (+) [x] ([0]++ (addLists xs)) 

Answer 1

Penso che questo fa ciò che si vuole

import Data.List (transpose) 

addLists :: Num a => [[a]] -> [a] 
addLists xs = map sum . transpose $ zipWith (\n x -> replicate n 0 ++ x) [0..] xs 

Answer 2

Nota che ([0]++) è lo stesso di (0:), che lo renderà più ordinato e ci farà risparmiare un nanosecondo o due. (Sto scherzando con la cosa al nanosecondo - nessun umano può dire quando qualcosa è un nanosecondo più veloce, ma è comunque più bello.)

Iniziamo a pensare di creare gli elenchi di cui hai bisogno. Vogliamo

postponeLists [[1,2,3], [7,6,8], [10,20,30,40]] 
      = [[1,2,3], [0,7,6,8], [0,0,10,20,30,40]] 
      = [1,2,3] : ones that should have zero in front of them 

Questo è abbastanza informazioni per una definizione:

postponeLists [] = [] 
postponeLists (l:ls) = l : map (0:) (postponeLists ls) 

Ora è detto

foldl (zipWith +) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]] 

ma intendiamo

foldl (zipWith (+)) [] [[1,2,3],[0,7,6,8],[0,0,0,3,4]] 

ma purtroppo, che ti dà [] perché zipWith si interrompe non appena uno degli elenchi si esaurisce di elementi. Abbiamo bisogno di un modo per zipparli che non si ferma.

Soluzione 1: trovare il più lungo, renderli tutti che maxlength utilizzando take maxlength.(++ repeat 0)
Soluzione 2: scrivere un'altra funzione zipWith che non si ferma.

io preferisco la soluzione 2. Diamo un'occhiata alla definition of zipWith

zipWith :: (a->b->c) -> [a]->[b]->[c] 
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs 
zipWith _ _  _  = [] -- here's the problem - it stops as soon as any list is empty 

OK, cerchiamo di non fermare allora:

zipWithMore :: (a -> a -> a) -> [a] -> [a] -> [a] 
zipWithMore f (a:as) (b:bs) = f a b : zipWithMore f as bs 
zipWithMore f []  bs  = bs -- if there's more in bs, use that 
zipWithMore f as  []  = as -- if there's more in as, use that 

Ora si può sostituire con zipWith (+)zipWithMore (+). Lascerò la battuta finale a te.