Come trasformare un elenco di numeri interi in una matrice di vero e falso in Haskell

Question

In questo esercizio dovrei scrivere una funzione che riceva un elenco di numeri interi come argomento e fornisca una matrice o un elenco di elenchi. Il punto nel fare la matrice è che gli interi rappresentano il numero di True s in ogni colonna della matrice. Ad esempio

[2,4,1] 

deve essere tradotto a:

che nel sistema è rappresentato come una lista di liste:

[ [0,1,0], [0,1,0], [1,1,0], [1,1,1] ] 

Poiché non è facile da manipolare matrici (lista di liste) per colonne ho usato un trucco e ruotato la matrice di 90 gradi a sinistra usando transpose che fa apparire la matrice qui di seguito:

Poi ho sviluppato il seguente algoritmo per risolvere il problema:

1. Prendere il primo elemento della lista di input
2. Creare una lista di lunghezza maximum xs (la lunghezza di ogni lista è uguale all'elemento massimo nell'elenco)
3. Metti così tanti True nell'elenco come determina il primo elemento.
4. riempimento nel resto della lista con False
5. Fare lo stesso per tutti gli elementi e ruotare la matrice

Ho cercato di implementare due soluzioni ma ognuno ha un problema che non riesco a risolvere:

1. Questo funziona per il primo elemento più che bene, ma non so come applicare a tutti gli elementi della lista di input

   listToMatrix x = (replicate ((maximum x) - (head x)) False) ++ (replicate (head x) True)` 
   

2. Questo funziona per tutti gli elementi ma non può mantenere la lunghezza dell'elenco interno in modo che le liste abbiano lunghezze diverse.

   listToMatrix lst@(x:xs) = ((replicate ((maximum lst) - x) False) ++ (replicate x True)) : listToMatrix xs` 
   

Domanda 1: Come posso fare queste funzioni lavorano con modifiche minime?

Domanda 2: soluzioni più eleganti e compatte?

P.S. Ho usato 1 e 0 nelle matrici per renderle più leggibili ma in realtà sono True e False

Answer 1

Vorrei utilizzare il seguente approccio, che è compatibile con il tuo.

Come da voi proposto, usiamo transpose alla fine, poiché la matrice trasposta sembra più facile da generare.

f :: [Int] -> [[Bool]] 
f xs = transpose (...) 

Poi, ogni elemento di xs deve generare una nuova riga. Possiamo usare una comprensione di lista (fatta sotto), o in alternativa usare map.

f :: [Int] -> [[Bool]] 
f xs = transpose [ row x | x <- xs ] 
    where row :: Int -> [Bool] 
     row x = ... 

Come lei suggerisce, abbiamo anche bisogno maximum per generare ogni riga, quindi calcoliamo una volta:

f :: [Int] -> [[Bool]] 
f xs = transpose [ row x | x <- xs ] 
    where m = maximum xs 
     row :: Int -> [Bool] 
     row x = ... -- we know x and m, we need m-x Falses and x Trues 

Ora, è solo bisogno di adattare il codice.

Answer 2

Ecco come lo farei:

toMatrix' :: [[Bool]] -> [Int] -> [[Bool]] 
toMatrix' acc xs 
    | or bools = toMatrix' (bools : acc) (map pred xs) 
    | otherwise = acc 
    where bools = map (> 0) xs 

toMatrix :: [Int] -> [[Bool]] 
toMatrix = toMatrix' [] 

semplice e diretto. Non c'è bisogno di trasporre.

Ecco la visualizzazione del mio programma. Userò 0 e 1 per False e True rispettivamente.

toMatrix [2,4,1] = toMatrix' []        [ 2, 4, 1] 
       = toMatrix' [[1,1,1]]       [ 1, 3, 0] 
       = toMatrix' [[1,1,0],[1,1,1]]     [ 0, 2,-1] 
       = toMatrix' [[0,1,0],[1,1,0],[1,1,1]]   [-1, 1,-2] 
       = toMatrix' [[0,1,0],[0,1,0],[1,1,0],[1,1,1]] [-2, 0,-3] 
       = [[0,1,0], 
        [0,1,0], 
        [1,1,0], 
        [1,1,1]] 

Quando chiamiamo toMatrix' acc xs prima calcoliamo bools = map (> 0) xs. Se tutti gli elementi di bools sono False, abbiamo finito. Restituiamo semplicemente acc. In caso contrario, aggiungere bools all'inizio di acc e sottrarre uno da ciascun elemento di xs. Risciacqua e ripeti.

Non è necessario tenere traccia dell'elemento più grande di xs e non è necessario trasporre la matrice. Semplice.