gefilterte Liste kartesisches Produkt ohne Zwischenliste

Ich versuche, ein gefiltertes kartesisches Produkt aus einer bestimmten Liste von Listen zu erstellen. Die naive Lösung ist folgende:gefilterte Liste kartesisches Produkt ohne Zwischenliste

import Data.Traversable (sequence) 

predicate :: [T] -> Bool 
predicate = ... 

filteredCartesianProduct :: [[T]] -> [[T]] 
filteredCartesianProduct = filter predicate . sequence

Ist Traversable mächtig genug, um es ohne Erstellen einer Zwischenliste zu tun? Gibt es einen idiomatischen Weg, dies zu tun?

Quelle

2017-01-29 lanskey

Angenommen, die Signatur Ihrer 'Prädikat'-Funktion ist korrekt, dann ist Ihre Implementierung von 'filteredPowerSet' falsch. Warum komponierst du 'Filter-Prädikat' mit' Sequenz'? Dies wird nicht überprüft. Sollte Ihre Implementierung nicht 'filteredPowerSet = Filterprädikat' sein? – liminalisht

Der deklarierte Typ impliziert, dass Sie bereits ein Potset, nicht ein Set, als Argument erhalten (oder zumindest erwarten). – chepner

Ich erhalte eine Liste von Listen, wie [[1,2], [3,4,5]], die Sequenz ergibt folgendes: [[1,3], [1,4], [1,5], [2,3], [2,4], [2,5]]. – lanskey

traverse codiert hier das Muster predicate hat die Form all foo für einige foo. Dann ist filteredCartesianProducttraverse (filter foo).

Wenn predicate sagt ja für jeden Präfix jeder Liste, auf die es sagt ja, Sie Rückzieher Muster haben:

filteredCartesianProduct = foldlM (\accum factor -> [new | x <- factor, let new = accum ++ [x], predicate new]) []

Ich frage mich, wie der ++ [_] Geruch loszuwerden.

Quelle

2017-01-29 19:39:19 Gurkenglas

gefilterte Liste kartesisches Produkt ohne Zwischenliste

Antwort

Verwandte Themen