1votos

Combinaciones Posibles en Haskell

por josejuan hace 4 años

Usando mónadas.

Obtener todas las posibles combinaciones de un vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
combinacionesTomadosNenN xs n = mapM (const xs) [1..n] 
 
combinaciones xs = combinacionesTomadosNenN xs (length xs) 
 
 
 
 
-- para entender como funciona es mejor acudir a la definición de `mapM` 
mapM f = sequence . map f 
 
-- o, en nuestro caso, la versión 
sequence [xs, xs, ..., xs] 
 
-- de la definición de `sequence` https://hackage.haskell.org/package/base-4.7.0.2/docs/src/Control-Monad.html#sequence 
-- vemos que concatena la aplicación de la mónada interior 
-- que en este caso también es de listas, en 
    k m m' = do { x <- m; xs <- m'; return (x:xs) } 
 
-- se ve como se recolectan para cada `x` en `xs`, aplicando la mónada interior en cada 
-- iteración sobre el resultado monádico anterior (en este caso de listas), para verlo bien, 
-- se puede sustituir en `fold` por un `scan` 
   scanr k (return []) [xs,xs] 
 
-- con resultado 
   [[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]],[[1],[2],[3]],[[]]] 
 
-- ahora, debería ser obvio como actúa la doble acción monádica. 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.