Pensare al Prolog e ad Haskell - Generare liste di combinazioni di valori di verità

Question

Conosco un po 'di Prolog e ho appena iniziato un po' di studio individuale in Haskell. Ho lavorato attraverso lo 99 Problems for Haskell, imparando molto lungo la strada e godendo davvero Haskell. A volte cerco di chiarire la mia comprensione di uno spazio problematico codificando qualcosa in Prolog e poi pensando a come quella soluzione potrebbe riguardare un approccio funzionale in Haskell. Stasera, mentre lavoravo sui problemi relativi alla logica (problemi 47 e 48), mi sono distratto nel tentativo di realizzare il semplice compito di creare un elenco degli elenchi di tutte le combinazioni di valori di verità con n valori. Voglio una funzione tValues :: Int -> [[Bool]]. Questo problema può essere risolto in modo molto semplice e dichiarativa in Prolog, es .:

combinations_of_n_truth_values(N, AllValues) :- 
    findall(Values, n_truth_values(N, Values), AllValues). 

n_truth_values(N, TruthValues) :- 
    length(TruthValues, N), 
    maplist(truth_value, TruthValues). 

truth_value(true). 
truth_value(false). 

Quando usato, la variabile AllValues sarà unificare con l'elenco desiderato di elenchi di valori di verità. Mi piacerebbe sapere come un esperto programmatore Haskell dovrebbe risolvere questo stesso problema. Mi aspetto che ci sia una soluzione altrettanto semplice e dichiarativa, ma non riesco a far funzionare il mio cervello di Haskell nel modo giusto.

ho giocherellava con alcuni semi-analoghi utilizzando list comprehension, come ad esempio il seguente:

tValues:: Int -> [[Bool]] 
tValues 0 = [] 
tValues n = [v:vs | v <- tValue 
        , vs <- tValues (n-1) ] 

tValue :: [Bool] 
tValue = [True, False] 

ma tValues restituisce solo []. Penso di aver bisogno solo di un impegno da uomo a uomo per aiutare a scuotere la mia mente in modo chiaro e magari a darmi una visione più profonda.

Molte grazie.

Answer 1

In pseudo-codice, la lista la vostra comprensione

[v:vs | v <- tValue 
     , vs <- tValues (n-1) ] 

pari

for any combination of two elements in `tValue` and `tValues (n-1)` 
    cons the first onto the latter 

Tuttavia, tValues non ci sono elementi per cominciare, si tratta di una lista vuota. Consente di simulare questo per n = 1:

tValues 1 = [v:vs | v <- tValue 
        , vs <- tValues 0 ] 
      = [v:vs | v <- [True, False] 
        , vs <- [] ] 
      -- since there is no vs 
      = [] 

Questo propaga in tutta la ricorsione. La soluzione è molto semplice: cambiare il caso base per contenere una combinazione di vuoto:

tValues 0 = [[]] -- or: return [] 

Ora i rendimenti della simulazione:

tValues 1 = [v:vs | v <- tValue 
        , vs <- tValues 0 ] 
      = [v:vs | v <- [True, False] 
        , vs <- [[]]] 
      -- vs is [] 
      = [True:[],False:[]] 
      = [[True],[False]] 

che è proprio quello che volevamo.

Answer 2

truths :: [[Bool]] 
truths = [True] : [False] : concatMap (\bs -> [True:bs, False:bs]) truths 

truthValues :: Int -> [[Bool]] 
truthValues n = dropWhile ((< n) . length) . takeWhile ((<= n) . length) $ truths 

truths è un elenco infinito di tutte le combo valore di verità, perché le lunghezze aumentano monotonicamente possiamo solo prendere la parte anteriore della lista, mentre le lunghezze sono inferiori o uguali ai set che stiamo cercando, quindi rilasciare la parte anteriore di quelle le cui lunghezze sono inferiori.

Il motivo per cui si sta recuperando solo la lista vuota è che alla fine tValues (n-1) restituisce tValues 0 che è ovviamente la lista vuota. Provare a disegnare dalla lista vuota in una lista di comprensione fa fallire l'iterazione. Questo diffonde la catena di comprensione. Cambiare il caso base su tValues 1 = [[True], [False]] e funzionerà.

Answer 3

Non una risposta completa per sé, ma se vi interessa, con l'elenco monade:

truthValues ∷ Int → [[Bool]] 
truthValues 0 = return [] 
truthValues n = truthValues (n - 1) >>= (\l → [True:l, False:l]) 

o

truthValues n = foldM (\l _ -> [True:l, False:l]) [] [1..n] 

o

truthValues = flip replicateM [True, False] 

Vedi anche Will Ness' risposta e i commenti in allegato :)

Answer 4

Con la lista Monade,

g n = mapM (\_-> [True, False]) [1..n] 

Chi caso base della vostra funzione. Poiché la funzione restituisce un elenco contenente di valori di verità di lunghezza n, ne consegue che per n=0 deve restituire un elenco contenente tutti gli elenchi di valori di verità di lunghezza 0, ovvero un elenco contenente una lista vuota.