Triparticiones de una lista
Definir la función
|
1 |
triparticiones :: [a] -> [([a],[a],[a])] |
tal que (triparticiones xs) es la lista de las ternas (xs1,xs2,xs3) tales que su concatenación es xs. Por ejemplo,
|
1 2 3 4 |
ghci> triparticiones "abc" [("","","abc"),("","a","bc"),("","ab","c"),("","abc",""), ("a","","bc"),("a","b","c"),("a","bc",""),("ab","","c"), ("ab","c",""),("abc","","")] |
Comprobar con QuickCheck que, suponiendo que xs es una lista de elementos comparables por igualdad, entonces para cada terna de (triparticiones xs) se cumple que la concatenación de sus elementos es xs.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import Test.QuickCheck triparticiones :: [a] -> [([a],[a],[a])] triparticiones xs = [(xs1,xs2,xs3) | (xs1,ys) <- biparticiones xs, (xs2,xs3) <- biparticiones ys] -- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su -- concatenación es xs. Por ejemplo, -- ghci> biparticiones "abc" -- [("","abc"),("a","bc"),("ab","c"),("abc","")] biparticiones :: [a] -> [([a],[a])] biparticiones [] = [([],[])] biparticiones (x:xs) = ([],x:xs) : [(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs] -- La propiedad es prop_triparticiones :: Eq a => [a] -> Bool prop_triparticiones xs = all (\(xs1,xs2,xs3) -> xs1 ++ xs2 ++ xs3 == xs) (triparticiones xs) -- La comprobación es -- ghci> quickCheck prop_triparticiones -- +++ OK, passed 100 tests. |
Es poco eficiente para cadenas largas.